First passage percolation on random graphs with finite mean degrees (Q1958506)

This paper determines precise asymptotics for the length of a minimum weight path on first passage percolation on a random graph with a given degree sequence. This degree sequence is power law with exponent greater than 2. In the context of first passage percolation on a random graph, there are two levels of randomness: the underlying random graph itself as well as the random weights of the edges, which here are assumed to be i.i.d. exponentially distributed random variables with mean 1. Thus, in this context, we consider two fixed nodes and the main question in first passage percolation is what is the length of a path between these two nodes that has minimum weight. In this paper, the authors give a precise answer to this question in the case where the degree sequence is power law with exponent greater than 2. The most surprising among their findings is that though in the case where the exponent of the degree sequence is between 2 and 3, most of the vertices are within distance \(O(\log \log n)\) from each other (where \(n\) is the total number of vertices), the length of a minimum total weight path is of logarithmic order. In particular, the authors show that the asymptotic distribution of the length of such a path is the normal distribution, whose expected value is \(\alpha \log n\), where \(\alpha\) is some positive number depending on the exponent of the power law. They also determine the asymptotic distribution the minimum weight itself.