some text

Geometry and navigability in random graphs

The study of random graphs has been dominated for over fifty years by the Erdos-Renyi (ER) model. It is by now well-understood that ER graphs bear very little resemblance to real networks, rendering analytical results for ER graphs largely uninformative. The first part of the talk will be a quick concrete overview of the shortcomings and of a number of attempts to overcome them. We will see that all these attempts run afoul of the inherent tension between low-dimensionality, i.e., realism, and probabilistic independence, i.e., mathematical tractability. I will then describe some very recent work aimed at resolving this tension by avoiding to model random graphs as explicit probability distributions and presenting them instead as maximally random solutions to constrained optimization problems. While the work is still in early stages, I hope to demonstrate how this approach offers advantages both in terms of robustness and flexibility, by giving analytical results for network navigability.