Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-09T01:34:33.513Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of: Operations research and management science Graph theory Combinatorial probability

Published online by Cambridge University Press:  01 July 2016

Shankar Bhamidi ,
Remco van der Hofstad  and
Gerard Hooghiemstra
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: [email protected]
∗∗∗ Postal address: DIAM, Delft University of Technology, Mekelweg 4, 2628 CD Delft, The Netherlands. Email address: [email protected]
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).

Keywords

Configuration modelrandom graphfirst passage percolationhopcountextreme value theoryPoisson-Dirichlet distributionscale-free network

MSC classification

Primary: 60C05: Combinatorial probability 05C80: Random graphs 90B15: Network models, stochastic
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 42 , Issue 3 , September 2010 , pp. 706 - 738
Copyright
Copyright © Applied Probability Trust 2010 

References

Abramowitz, M. and Stegun, I. A. (eds) (1992). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. (Reprint of the 1972 edition.) Dover Publications, New York.Google Scholar
Albert, R., Jeong, H. and Barabási, A.-L. (2000). Error and attack tolerance of complex networks. Nature 406, 378–382.CrossRefGoogle ScholarPubMed
Aldous, D. J. and Bhamidi, S. (2010). Flows through random networks. To appear in Random Structures and Algorithms.CrossRefGoogle Scholar
Bender, E. A. and Canfield, E. R. (1978). The asymptotic number of labeled graphs with given degree sequences. J. Combinatorial Theory A 24, 296–307.CrossRefGoogle Scholar
Bhamidi, S. (2008). First passage percolation on locally treelike networks. I. Dense random graphs. J. Math. Phys. 49, 125218, 27 pp.CrossRefGoogle Scholar
Bhamidi, S., van der Hofstad, R. and Hooghiemstra, G. (2010). First passage percolation on sparse random graphs with finite mean degrees. To appear in Ann. Appl. Prob.Google Scholar
Bollobás, B. and Riordan, O. (2004). Robustness and vulnerability of scale-free random graphs. Internet Math. 1, 1–35.CrossRefGoogle Scholar
Durrett, R. (1988). Lecture Notes on Particle Systems and Percolation. Wadsworth & Brooks/Cole, Pacific Grove, CA.Google Scholar
Durrett, R. (2007). Random Graph Dynamics. Cambridge University Press.Google Scholar
Gradshteyn, I. S. and Ryzhik, I. M. (1965). Table of Integrals, Series, and Products, 4th edn. Academic Press, New York.Google Scholar
Hammersley, J. M. and Welsh, D. J. A. (1965). First-passage percolation, subadditive processes, stochastic networks, and generalized renewal theory. In Proc. Internat. Res. Semin. (Statist. Lab., University of California, Berkeley), Springer, New York, pp. 61–110.Google Scholar
Howard, C. D. (2004). Models of first-passage percolation. In Probability on Discrete Structures, Springer, Berlin, pp. 125–173.CrossRefGoogle Scholar
Janson, S. (1999). One, two and three times log n/n for paths in a complete graph with random weights. Combin. Prob. Comput. 8, 347–361.CrossRefGoogle Scholar
Janson, S. (2002). On concentration of probability. In Contemporary Combinatorics (Bolyai Soc. Math. Stud. 10), ed. Bollobás, B., János Bolyai Mathematical Society, Budapest, pp. 289–301.Google Scholar
Kallenberg, O. (2002). Foundations of Modern Probability, 2nd edn. Springer, New York.CrossRefGoogle Scholar
Meyers, L. A., Newman, M. E. J. and Pourbohloul, B. (2006). Predicting epidemics on directed contact networks. J. Theoret. Biol. 240, 400–418.CrossRefGoogle ScholarPubMed
Meyers, L. A., et al. (2005). Network theory and SARS: predicting outbreak diversity. J. Theoret. Biol. 232, 71–81.CrossRefGoogle ScholarPubMed
Molloy, M. and Reed, B. (1995). A critical point for random graphs with a given degree sequence. In Proc. 6th Internat. Sem. on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science, John Wiley, New York, pp. 161–179.Google Scholar
Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Rev. 45, 167–256.CrossRefGoogle Scholar
Pitman, J. and Yor, M. (1997). The two-parameter Poisson–Dirichlet distribution derived from a stable subordinator. Ann. Prob. 25, 855–900.CrossRefGoogle Scholar
Pruitt, W. E. (1987). The contribution to the sum of the summand of maximum modulus. Ann. Prob. 15, 885–896.CrossRefGoogle Scholar
Reittu, H. and Norros, I. (2004). On the power-law random graph model of massive data networks. Performance Evaluation 55, 3–23.CrossRefGoogle Scholar
Van den Esker, H., van der Hofstad, R., Hooghiemstra, G. and Znamenski, D. (2005). Distances in random graphs with infinite mean degrees. Extremes 8, 111–141.CrossRefGoogle Scholar
Van der Hofstad, R., Hooghiemstra, G. and Van Mieghem, P. (2001). First-passage percolation on the random graph. Prob. Eng. Inf. Sci. 15, 225–237.CrossRefGoogle Scholar
Van der Hofstad, R., Hooghiemstra, G. and Van Mieghem, P. (2002). The flooding time in random graphs. Extremes 5, 111–129.CrossRefGoogle Scholar
Van der Hofstad, R., Hooghiemstra, G. and Van Mieghem, P. (2005). Distances in random graphs with finite variance degrees. Random Structures Algorithms 27, 76–123.CrossRefGoogle Scholar
Van der Hofstad, R., Hooghiemstra, G. and Znamenski, D. (2007). Distances in random graphs with finite mean and infinite variance degrees. Electron. J. Prob. 12, 703–766.CrossRefGoogle Scholar
Wästlund, J. (2006). Random assignment and shortest path problems. In 4th Colloq. Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, Assoc. Discrete Math. Theoret. Comput. Sci., Nancy, pp. 31–38. Available at http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/issue/view/84/showToc.Google Scholar