Scaling limits of random graph models at criticality: Universality and the basin of attraction of the Erd\H{o}s-R\'enyi random graph

Authors Shankar Bhamidi, Nicolas Broutin, Sanchayan Sen, Xuan Wang

Publication date 12 November 2014

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

Abstract: A wide array of random graph models have been postulated to understand properties of observed networks. Typically these models have a parameter

t

and a critical time

t_{c}

when a giant component emerges. It is conjectured that for a large class of models, the nature of this emergence is similar to that of the ErdH{o}s-R'enyi random graph, in the sense that (a) the sizes of the maximal components in the critical regime scale like

n^{2 / 3}

, and (b) the structure of the maximal components at criticality (rescaled by

n^{- 1 / 3}

) converges to random fractals. To date, (a) has been proven for a number of models using different techniques. This paper develops a general program for proving (b) that requires three ingredients: (i) in the critical scaling window, components merge approximately like the multiplicative coalescent, (ii) scaling exponents of susceptibility functions are the same as that of the ErdH{o}s-R'enyi random graph, and (iii) macroscopic averaging of distances between vertices in the barely subcritical regime. We show that these apply to two fundamental random graph models: the configuration model and inhomogeneous random graphs with a finite ground space. For these models, we also obtain new results for component sizes at criticality and structural properties in the barely subcritical regime.

This page was built for publication: Scaling limits of random graph models at criticality: Universality and the basin of attraction of the Erd\H{o}s-R\'enyi random graph

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