TY - JOUR

T1 - First passage percolation on random graphs with finite mean degrees

AU - Bhamidi, S.

AU - Hofstad, van der, R.W.

AU - Hooghiemstra, G.

PY - 2010

Y1 - 2010

N2 - We study first passage percolation on the configuration model. Assuming that each edge has an independent exponentially distributed edge weight, we derive explicit distributional asymptotics for the minimum weight between two randomly chosen connected vertices in the network, as well as for the number of edges on the least weight path, the so-called hopcount.
We analyze the configuration model with degree power-law exponent \tau >2, in which the degrees are assumed to be i.i.d. with a tail distribution which is either of power-law form with exponent \tau-1>1, or has even thinner tails (\tau=\infty). In this model, the degrees have a finite first moment, while the variance is finite for \tau>3, but infinite for \tau\in (2,3).
We prove a central limit theorem for the hopcount, with asymptotically equal means and variances equal to \alpha\log{n}, where \alpha\in (0,1) for \tau\in (2,3), while \alpha>1 for \tau>3. Here n denotes the size of the graph. For \tau\in (2,3), it is known that the graph distance between two randomly chosen connected vertices is proportional to \log\log{n} (van der Hofstad, Hooghiemtra and Znamenski (2007), i.e., distances are ultra small. Thus, the addition of edge weights causes a marked change in the geometry of the network. We further study the weight of the least weight path, and prove convergence in distribution of an appropriately centered version.

AB - We study first passage percolation on the configuration model. Assuming that each edge has an independent exponentially distributed edge weight, we derive explicit distributional asymptotics for the minimum weight between two randomly chosen connected vertices in the network, as well as for the number of edges on the least weight path, the so-called hopcount.
We analyze the configuration model with degree power-law exponent \tau >2, in which the degrees are assumed to be i.i.d. with a tail distribution which is either of power-law form with exponent \tau-1>1, or has even thinner tails (\tau=\infty). In this model, the degrees have a finite first moment, while the variance is finite for \tau>3, but infinite for \tau\in (2,3).
We prove a central limit theorem for the hopcount, with asymptotically equal means and variances equal to \alpha\log{n}, where \alpha\in (0,1) for \tau\in (2,3), while \alpha>1 for \tau>3. Here n denotes the size of the graph. For \tau\in (2,3), it is known that the graph distance between two randomly chosen connected vertices is proportional to \log\log{n} (van der Hofstad, Hooghiemtra and Znamenski (2007), i.e., distances are ultra small. Thus, the addition of edge weights causes a marked change in the geometry of the network. We further study the weight of the least weight path, and prove convergence in distribution of an appropriately centered version.

U2 - 10.1214/09-AAP666

DO - 10.1214/09-AAP666

M3 - Article

VL - 20

SP - 1907

EP - 1965

JO - The Annals of Applied Probability

JF - The Annals of Applied Probability

SN - 1050-5164

IS - 5

ER -