ITA 2010 – Random Graphs and Large Networks, Dimitris Achlioptas

The best-known model of random graphs was introduced 50 years ago, by Erdos and Renyi (ER): take n vertices and connect each pair of them, independently, with probability p(n).

By now, and thousands of research papers later, we know that ER random graphs have a number of amazing properties, many of which we understand very well.

A bit more slowly we have also come to understand that ER random graphs can be poor models of “network realities”: it is impossible to place the vertices of a (typical) ER random graph in a low-dimensional space, so that for each pair of vertices, their geometric distance is a good approximation of their graphical (shortest-path) distance. In other words, ER random graphs are inherently high-dimensional objects, in contrast to many real networks.

In this tutorial talk we will survey some of the fundamental results for ER random graphs and use them as springboards to introduce (and compare with) alternative random graph models.

Leave a Comment