Scaling Limits for Critical Inhomogeneous Random Graphs with Finite Third Moments

Shankar Bhamidi (University of North Carolina)
Remco van der Hofstad (Eindhoven University of Technology)
Johan S.H. van Leeuwaarden (Eindhoven University of Technology)

Abstract


We identify the scaling limit for the sizes of the largest components at criticality for inhomogeneous random graphs with weights that have finite third moments. We show that the sizes of the (rescaled) components converge to the excursion lengths of an inhomogeneous Brownian motion, which extends results of Aldous (1997) for the critical behavior of Erdös-Rényi random graphs. We rely heavily on martingale convergence techniques, and concentration properties of (super)martingales. This paper is part of a programme initiated in van der Hofstad (2009) to study the near-critical behavior in inhomogeneous random graphs of so-called rank-1.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1682-1702

Publication Date: November 2, 2010

DOI: 10.1214/EJP.v15-817

References

  1. Aldous, David. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25 (1997), no. 2, 812--854. MR1434128 (98d:60019)

  2. Bhamidi, Shankar; van der Hofstad, Remco; van Leeuwaarden, Johan S.H.. Novel scaling limits for critical inhomogeneous random graphs. Preprint (2009).

  3. Billingsley, Patrick. Convergence of probability measures. Second edition. Wiley Series in Probability and Statistics: Probability and Statistics. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1999. x+277 pp. ISBN: 0-471-19745-9 MR1700749 (2000e:60008)

  4. Bollobás, Béla. Random graphs. Second edition. Cambridge Studies in Advanced Mathematics, 73. Cambridge University Press, Cambridge, 2001. xviii+498 pp. ISBN: 0-521-80920-7; 0-521-79722-5 MR1864966 (2002j:05132)

  5. Bollobás, Béla; Janson, Svante; Riordan, Oliver. The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31 (2007), no. 1, 3--122. MR2337396 (2008e:05124)

  6. Britton, Tom; Deijfen, Maria; Martin-Löf, Anders. Generating simple random graphs with prescribed degree distribution. J. Stat. Phys. 124 (2006), no. 6, 1377--1397. MR2266448 (2007g:05168)

  7. Chung, Fan; Lu, Linyuan. The average distances in random graphs with given expected degrees. Proc. Natl. Acad. Sci. USA 99 (2002), no. 25, 15879--15882 (electronic). MR1944974 (2003k:05124)

  8. Chung, Fan; Lu, Linyuan. Connected components in random graphs with given expected degree sequences. Ann. Comb. 6 (2002), no. 2, 125--145. MR1955514 (2003k:05123)

  9. Chung, Fan; Lu, Linyuan. The average distance in a random graph with given expected degrees. Internet Math. 1 (2003), no. 1, 91--113. MR2076728 (2005e:05122)

  10. Chung, Fan; Lu, Linyuan. Complex graphs and networks. CBMS Regional Conference Series in Mathematics, 107. Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2006. viii+264 pp. ISBN: 978-0-8218-3657-6; 0-8218-3657-9 MR2248695 (2007i:05169)

  11. Chung, Fan; Lu, Linyuan. The volume of the giant component of a random graph with given expected degrees. SIAM J. Discrete Math. 20 (2006), no. 2, 395--411 (electronic). MR2257269 (2007h:05144)

  12. Dudley, R. M. Real analysis and probability. Revised reprint of the 1989 original. Cambridge Studies in Advanced Mathematics, 74. Cambridge University Press, Cambridge, 2002. x+555 pp. ISBN: 0-521-00754-2 MR1932358 (2003h:60001)

  13. van den Esker, Henri; van der Hofstad, Remco; Hooghiemstra, Gerard. Universality for the distance in finite variance random graphs. J. Stat. Phys. 133 (2008), no. 1, 169--202. MR2438903 (2009k:05165)

  14. Ethier, Stewart N.; Kurtz, Thomas G. Markov processes. Characterization and convergence. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons, Inc., New York, 1986. x+534 pp. ISBN: 0-471-08186-8 MR0838085 (88a:60130)

  15. Gut, Allan. Probability: a graduate course. Springer Texts in Statistics. Springer, New York, 2005. xxiv+603 pp. ISBN: 0-387-22833-0 MR2125120 (2006a:60001)

  16. van der Hofstad, Remco. Critical behavior in inhomogeneous random graphs. Preprint (2009).

  17. van der Hofstad, Remco; Kager, Wouter; Müller, Tobias. A local limit theorem for the critical random graph. Electron. Commun. Probab. 14 (2009), 122--131. MR2481672 (2010g:05340)

  18. Janson, Svante. Asymptotic equivalence and contiguity of some random graphs. Random Structures Algorithms 36 (2010), no. 1, 26--45. MR2591045

  19. Janson, Svante; Łuczak, Tomasz; Rucinski, Andrzej. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. xii+333 pp. ISBN: 0-471-17541-2 MR1782847 (2001k:05180)

  20. Kallenberg, Olav. Foundations of modern probability. Second edition. Probability and its Applications (New York). Springer-Verlag, New York, 2002. xx+638 pp. ISBN: 0-387-95313-2 MR1876169 (2002m:60002)

  21. Martin-Löf, Anders. The final size of a nearly critical epidemic, and the first passage time of a Wiener process to a parabolic barrier. J. Appl. Probab. 35 (1998), no. 3, 671--682. MR1659544 (2000e:92046)

  22. Nachmias, Asaf; Peres, Yuval. Critical percolation on random regular graphs. Random Structures Algorithms 36 (2010), no. 2, 111--148. MR2583058

  23. Norros, Ilkka; Reittu, Hannu. On a conditionally Poissonian graph process. Adv. in Appl. Probab. 38 (2006), no. 1, 59--75. MR2213964 (2006m:05227)

  24. Pittel, Boris. On the largest component of the random graph at a nearcritical stage. J. Combin. Theory Ser. B 82 (2001), no. 2, 237--269. MR1842114 (2002j:05134)

  25. Rogers, L. C. G.; Williams, David. Diffusions, Markov processes, and martingales. Vol. 1. Foundations. Second edition. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons, Ltd., Chichester, 1994. xx+386 pp. ISBN: 0-471-95061-0 MR1331599 (96h:60116)

  26. Turova, Tatyana. Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1. Preprint (2009).

Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.