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.

* This talk is joint with the CS Theory seminar.