{
  "id": "1404.4118",
  "version": "v2",
  "published": "2014-04-16T00:36:35.000Z",
  "updated": "2014-11-13T01:34:05.000Z",
  "title": "Continuum limit of critical inhomogeneous random graphs",
  "authors": [
    "Shankar Bhamidi",
    "Sanchayan Sen",
    "Xuan Wang"
  ],
  "comment": "49 pages, 2 figures. Assumption on exponential moments relaxed",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Motivated by applications, the last few years have witnessed tremendous interest in understanding the structure as well as the behavior of dynamics for inhomogeneous random graph models. In this study we analyze the maximal components at criticality of one famous class of such models, the rank-one inhomogeneous random graph model. 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 $n^{-1/3}$ converge in the Gromov-Haussdorf-Prokhorov metric to rescaled versions of the limit objects identified for the Erd\\H{o}s-R\\'enyi random graph components at criticality Addario-Berry, Broutin and Goldschmidt (2012). A key step is the construction of connected components of the random graph through an appropriate tilt of a famous class of random trees called $\\mathbf{p}$-trees (studied previously by Aldous, Miermont and Pitman (2004) and by Camarri and Pitman (2000)). 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 (see Braunstein et al., 2003) for such graph models. By asymptotic equivalence (Janson, 2010), the same results are true for the Chung-Lu model and the Britton-Deijfen-Lof model. A crucial ingredient of the proof of independent interest is tail bounds for the height of $\\mathbf{p}$-trees. The techniques developed in this paper form the main technical bedrock for proving continuum scaling limits in the critical regime for a wide array of other random graph models (Bhamidi, Broutin, Sen and Wang, 2014) including the configuration model and inhomogeneous random graphs with general kernels which were introduced by Bollobas, Janson and Riordan (2007).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-04-16T00:36:35.000Z",
      "abstract": "Motivated by applications, the last few years have witnessed tremendous interest in understanding the structure as well as the behavior of dynamics for inhomogeneous random graph models. In this study we analyze the maximal components at criticality of one famous class of such models, the rank one or Norros-Reittu inhomogeneous random graph model [36], [12, Section 16.4]. Viewing these components as measured random metric spaces, under finite exponential moment assumptions for the weight distribution, we show that the components in the critical scaling window with distances scaled by $n^{-1/3}$ converge in the Gromov-Haussdorf-Prokhorov metric to rescaled versions of the limit objects identified for the Erd\\H{o}s-R\\'enyi random graph components at criticality in [2]. 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 [14] for such graph models. By asymptotic equivalence [27], the same results are true for the Chung-Lu model [19-21] and the Britton-Deijfen-Lof model [16]. A crucial ingredient in the proof which is of independent interest is a tail bound for the height of $\\mathbf{p}$-trees [8,18].",
      "comment": "2 figures",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2014-11-13T01:34:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "05C80"
    ],
    "keywords": [
      "critical inhomogeneous random graphs",
      "continuum limit",
      "norros-reittu inhomogeneous random graph model",
      "finite exponential moment assumptions",
      "components"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 49,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1404.4118B"
    }
  }
}