Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T05:54:38.007Z Has data issue: false hasContentIssue false
  • English
  • Français

Nonuniversality of weighted random graphs with infinite variance degree

Part of: Probability theory on algebraic and topological structures Graph theory

Published online by Cambridge University Press:  04 April 2017

Enrico Baroni ,
Remco van der Hofstad  and
Júlia Komjáthy
Enrico Baroni*
Affiliation:
Eindhoven University of Technology
Remco van der Hofstad*
Affiliation:
Eindhoven University of Technology
Júlia Komjáthy*
Affiliation:
Eindhoven University of Technology
*
* Postal address: Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB, Eindhoven,The Netherlands.
* Postal address: Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB, Eindhoven,The Netherlands.
* Postal address: Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB, Eindhoven,The Netherlands.
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove nonuniversality results for first-passage percolation on the configuration model with independent and identically distributed (i.i.d.) degrees having infinite variance. We focus on the weight of the optimal path between two uniform vertices. Depending on the properties of the weight distribution, we use an example-based approach and show that rather different behaviours are possible. When the weights are almost surely larger than a constant, the weight and number of edges in the graph grow proportionally to log log n, as for the graph distances. On the other hand, when the continuous-time branching process describing the first-passage percolation exploration through the graph reaches infinitely many vertices in finite time, the weight converges to the sum of two i.i.d. random variables representing the explosion times of the continuous-time processes started from the two sources. This nonuniversality is in sharp contrast to the setting where the degree sequence has a finite variance, Bhamidi et al. (2012).

Keywords

Configuration modeluniversalityfirst-passage percolationpower-law degree

MSC classification

Primary: 05C80: Random graphs
Secondary: 60B10: Convergence of probability measures
Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 1 , March 2017 , pp. 146 - 164
Copyright
Copyright © Applied Probability Trust 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Albert, R. and Barabási, A.-L. (2002).Statistical mechanics of complex networks.Rev. Mod. Phys. 74,47–97.CrossRefGoogle Scholar
[2] Albert, R., Albert, I.and Nakarado, G. L. (2004).Structural vulnerability of the North American power grid.Phys. Rev. E 69, 125103.CrossRefGoogle ScholarPubMed
[3] Amini, O., Devroye, L., Griffiths, S. and Olver, N. (2013).On explosions in heavy-tailed branching random walks.Ann. Prob. 41,1864–1899.CrossRefGoogle Scholar
[4] Barabási, A. L., Réka, A. and Hawoong, J. (2000).Scale-free characteristics of random networks: the topology of the world-wide web.Physica A 281,69–77.Google Scholar
[5] Baroni, E., van der Hofstad, R. and Komjáthy, J. (2015).Fixed speed competition on the configuration model with infinite variance degrees: unequal speeds.Electron. J. Prob. 20,1–48.CrossRefGoogle Scholar
[6] Bhamidi, S., van der Hofstad, R. and Hooghiemstra, G. (2010).First passage percolation on random graphs with finite mean degrees.Ann. Appl. Prob. 20,1907–1965.CrossRefGoogle Scholar
[7] Bhamidi, S., van der Hofstad, R. and Hooghiemstra, G. (2012).Universality for first passage percolation on sparse random graphs. To appear in Ann. Prob. Available at https://arxiv.org/pdf1210.6839.pdf.Google Scholar
[8] Bollobás, B. (1980).A probabilistic proof of an asymptotic formula for the number of labelled regular graphs.Europ. J. Combinatorics 1,311–316.CrossRefGoogle Scholar
[9] Bollobás, B. (2001). Random Graphs.Cambridge University Press.CrossRefGoogle Scholar
[10] Bornholdt, S. and Schuster, H. G. (2003).Handbook of Graphs and Networks.John Wiley,New York.Google Scholar
[11] Chernoff, H. (1952).A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.Ann. Math. Statist. 23,493–507.CrossRefGoogle Scholar
[12] Davies, P. L. (1978).The simple branching process: a note on convergence when the mean is infinite.J. Appl. Prob. 15,466–480.CrossRefGoogle Scholar
[13] Deijfen, M. and van der Hofstad, R. (2016).The winner takes it all.Ann. Appl. Prob. 26,2419–2453.Google Scholar
[14] Erdős, P. and Rényi, A. (1959).On random graphs I.Publ. Math. Debrecen 6,290–297.Google Scholar
[15] Faloutsos, M., Faloutsos, P. and Faloutsos, C. (1999).On power-law relationships of the internet topology.Comp. Commun. Rev. 29,251–262.CrossRefGoogle Scholar
[16] Fountoulakis, N. (2007).Percolation on sparse random graphs with given degree sequence.Internet Math. 4,329–356.Google Scholar
[17] Grey, D. R. (1974).Explosiveness of age-dependent branching processes.Z. Wahrscheinlichkeit. 28,129–137.Google Scholar
[18] Harris, T. (1963).The Theory of Branching Processes.Springer,Berlin.Google Scholar
[19] Janson, S. (2009).On percolation in random graphs with given vertex degrees.Electron. J. Prob. 14,86–118.Google Scholar
[20] Janson, S. and Luczak, M. J. (2009).A new approach to the giant component problem.Random Structures Algorithms 34,197–216.Google Scholar
[21] Jasny, B. R., Zahn, L. M. and Marshall, E. (2009).Connections.Science 325, 405p.Google Scholar
[22] Kaluza, P., Kölzsch, A., Gastner, M. T. and Blasius, B. (2010).The complex network of global cargo ship movements.J. R. Soc. Interface. Available at http://rsif.royalsocietypublishing.org/content/early/2010/01/19/rsif.2009.0495.abstract.CrossRefGoogle ScholarPubMed
[23] Komjáthy, J. (2016).Explosive Crump–Mode–Jagers branching processes. Preprint. Available at https://arxiv.org/pdf/1602.01657v1.pdf.Google Scholar
[24] Molloy, M. and Reed, B. (1995).A critical point for random graphs with a given degree sequence.Random Structures Algorithms 6,161–180.Google Scholar
[25] Newman, M. E. J. (2003).The structure and function of complex networks.SIAM Rev. 45,167–256.CrossRefGoogle Scholar
[26] Radicchi, F., Fortunato, S. and Vespignani, A.(2012).Models of Science Dynamics. In Understanding Complex Systems, eds A. Scharnhost, K. Börner and P. van den Besselaar.Springer,Berlin, pp.233–257.Google Scholar
[27] Van der Hofstad, R. (2016).Random Graphs and Complex Networks, Vol. 1.Cambridge University Press.CrossRefGoogle Scholar
[28] Van der Hofstad, R. and Komjáthy, J. (2015).Fixed speed competition on the configuration model with infinite variance degrees: equal speeds.Electron. J. Prob. 20,1–48.Google Scholar
[29] Van der Hofstad, R. and Litvak, N. (2014).Degree-degree dependencies in random graphs with heavy-tailed degrees.Internet Math. 10,287–334.CrossRefGoogle Scholar
[30] 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
[31] Wu, J., Tse, C. K., Lau, F. C. M. and Ho, I. W. H. (2013).Analysis of communication network performance from a complex network perspective.IEEE T. Circuits Syst. 60,3303–3316.CrossRefGoogle Scholar