First passage percolation on random graphs with finite mean degrees

Abstract

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.

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

References in corpus (4)

• Optimal Paths in Disordered Complex Networks
• Diameters in preferential attachment models
• A preferential attachment model with random initial degrees
• The structure of typical clusters in large sparse random configurations

Cited by in corpus (26)

• Ising models on power-law random graphs
• Interacting particle systems as stochastic social dynamics
• Explosion in weighted Hyperbolic Random Graphs and Geometric Inhomogeneous Random Graphs
• Weak disorder asymptotics in the stochastic mean-field model of distance
• The shape of shortest paths in random spatial networks
• The diameter of weighted random graphs
• Power-law relations in random networks with communities
• First Passage Percolation on Inhomogeneous Random Graphs
• The front of the epidemic spread and first passage percolation
• Kardar-Parisi-Zhang Universality in First-Passage Percolation: the Role of Geodesic Degeneracy
• Weighted distances in scale-free configuration models
• Weighted distances in scale-free preferential attachment models
• When is a scale-free graph ultra-small?
• Weak disorder in the stochastic mean-field model of distance II
• Distance evolutions in growing preferential attachment graphs
• First passage percolation on the Newman-Watts small world model
• Degree distribution of shortest path trees and bias of network sampling algorithms
• Local neighbourhoods for first passage percolation on the configuration model
• Probability-graphons: Limits of large dense weighted graphs
• Information spreading in a large population of active transmitters and passive receivers
• Flooding and Diameter in General Weighted Random Graphs
• On the Markov transition kernels for first-passage percolation on the ladder
• Degrees and distances in random and evolving Apollonian networks
• First passage percolation on Erdős-Rényi graphs with general weights
• First passage percolation in sparse random graphs with boundary weights
• Infinite paths on a random environment of ${\mathbb{Z}}^2$ with bounded and recurrent sums