Continuum limit of critical inhomogeneous random graphs

DOI10.1007/S00440-016-0737-XzbMATH Open1407.60014arXiv1404.4118OpenAlexW1608202680MaRDI QIDQ682809FDOQ682809

Shankar Bhamidi, Sanchayan Sen, Xuan Wang

Publication date: 5 February 2018

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

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 ErdH{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 $mathbfp$-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 $mathbfp$-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).

Full work available at URL: https://arxiv.org/abs/1404.4118

zbMATH Keywords

branching processescritical random graphsscaling limitsmultiplicative coalescentcontinuum random tree\(\mathbf {p}\)-trees

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Cites Work

• Statistical mechanics of complex networks
• The Structure and Function of Complex Networks
• The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality
• Title not available (Why is that?)
• A course in metric geometry
• Title not available (Why is that?)
• Title not available (Why is that?)
• The phase transition in inhomogeneous random graphs
• The birth of the giant component
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Connected components in random graphs with given expected degree sequences
• Critical behavior in inhomogeneous random graphs
• Asymptotic equivalence and contiguity of some random graphs
• Title not available (Why is that?)
• The average distances in random graphs with given expected degrees
• On a conditionally Poissonian graph process
• Title not available (Why is that?)
• Generating simple random graphs with prescribed degree distribution
• Component behavior near the critical point of the random graph process
• The asymptotic number of labeled graphs with given degree sequences
• The phase transition in the configuration model
• Random mappings, forests, and subsets associated with Abel-Cayley-Hurwitz multinomial expansions
• Random trees and applications
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent
• The continuum limit of critical random graphs
• Probability for Statistics and Machine Learning
• The Evolution of Random Graphs
• The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs
• Probability inequalities for the sum in sampling without replacement
• The scaling window for a random graph with a given degree sequence
• Scaling limits for critical inhomogeneous random graphs with finite third moments
• A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces
• The Phase Transition in the Erdős-Rényi Random Graph Process
• The Structure of a Random Graph at the Point of the Phase Transition
• Critical random graphs: limiting constructions and distributional properties
• Limit distributions and random trees derived from the birthday problem with unequal probabilities
• Critical random graphs and the structure of a minimum spanning tree
• Birth control for giants
• Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1.
• The component sizes of a critical random graph with given degree sequence
• Critical percolation on random regular graphs
• The scaling limit of the minimum spanning tree of the complete graph
• The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin's local time identity
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs

Cited In (18)

• Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
• Universality for critical heavy-tailed network models: metric structure of maximal components
• The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees
• Limits of multiplicative inhomogeneous random graphs and Lévy trees: the continuum graphs
• Convergence of blanket times for sequences of random walks on critical random graphs
• A probabilistic approach to the leader problem in random graphs
• Scaling limit of dynamical percolation on critical Erdős-Rényi random graphs
• Geometry of the minimal spanning tree of a random 3-regular graph
• Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes
• On breadth‐first constructions of scaling limits of random graphs and random unicellular maps
• Limits of multiplicative inhomogeneous random graphs and Lévy trees: limit theorems
• Stable graphs: distributions and line-breaking construction
• Critical random forests
• Big Jobs Arrive Early: From Critical Queues to Random Graphs
• Scaling Limits of Random Trees and Random Graphs
• Degree correlations in scale-free random graph models
• Local limits of spatial inhomogeneous random graphs
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs

   Recommendations

• The continuum limit of critical random graphs 👍 👎
• Novel scaling limits for critical inhomogeneous random graphs 👍 👎
• Critical random graphs: limiting constructions and distributional properties 👍 👎
• Limits of multiplicative inhomogeneous random graphs and Lévy trees: the continuum graphs 👍 👎
• Scaling limits for critical inhomogeneous random graphs with finite third moments 👍 👎
• Critical behavior in inhomogeneous random graphs 👍 👎
• A local limit theorem for the critical random graph 👍 👎
• The scaling limit of a critical random directed graph 👍 👎
• On the random graph structure near the critical point 👍 👎
• Scaling limits of random graphs from subcritical classes 👍 👎

This page was built for publication: Continuum limit of critical inhomogeneous random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q682809)