Abstract:

The study of random graphs has been dominated for over fifty years by the Erdos-Renyi (ER) model, wherein edges are present independently of one another. It is by now well-understood that ER graphs bear very little resemblance to real networks, rendering mathematical results about them largely uninformative. The first part of the talk will be an overview of the shortcomings of ER random graphs and of attempts to overcome them. We will see how these attempts run afoul of the inherent tension between low-dimensionality, i.e., realism, and probabilistic independence, i.e., mathematical tractability. The second part of the talk discusses some recent work aimed at resolving this tension by avoiding to model random networks as explicit probability distributions, defining them instead as maximally entropic solutions to constrained optimization problems. We will see how this approach offers advantages both in terms of robustness and flexibility, by giving analytical results for network navigability.