Heavy-tailed configuration models at criticality

Abstract

We study the critical behavior of the component sizes for the configuration model when the tail of the degree distribution of a randomly chosen vertex is a regularly-varying function with exponent $\tau -1$, where $\tau \in (3,4)$. The component sizes are shown to be of the order $n^{(\tau -2)/(\tau -1)}L(n{)}^{-1}$ for some slowly-varying function $L(\cdot )$. We show that the re-scaled ordered component sizes converge in distribution to the ordered excursions of a thinned Lévy process. This proves that the scaling limits for the component sizes for these heavy-tailed configuration models are in a different universality class compared to the Erdős-Rényi random graphs. Also the joint re-scaled vector of ordered component sizes and their surplus edges is shown to have a distributional limit under a strong topology. Our proof resolves a conjecture by Joseph, Ann. Appl. Probab. (2014) about the scaling limits of uniform simple graphs with i.i.d degrees in the critical window, and sheds light on the relation between the scaling limits obtained by Joseph and in this paper, which appear to be quite different. Further, we use percolation to study the evolution of the component sizes and the surplus edges within the critical scaling window, which is shown to converge in finite dimension to the augmented multiplicative coalescent process introduced by Bhamidi et. al., Probab. Theory Related Fields (2014). The main results of this paper are proved under rather general assumptions on the vertex degrees. We also discuss how these assumptions are satisfied by some of the frameworks that have been studied previously.

43 pages, revision of the paper

References in corpus (5)

• Epidemic spreading on complex networks with community structures
• The largest component in a subcritical random graph with a power law degree distribution
• Critical window for the configuration model: finite third moment degrees
• The local weak limit of the minimum spanning tree of the complete graph
• Universality for critical heavy-tailed network models: Metric structure of maximal components

Cited by in corpus (14)

• Critical window for the configuration model: finite third moment degrees
• Universality for critical heavy-tailed network models: Metric structure of maximal components
• Switchover phenomenon induced by epidemic seeding on geometric networks
• Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees
• Global lower mass-bound for critical configuration models in the heavy-tailed regime
• Scaling limit of dynamical percolation on critical Erdös-Rényi random graphs
• On breadth-first constructions of scaling limits of random graphs and random unicellular maps
• Limit of trees with fixed degree sequence
• Universality for the directed configuration model: metric space convergence of the strongly connected components at criticality
• Critical Percolation on Random Networks with Prescribed Degrees
• Critical scaling limits of the random intersection graph
• Critical random forests
• Almost-2-regular random graphs
• Scaling limits and universality: Critical percolation on weighted graphs converging to an $L^3$ graphon