First passage percolation on random graphs with finite mean degrees

Details First passage percolation on random graphs with finite mean degrees First passage percolation on random graphs with finite mean degrees

2009-03-30

arxiv.org/abs/0903.5136v3

Annals of Applied Probability 2010, Vol. 20, No. 5, 1907-1965

Mathematics

Probability

Published in at http://dx.doi.org/10.1214/09-AAP666 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Inst

Scientific paper

10.1214/09-AAP666

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}$ [Electron. J. Probab. 12 (2007) 703--766], that is, 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. This study continues the program initiated in [J. Math. Phys. 49 (2008) 125218] of showing that $\log{n}$ is the correct scaling for the hopcount under i.i.d. edge disorder, even if the graph distance between two randomly chosen vertices is of much smaller order. The case of infinite mean degrees ($\tau\in[1,2)$) is studied in [Extreme value theory, Poisson--Dirichlet distributions and first passage percolation on random networks (2009) Preprint] where it is proved that the hopcount remains uniformly bounded and converges in distribution.

Affiliated with

Also associated with

No associations

Rating

First passage percolation on random graphs with finite mean degrees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with First passage percolation on random graphs with finite mean degrees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and First passage percolation on random graphs with finite mean degrees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-424517