Continuum limit of critical inhomogeneous random graphs

S. Bhamidi, S. Sen, X. Wang

    Research output: Contribution to journalArticleAcademicpeer-review

    8 Citations (Scopus)

    Abstract

    The last few years have witnessed tremendous interest in understanding the structure as well as the behavior of dynamics for inhomogeneous random graph models to gain insight into real-world systems. In this study we analyze the maximal components at criticality of one famous class of such models, the rank-one inhomogeneous random graph model (Norros and Reittu, Adv Appl Probab 38(1):59–75, 2006; Bollobás et al., Random Struct Algorithms 31(1):3–122, 2007, Section 16.4). Viewing these components as measured random metric spaces, under finite moment assumptions for the weight distribution, we show that the components in the critical scaling window with distances scaled by (Formula presented.) converge in the Gromov–Haussdorf–Prokhorov metric to rescaled versions of the limit objects identified for the Erdős–Rényi random graph components at criticality in Addario-Berry et al. (Probab. Theory Related Fields, 152(3–4):367–406, 2012). A key step is the construction of connected components of the random graph through an appropriate tilt of a fundamental class of random trees called (Formula presented.)-trees (Camarri and Pitman, Electron. J. Probab 5(2):1–18, 2000; Aldous et al., Probab Theory Related Fields 129(2):182–218, 2004). This is the first step in rigorously understanding the scaling limits of objects such as the minimal spanning tree and other strong disorder models from statistical physics (Braunstein et al., Phys Rev Lett 91(16):168701, 2003) for such graph models. By asymptotic equivalence (Janson, Random Struct Algorithms 36(1):26–45, 2010), the same results are true for the Chung–Lu model (Chung and Lu, Proc Natl Acad Sci 99(25):15879–15882, 2002; Chung and Lu, Ann Combin 6(2):125–145, 2002; Chung and Lu, Complex graphs and networks, 2006) and the Britton–Deijfen–Martin–Löf model (Britton et al., J Stat Phys 124(6):1377–1397, 2006). A crucial ingredient of the proof of independent interest are tail bounds for the height of (Formula presented.)-trees. The techniques developed in this paper form the main technical bedrock for the general program developed in Bhamidi et al. (Scaling limits of random graph models at criticality: Universality and the basin of attraction of the Erdős–Rényi random graph. arXiv preprint, 2014) for proving universality of the continuum scaling limits in the critical regime for a wide array of other random graph models including the configuration model and inhomogeneous random graphs with general kernels (Bollobás et al., Random Struct Algorithms 31(1):3–122, 2007).

    Original languageEnglish
    Pages (from-to)565-641
    Number of pages77
    JournalProbability Theory and Related Fields
    Volume169
    Issue number1-2
    DOIs
    Publication statusPublished - 1 Oct 2017

    Keywords

    • Branching processes
    • Continuum random tree
    • Critical random graphs
    • Multiplicative coalescent
    • Scaling limits
    • p-trees

    Fingerprint Dive into the research topics of 'Continuum limit of critical inhomogeneous random graphs'. Together they form a unique fingerprint.

    Cite this