Novel scaling limits for critical inhomogeneous random graphs

Abstract

We find scaling limits for the sizes of the largest components at criticality for rank-1 inhomogeneous random graphs with power-law degrees with power-law exponent τ. We investigate the case where $\tau \in (3,4)$, so that the degrees have finite variance but infinite third moment. The sizes of the largest clusters, rescaled by $n^{-(\tau -2)/(\tau -1)}$, converge to hitting times of a "thinned" Lévy process, a special case of the general multiplicative coalescents studied by Aldous [Ann. Probab. 25 (1997) 812-854] and Aldous and Limic [Electron. J. Probab. 3 (1998) 1-59]. Our results should be contrasted to the case τ>4, so that the third moment is finite. There, instead, the sizes of the components rescaled by $n^{-2/3}$ converge to the excursion lengths of an inhomogeneous Brownian motion, as proved in Aldous [Ann. Probab. 25 (1997) 812-854] for the Erdős-Rényi random graph and extended to the present setting in Bhamidi, van der Hofstad and van Leeuwaarden [Electron. J. Probab. 15 (2010) 1682-1703] and Turova [(2009) Preprint].

Published in at http://dx.doi.org/10.1214/11-AOP680 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (4)

• The phase transition in inhomogeneous random graphs
• Generating simple random graphs with prescribed degree distribution
• The largest component in a subcritical random graph with a power law degree distribution
• The component sizes of a critical random graph with given degree sequence

Cited by in corpus (13)

• Epidemic spreading on complex networks with community structures
• Critical window for the configuration model: finite third moment degrees
• Heavy-tailed configuration models at criticality
• Local clustering in scale-free networks with hidden variables
• Universality for critical heavy-tailed network models: Metric structure of maximal components
• Ising critical behavior of inhomogeneous Curie-Weiss models and annealed random graphs
• Rigid representations of the multiplicative coalescent with linear deletion
• Switchover phenomenon induced by epidemic seeding on geometric networks
• A large-deviations principle for all the components in a sparse inhomogeneous random graph
• On rate of convergence to the Poisson law of the number of cycles in the generalized random graphs
• Mesoscopic scales in hierarchical configuration models
• Expansion of percolation critical points for Hamming graphs
• Poisson approximation for cycles in the generalised random graph