The Annals of Probability

Novel scaling limits for critical inhomogeneous random graphs

Shankar Bhamidi, Remco van der Hofstad, and Johan S. H. van Leeuwaarden

Full-text: Open access

Enhanced PDF (523 KB)

Abstract

We find scaling limits for the sizes of the largest components at criticality for rank-1 inhomogeneous random graphs with power-law degrees with power-law exponent τ. We investigate the case where τ∈(3,4), so that the degrees have finite variance but infinite third moment. The sizes of the largest clusters, rescaled by n−(τ−2)/(τ−1), converge to hitting times of a “thinned” Lévy process, a special case of the general multiplicative coalescents studied by Aldous [Ann. Probab. 25 (1997) 812–854] and Aldous and Limic [Electron. J. Probab. 3 (1998) 1–59].

Our results should be contrasted to the case τ>4, so that the third moment is finite. There, instead, the sizes of the components rescaled by n−2/3 converge to the excursion lengths of an inhomogeneous Brownian motion, as proved in Aldous [Ann. Probab. 25 (1997) 812–854] for the Erdős–Rényi random graph and extended to the present setting in Bhamidi, van der Hofstad and van Leeuwaarden [Electron. J. Probab. 15 (2010) 1682–1703] and Turova [(2009) Preprint].

Article information

Source
Ann. Probab., Volume 40, Number 6 (2012), 2299-2361.

Dates
First available in Project Euclid: 26 October 2012

Permanent link to this document
https://projecteuclid.org/euclid.aop/1351258728

Digital Object Identifier
doi:10.1214/11-AOP680

Mathematical Reviews number (MathSciNet)
MR3050505

Zentralblatt MATH identifier
1257.05157

Subjects
Primary: 60C05: Combinatorial probability 05C80: Random graphs [See also 60B20] 90B15: Network models, stochastic

Keywords
Critical random graphs phase transitions inhomogeneous networks thinned Lévy processes multiplicative coalescent

Citation

Bhamidi, Shankar; van der Hofstad, Remco; van Leeuwaarden, Johan S. H. Novel scaling limits for critical inhomogeneous random graphs. Ann. Probab. 40 (2012), no. 6, 2299--2361. doi:10.1214/11-AOP680. https://projecteuclid.org/euclid.aop/1351258728


Export citation

