Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T18:43:21.200Z Has data issue: false hasContentIssue false

Extreme value theory, Poisson-Dirichlet distributions, and first passage percolation on random networks

Published online by Cambridge University Press:  01 July 2016

Shankar Bhamidi*
Affiliation:
University of North Carolina
Remco van der Hofstad*
Affiliation:
Eindhoven University of Technology
Gerard Hooghiemstra*
Affiliation:
Delft University of Technology
*
∗ Postal address: Department of Statistics and Operations Research, University of North Carolina, #304 Hanes Hall, Chapel Hill, NC 27599, USA.
∗∗ Postal address: Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, The Netherlands. Email address: rhofstad@win.tue.nl
∗∗∗ Postal address: DIAM, Delft University of Technology, Mekelweg 4, 2628 CD Delft, The Netherlands. Email address: g.hooghiemstra@ewi.tudelft.nl
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We study first passage percolation (FPP) on the configuration model (CM) having power-law degrees with exponent τ ∈ [1, 2) and exponential edge weights. We derive the distributional limit of the minimal weight of a path between typical vertices in the network and the number of edges on the minimal-weight path, both of which can be computed in terms of the Poisson-Dirichlet distribution. We explicitly describe these limits via construction of infinite limiting objects describing the FPP problem in the densely connected core of the network. We consider two separate cases, the original CM, in which each edge, regardless of its multiplicity, receives an independent exponential weight, and the erased CM, for which there is an independent exponential weight between any pair of direct neighbors. While the results are qualitatively similar, surprisingly, the limiting random variables are quite different. Our results imply that the flow carrying properties of the network are markedly different from either the mean-field setting or the locally tree-like setting, which occurs as τ > 2, and for which the hopcount between typical vertices scales as log n. In our setting the hopcount is tight and has an explicit limiting distribution, showing that information can be transferred remarkably quickly between different vertices in the network. This efficiency has a down side in that such networks are remarkably fragile to directed attacks. These results continue a general program by the authors to obtain a complete picture of how random disorder changes the inherent geometry of various random network models; see Aldous and Bhamidi (2010), Bhamidi (2008), and Bhamidi, van der Hofstad and Hooghiemstra (2009).

Information

Type
General Applied Probability
Copyright
Copyright © Applied Probability Trust 2010