Heavy-tailed configuration models at criticality

DOI10.1214/19-AIHP980zbMATH Open1475.60020arXiv1612.00650MaRDI QIDQ2227459FDOQ2227459

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)

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.

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

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

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)

Cites Work

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

Cited In (17)

• 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
• Component structure of the configuration model: barely supercritical case
• 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
• Title not available (Why is that?)
• Mesoscopic scales in hierarchical configuration models
• Critical window for connectivity in the configuration model
• Universality for the directed configuration model: metric space convergence of the strongly connected components at criticality
• A probabilistic approach to the leader problem in random graphs
• Upper bounds for number of removed edges in the erased configuration model
• 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
• Largest component of subcritical random graphs with given degree sequence
• Stable graphs: distributions and line-breaking construction
• Global lower mass-bound for critical configuration models in the heavy-tailed regime
• Critical window for the configuration model: finite third moment 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)