Heavy-tailed configuration models at criticality

DOI10.1214/19-AIHP980MaRDI QIDQ2227459zbMATH OpenFDO

Authors Souvik Dhara, Remco van der Hofstad, Sanchayan Sen, Johan S. H. van Leeuwaarden

Publication date 15 February 2021

Published in Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.00650, https://projecteuclid.org/euclid.aihp/1593137302

zbMATH Keywords

universalitycritical percolationcritical configuration modelaugmented multiplicative coalescentheavy-tailed degreethinned Lévy process

Mathematics Subject Classification ID

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

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 $au-1$, where $auin(3,4)$. The component sizes are shown to be of the order $n^{(au-2)/(au-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'evy 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 ErdH{o}s-R'enyi 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.

Recommendations

• Critical window for the configuration model: finite third moment degrees
• Critical percolation on scale-free random graphs: new universality class for the configuration model
• The component sizes of a critical random graph with given degree sequence
• Universality for critical heavy-tailed network models: metric structure of maximal components
• Global lower mass-bound for critical configuration models in the heavy-tailed regime

Cites work

• scientific article; zbMATH DE number 3951715 (Why is no real title available?)
• scientific article; zbMATH DE number 43570 (Why is no real title available?)
• scientific article; zbMATH DE number 3581363 (Why is no real title available?)
• scientific article; zbMATH DE number 739283 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 918811 (Why is no real title available?)
• scientific article; zbMATH DE number 3049368 (Why is no real title available?)
• A critical point for random graphs with a given degree sequence
• A new encoding of coalescent processes: applications to the additive and multiplicative cases
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Cluster tails for critical power-law inhomogeneous random graphs
• Compensators and Cox convergence
• Component behavior near the critical point of the random graph process
• Component structure of the configuration model: barely supercritical case
• Critical epidemics, random graphs, and Brownian motion with a parabolic drift
• Critical percolation on random regular graphs
• Critical window for the configuration model: finite third moment degrees
• Differential equations for random processes and random graphs
• Emergence of Scaling in Random Networks
• Foundations of Modern Probability
• Gray codes for partial match and range queries
• Large deviations for power-law thinned Lévy processes
• Novel scaling limits for critical inhomogeneous random graphs
• On a random graph with immigrating vertices: Emergence of the giant component
• On percolation in random graphs with given vertex degrees
• Percolation on sparse random graphs with given degree sequence
• Random graphs and complex networks. Volume 1
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• Scaling limits for critical inhomogeneous random graphs with finite third moments
• Statistical mechanics of complex networks
• Stochastic-Process Limits
• Susceptibility of random graphs with given vertex degrees
• The Evolution of Random Graphs
• The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs
• The birth of the giant component
• The component sizes of a critical random graph with given degree sequence
• The entrance boundary of the multiplicative coalescent
• The largest component in a subcritical random graph with a power law degree distribution
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs
• The phase transition in the configuration model
• The probability that a random multigraph is simple
• The scaling limit of the minimum spanning tree of the complete graph
• Universality for critical heavy-tailed network models: metric structure of maximal components

Cited in

(17)

• A probabilistic approach to the leader problem in random graphs
• Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
• Geometry of the minimal spanning tree of a random 3-regular graph
• Component structure of the configuration model: barely supercritical case
• Mesoscopic scales in hierarchical configuration models
• Upper bounds for number of removed edges in the erased configuration model
• Limits of multiplicative inhomogeneous random graphs and Lévy trees: the continuum graphs
• Global lower mass-bound for critical configuration models in the heavy-tailed regime
• Stable graphs: distributions and line-breaking construction
• Critical window for connectivity in the configuration model
• Universality for critical heavy-tailed network models: metric structure of maximal components
• Largest component of subcritical random graphs with given degree sequence
• Universality for the directed configuration model: metric space convergence of the strongly connected components at criticality
• Scaling limit of dynamical percolation on critical Erdős-Rényi random graphs
• scientific article; zbMATH DE number 7731163 (Why is no real title available?)
• Critical window for the configuration model: finite third moment degrees
• The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees

This page was built for publication: Heavy-tailed configuration models at criticality

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