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

DOI10.1239/AAP/1282924060MaRDI QIDQ3059693zbMATH OpenOpenAlexFDO

Authors Shankar Bhamidi, Remco van der Hofstad, Gerard Hooghiemstra

Publication date 26 November 2010

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0905.4438

zbMATH Keywords

random graphfirst passage percolationconfiguration modelscale-free networkpower law degree distribution

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Stochastic network models in operations research (90B15)

Abstract: We study first passage percolation on the configuration model (CM) having power-law degrees with exponent $auin[1,2)$. To this end we equip the edges with exponential 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, which can be computed in terms of the Poisson-Dirichlet distribution. We explicitly describe these limits via the construction of an infinite limiting object describing the FPP problem in the densely connected core of the network. We consider two separate cases, namely, the {it original CM}, in which each edge, regardless of its multiplicity, receives an independent exponential weight, as well as the {it 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 $au>2$, and for which the hopcount between typical vertices scales as $logn$. In our setting the hopcount is tight and has an explicit limiting distribution, showing that one can transfer information 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.

Recommendations

• Stochastic networks and the extreme value distribution
• Large deviation theory of percolation on multiplex networks
• Extreme events in stochastic transport on networks
• Poisson approximation and connectivity in a scale-free random connection model
• First passage percolation on random graphs with finite mean degrees
• First passage percolation on locally treelike networks. I. Dense random graphs
• First passage percolation on the Erdős-Rényi random graph
• The distribution of first hitting times of random walks on directed Erdős–Rényi networks
• Distributions in a class of Poissonized urns with an application to Apollonian networks
• First passage percolation on inhomogeneous random graphs

Cites work

• scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• scientific article; zbMATH DE number 193169 (Why is no real title available?)
• scientific article; zbMATH DE number 486467 (Why is no real title available?)
• scientific article; zbMATH DE number 2042288 (Why is no real title available?)
• scientific article; zbMATH DE number 1787234 (Why is no real title available?)
• scientific article; zbMATH DE number 3231627 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• A critical point for random graphs with a given degree sequence
• Distance in random graphs with infinite mean degrees
• Distances in random graphs with finite mean and infinite variance degrees
• Distances in random graphs with finite variance degrees
• Edge flows in the complete random-lengths network
• First passage percolation on locally treelike networks. I. Dense random graphs
• First passage percolation on random graphs with finite mean degrees
• First-passage percolation on the random graph
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Random assignment and shortest path problems
• Random graph dynamics
• Robustness and Vulnerability of Scale-Free Random Graphs
• The Structure and Function of Complex Networks
• The asymptotic number of labeled graphs with given degree sequences
• The contribution to the sum of the summand of maximum modulus
• The flooding time in random graphs
• The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator

Cited in

(18)

• Limiting distributions of generalised Poisson-Dirichlet distributions based on negative binomial processes
• Weighted distances in scale-free configuration models
• Competing first passage percolation on random regular graphs
• Long paths in first passage percolation on the complete graph II. Global branching dynamics
• Weak disorder asymptotics in the stochastic mean-field model of distance
• Distributions in a class of Poissonized urns with an application to Apollonian networks
• Local neighbourhoods for first-passage percolation on the configuration model
• The diameter of weighted random graphs
• WEIGHT OF THE SHORTEST PATH TO THE FIRST ENCOUNTERED PEER IN A PEER GROUP OF SIZE m
• Degree distribution of shortest path trees and bias of network sampling algorithms
• First passage percolation on the Erdős-Rényi random graph
• First passage percolation on random graphs with finite mean degrees
• New exploratory tools for extremal dependence: \(\chi \) networks and annual extremal networks
• The winner takes it all but one
• Convergence of directed random graphs to the Poisson-weighted infinite tree
• Epidemics and vaccination on weighted graphs
• Nonuniversality of weighted random graphs with infinite variance degree
• Joint distribution of distances in large random regular networks

This page was built for publication: Extreme value theory, Poisson-Dirichlet distributions, and first passage percolation on random networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3059693)