×

The component sizes of a critical random graph with given degree sequence. (English) Zbl 1318.60015

The theme of this paper is the limiting distribution of the component sizes of a critical random graph on \(n\) vertices with a given degree distribution. Let \(\nu_k\) denote the fraction of vertices that have \(k\) neighbours. The Molloy-Reed criterion for the existence of a giant component is the sign of the expression \(\sum_{k=1}^\infty k(k-2) \nu_k\). The author of the present paper considers the critical case, where \(\sum_{k=1}^\infty k(k-2) \nu_k = 0\) under the condition that \(\sum_{k>0} k^3 \nu_k < \infty\) and \(\nu_2 < 1\). The result obtained here is analogous to the result of D. Aldous [Ann. Probab. 25, No. 2, 812–854 (1997; Zbl 0877.60010)] on the component sizes distribution of a critical \(G(n,p)\) random graph. The author shows that the ordered vector of the component sizes rescaled by \(n^{-2/3}\) converges to the ordered vector of the excursion intervals of a Brownian motion with parabolic drift.

MSC:

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

Citations:

Zbl 0877.60010
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] Aldous, D. (1997). Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25 812-854. · Zbl 0877.60010
[2] Aldous, D. and Limic, V. (1998). The entrance boundary of the multiplicative coalescent. Electron. J. Probab. 3 59 pp. (electronic). · Zbl 0889.60080
[3] Arratia, R., Barbour, A. D. and Tavaré, S. (2003). Logarithmic Combinatorial Structures : A Probabilistic Approach . European Mathematical Society (EMS), Zürich. · Zbl 1040.60001
[4] Bender, E. A. and Canfield, E. R. (1978). The asymptotic number of labeled graphs with given degree sequences. J. Combin. Theory Ser. A 24 296-307. · Zbl 0402.05042
[5] Bertoin, J. (1996). Lévy Processes. Cambridge Tracts in Mathematics 121 . Cambridge Univ. Press, Cambridge. · Zbl 0861.60003
[6] Bertoin, J. and Sidoravicius, V. (2009). The structure of typical clusters in large sparse random configurations. J. Stat. Phys. 135 87-105. · Zbl 1168.82028
[7] 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. · Zbl 1228.60018
[8] Bhamidi, S., van der Hofstad, R. and van Leeuwaarden, J. S. H. (2012). Novel scaling limits for critical inhomogeneous random graphs. Ann. Probab. 40 2299-2361. · Zbl 1257.05157
[9] Bollobás, B. (1980). A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin. 1 311-316. · Zbl 0457.05038
[10] Bollobás, B. (2001). Random Graphs , 2nd ed. Cambridge Studies in Advanced Mathematics 73 . Cambridge Univ. Press, Cambridge. · Zbl 0979.05003
[11] Britton, T., Deijfen, M. and Martin-Löf, A. (2006). Generating simple random graphs with prescribed degree distribution. J. Stat. Phys. 124 1377-1397. · Zbl 1106.05086
[12] Erdős, P. and Rényi, A. (1960). On the evolution of random graphs. Magy. Tud. Akad. Mat. Kut. Intéz. Közl. 5 17-61. · Zbl 0103.16301
[13] Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes : Characterization and Convergence . Wiley, New York. · Zbl 0592.60049
[14] Hatami, H. and Molloy, M. (2010). The scaling window for a random graph with a given degree sequence. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms 1403-1411. SIAM, Philadelphia, PA. · Zbl 1288.05250
[15] 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. · Zbl 1018.60002
[16] Janson, S. (2008). The largest component in a subcritical random graph with a power law degree distribution. Ann. Appl. Probab. 18 1651-1668. · Zbl 1149.60007
[17] Janson, S. (2009). The probability that a random multigraph is simple. Combin. Probab. Comput. 18 205-225. · Zbl 1216.05145
[18] Janson, S. and Luczak, M. J. (2009). A new approach to the giant component problem. Random Structures Algorithms 34 197-216. · Zbl 1177.05110
[19] Kang, M. and Seierstad, T. G. (2008). The critical phase for random graphs with a given degree sequence. Combin. Probab. Comput. 17 67-86. · Zbl 1133.05092
[20] Molloy, M. and Reed, B. (1995). A critical point for random graphs with a given degree sequence. Random Structures Algorithms 6 161-179. · Zbl 0823.05050
[21] Molloy, M. and Reed, B. (1998). The size of the giant component of a random graph with a given degree sequence. Combin. Probab. Comput. 7 295-305. · Zbl 0916.05064
[22] Pittel, B. G. (2008). On the largest component of a random graph with a subpower-law degree sequence in a subcritical phase. Ann. Appl. Probab. 18 1636-1650. · Zbl 1149.05043
[23] Turova, T. S. (2013). Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1. Random Structures Algorithms 43 486-539. · Zbl 1278.05227
[24] van der Hofstad, R. (2013). Critical behavior in inhomogeneous random graphs. Random Structures Algorithms 42 480-508. · Zbl 1269.05101
[25] Wormald, N. C. (1978). Some problems in the enumeration of labelled graphs. Ph.D. thesis, Newcastle Univ. · Zbl 0386.05034
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.