References

  • [1] Albert, R. and Barabási, A.-L. (2002). Statistical mechanics of complex networks. Rev. Modern Phys. 74 47–97.
    Mathematical Reviews (MathSciNet): MR1895096
    Zentralblatt MATH: 1205.82086
    Digital Object Identifier: doi:10.1103/RevModPhys.74.47
    Library Links
  • [2] Aldous, D. (1997). Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25 812–854.
    Mathematical Reviews (MathSciNet): MR1434128
    Zentralblatt MATH: 0877.60010
    Digital Object Identifier: doi:10.1214/aop/1024404421
    Project Euclid: euclid.aop/1024404421
    Library Links
  • [3] Aldous, D. and Limic, V. (1998). The entrance boundary of the multiplicative coalescent. Electron. J. Probab. 3 59 pp. (electronic).
    Mathematical Reviews (MathSciNet): MR1491528
    Zentralblatt MATH: 0889.60080
    Digital Object Identifier: doi:10.1214/EJP.v3-25
    Library Links
  • [4] Aldous, D. J. (1999). Deterministic and stochastic models for coalescence (aggregation and coagulation): A review of the mean-field theory for probabilists. Bernoulli 5 3–48.
    Mathematical Reviews (MathSciNet): MR1673235
    Digital Object Identifier: doi:10.2307/3318611
    Project Euclid: euclid.bj/1173707093
    Library Links
  • [5] Alon, N. and Spencer, J. H. (2000). The Probabilistic Method, 2nd ed. Wiley, New York. With an appendix on the life and work of Paul Erdős.
    Mathematical Reviews (MathSciNet): MR1885388
    Library Links
  • [6] Bertoin, J. (1996). Lévy Processes. Cambridge Tracts in Mathematics 121. Cambridge Univ. Press, Cambridge.
    Mathematical Reviews (MathSciNet): MR1406564
    Library Links
  • [7] Bertoin, J. (2006). Random Fragmentation and Coagulation Processes. Cambridge Studies in Advanced Mathematics 102. Cambridge Univ. Press, Cambridge.
    Mathematical Reviews (MathSciNet): MR2253162
    Library Links
  • [8] Bhamidi, S., van der Hofstad, R. and van Leeuwaarden, J. S. H. (2010). Scaling limits for critical inhomogeneous random graphs with finite third moments. Electron. J. Probab. 15 1682–1703.
    Mathematical Reviews (MathSciNet): MR2735378
    Zentralblatt MATH: 1228.60018
    Digital Object Identifier: doi:10.1214/EJP.v15-817
    Library Links
  • [9] Billingsley, P. (1999). Convergence of Probability Measures, 2nd ed. Wiley, New York.
    Mathematical Reviews (MathSciNet): MR1700749
    Library Links
  • [10] Bollobás, B. (2001). Random Graphs, 2nd ed. Cambridge Studies in Advanced Mathematics 73. Cambridge Univ. Press, Cambridge.
    Mathematical Reviews (MathSciNet): MR1864966
    Library Links
  • [11] Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31 3–122.
    Mathematical Reviews (MathSciNet): MR2337396
    Library Links
  • [12] Britton, T., Deijfen, M. and Martin-Löf, A. (2006). Generating simple random graphs with prescribed degree distribution. J. Stat. Phys. 124 1377–1397.
    Mathematical Reviews (MathSciNet): MR2266448
    Zentralblatt MATH: 1106.05086
    Digital Object Identifier: doi:10.1007/s10955-006-9168-x
    Library Links
  • [13] Chung, F. and Lu, L. (2002). The average distances in random graphs with given expected degrees. Proc. Natl. Acad. Sci. USA 99 15879–15882 (electronic).
    Mathematical Reviews (MathSciNet): MR1944974
    Zentralblatt MATH: 1064.05137
    Digital Object Identifier: doi:10.1073/pnas.252631999
    Library Links
  • [14] Chung, F. and Lu, L. (2002). Connected components in random graphs with given expected degree sequences. Ann. Comb. 6 125–145.
    Mathematical Reviews (MathSciNet): MR1955514
    Zentralblatt MATH: 1009.05124
    Digital Object Identifier: doi:10.1007/PL00012580
    Library Links
  • [15] Chung, F. and Lu, L. (2003). The average distance in a random graph with given expected degrees. Internet Math. 1 91–113.
    Mathematical Reviews (MathSciNet): MR2076728
    Zentralblatt MATH: 1065.05084
    Digital Object Identifier: doi:10.1080/15427951.2004.10129081
    Project Euclid: euclid.im/1057768561
    Library Links
  • [16] Chung, F. and Lu, L. (2006). Complex Graphs and Networks. CBMS Regional Conference Series in Mathematics 107. Conference Board of the Mathematical Sciences, Washington, DC.
    Mathematical Reviews (MathSciNet): MR2248695
    Zentralblatt MATH: 1114.90071
    Library Links
  • [17] Chung, F. and Lu, L. (2006). The volume of the giant component of a random graph with given expected degrees. SIAM J. Discrete Math. 20 395–411 (electronic).
    Mathematical Reviews (MathSciNet): MR2257269
    Zentralblatt MATH: 1119.05098
    Digital Object Identifier: doi:10.1137/050630106
    Library Links
  • [18] Dorogovtsev, S. N. and Mendes, J. F. F. (2002). Evolution of networks. Adv. Phys. 51 1079–1187.
    Mathematical Reviews (MathSciNet): MR1993912
    Zentralblatt MATH: 1109.68537
    Library Links
  • [19] Durrett, R. (2007). Random Graph Dynamics. Cambridge Univ. Press, Cambridge.
    Mathematical Reviews (MathSciNet): MR2271734
    Library Links
  • [20] Grimmett, G. (1999). Percolation, 2nd ed. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 321. Springer, Berlin.
    Mathematical Reviews (MathSciNet): MR1707339
    Library Links
  • [21] Grimmett, G. R. and Stirzaker, D. R. (2001). Probability and Random Processes, 3rd ed. Oxford Univ. Press, New York.
    Mathematical Reviews (MathSciNet): MR2059709
    Library Links
  • [22] Hatami, H. and Molloy, M. (2009). The scaling window for a random graph with a given degree sequence. Available at arXiv:0907.4211.
    arXiv: 0907.4211
    Mathematical Reviews (MathSciNet): MR2809753
    Zentralblatt MATH: 1247.05218
    Library Links
  • [23] Jacod, J. and Shiryaev, A. N. (2003). Limit Theorems for Stochastic Processes, 2nd ed. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 288. Springer, Berlin.
    Mathematical Reviews (MathSciNet): MR1943877
    Library Links
  • [24] Janson, S. (2008). The largest component in a subcritical random graph with a power law degree distribution. Ann. Appl. Probab. 18 1651–1668.
    Mathematical Reviews (MathSciNet): MR2434185
    Zentralblatt MATH: 1149.60007
    Digital Object Identifier: doi:10.1214/07-AAP490
    Project Euclid: euclid.aoap/1216677136
    Library Links
  • [25] Janson, S. (2010). Asymptotic equivalence and contiguity of some random graphs. Random Structures Algorithms 36 26–45.
    Mathematical Reviews (MathSciNet): MR2591045
    Library Links
  • [26] Janson, S., Łuczak, T. and Rucinski, A. (2000). Random Graphs. Wiley, New York.
    Mathematical Reviews (MathSciNet): MR1782847
    Library Links
  • [27] Joseph, A. (2010). The component sizes of a critical random graph with pre-described degree sequence. Preprint.
  • [28] Kallenberg, O. (2002). Foundations of Modern Probability, 2nd ed. Springer, New York.
    Mathematical Reviews (MathSciNet): MR1876169
    Library Links
  • [29] Kyprianou, A. E. (2006). Introductory Lectures on Fluctuations of Lévy Processes with Applications. Springer, Berlin.
    Mathematical Reviews (MathSciNet): MR2250061
    Library Links
  • [30] Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Rev. 45 167–256 (electronic).
    Mathematical Reviews (MathSciNet): MR2010377
    Zentralblatt MATH: 1029.68010
    Digital Object Identifier: doi:10.1137/S003614450342480
    Library Links
  • [31] Norros, I. and Reittu, H. (2006). On a conditionally Poissonian graph process. Adv. in Appl. Probab. 38 59–75.
    Mathematical Reviews (MathSciNet): MR2213964
    Zentralblatt MATH: 1096.05047
    Digital Object Identifier: doi:10.1239/aap/1143936140
    Project Euclid: euclid.aap/1143936140
    Library Links
  • [32] Thorisson, H. (2000). Coupling, Stationarity, and Regeneration. Springer, New York.
    Mathematical Reviews (MathSciNet): MR1741181
    Zentralblatt MATH: 1163.22007
    Library Links
  • [33] Turova, T. S. (2009). Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1. Preprint.
  • [34] van der Hofstad, R. (2009). Critical behavior in inhomogeneous random graphs. Preprint.
  • [35] van der Hofstad, R. (2011). Random graphs and complex networks. Unpublished manuscript. Available at http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf.
  • [36] van der Hofstad, R., Janson, S. and Luczak, M. The near-critical behavior for the configuration model with finite-variance degrees. Unpublished manuscript.

The Institute of Mathematical Statistics

The Annals of Probability

New content alerts

Email RSS ToC RSS Article
  • You have access to this content.
  • You have partial access to this content.
  • You do not have access to this content.
Turn Off MathJax

What is MathJax?

More like this

+ See more