First passage percolation on random graphs

We study the structure of minimal-weight paths in the configuration model with i.i.d. degrees with a fixed degree distribution. Here, each edge receives an independent exponential weight, leading to double randomness in the form of a stochastic process on a random graph.

We consider the hopcount, which equals the number of edges of the minimal-weight path between two uniformly chosen vertices, and the weight of this minimal path. When the degrees obey a power law with degree power-law exponent τ, then, whenever τ>2, we see that the hopcount obeys a central limit theorem with asymptotically equal mean and variance proportional to log n, where n is the size of the graph. A similar result was proved to hold on the complete graph, the difference being that the proportionality constant on the complete graph is equal to 1, whereas for the configuration model it is greater than 1 when τ>3 and in (0,1) when τ∈ (2,3). This gives a remarkably universal picture for first passage percolation on random graphs.

These results should be contrasted to the results when instead of i.i.d. exponential weights, each edge has a constant weight, so that the hopcount is equal to the graph distance on the graph. In the latter case, when τ∈ (2,3), the hopcount is asymptotically proportional to log log n, with uniformly bounded fluctuations.

We further discuss what happens when different edge weights are used. This problem is even quite hard on the complete graph, where it is sometimes referred to as Aldous’ stochastic mean-field model of distance. We discuss results and conjectures concerning the universality classes for this problem.

[This is joint work with Shankar Bhamidi and Gerard Hooghiemstra.]