Random Graphs From Less Randomness

Dimitris Achlioptas, UC/Santa Cruz - Computer Science
Mar 24 2014 - 4:30pm
Event type: 
PACM Colloquium
Fine 214

This is a Joint PACM/ORFE Colloquium

The study of random graphs has been dominated for over fifty years by the Erdos-Renyi (ER) model, wherein edges appear independently and with equal probability. It is by now well-understood that ER random graphs bear very little resemblance to real networks, rendering analytical results for them largely uninformative. After a quick overview of the ER model I will point out its main shortcomings and go over some of the attempts to overcome them. We will see that the main issue is the inherent tension between low-dimensionality, needed for realism, and probabilistic independence, needed for mathematical tractability. I will then describe recent work aimed at resolving this tension by defining random graphs as maximally random solutions to constrained optimization problems. Along with a strong concentration inequality we establish for the solutions of knapsack-like problems, this allows us to get natural generative models for random graphs which do not assume independence between edges, yet are highly tractable mathematically. As a demonstration of this tractability we prove that “navigability”, in the sense of Kleinberg, is a far more robust property of graphs than previously understood, arising without any coordination between the vertices, almost as soon as sufficient resources are present.