Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 15(2010) > Paper 54 open journal systems 


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: PDF

Pages: 1682-1702

Published on: November 2, 2010
Bibliography
  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).













Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489