Component structure of the configuration model: barely supercritical case

DOI10.1002/RSA.20837MaRDI QIDQ5236922zbMATH OpenOpenAlexWikidataFDO

Authors Remco van der Hofstad, Svante Janson, Malwina Luczak

Publication date 16 October 2019

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

percolationphase transitionrandom graphsscaling window

Mathematics Subject Classification ID

Vertex degrees (05C07) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study near-critical behavior in the configuration model. Let $D_n$ be the degree of a random vertex. We let $u_n=mathbbE[D_n(D_n-1)]/mathbbE[D_n]$ and, assuming that $u_{n}o1$ as $noinfty$, we write $varepsilo{n}_n=u_n-1$. We call the setting where $varepsilo{n}_n{n}^{1/3}/(mathbbE[D_n^3]{)}^{2/3}oinfty$ the {it barely supercritical} regime. We further assume that the variance of $D_n$ is uniformly bounded as $noinfty$. Let $D_n^{\ast }$ denote the size-biased version of $D_n$. We prove that there is a unique giant component of size $nh{o}_{n}mathbbE{D}_n(1+o(1))$, where $h{o}_n$ denotes the survival probability of a branching process with offspring distribution $D_n^{\ast }-1$. This extends earlier results of Janson and Luczak~cite{JanLuc07}, as well as those of Janson, Luczak, Windridge and House~cite{SJ300} to the case where the third moment of $D_n$ is unbounded, filling the gap in the literature. We further study the size of the largest component in the emph{critical} regime, where $varepsilo{n}_n=O(n^{-1/3}(mathbbE{D}_n^3{)}^{2/3})$, extending and complementing results of Hatami and Molloy~cite{HatamiMolloy}.

Recommendations

• Critical window for the configuration model: finite third moment degrees
• Largest component of subcritical random graphs with given degree sequence
• Anatomy of the giant component: the strictly supercritical regime
• Heavy-tailed configuration models at criticality
• The asymptotic variance of the giant component of configuration model random graphs

Cites work

• A critical point for random graphs with a given degree sequence
• A new approach to the giant component problem
• An old approach to the giant component problem
• Asymptotic equivalence and contiguity of some random graphs
• Asymptotic normality of the \(k\)-core in random graphs
• Asymptotic rates of growth of the extinction probability of a mutant gene
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Component behavior near the critical point of the random graph process
• Connected components in random graphs with given expected degree sequences
• Counting connected graphs inside-out
• Critical window for the configuration model: finite third moment degrees
• Generating simple random graphs with prescribed degree distribution
• Graphs with specified degree distributions, simple epidemics, and local vaccination strategies
• How to determine if a random graph with a fixed degree sequence has a giant component
• scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• scientific article; zbMATH DE number 2006037 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3283243 (Why is no real title available?)
• Near-critical SIR epidemic on a random graph with given degrees
• Novel scaling limits for critical inhomogeneous random graphs
• On a conditionally Poissonian graph process
• On percolation in random graphs with given vertex degrees
• On the survival probability of a slightly advantageous mutant gene with a general distribution of progeny size. A branching process model
• Orthogonal decompositions and functional limit theorems for random graph statistics
• Paths in graphs
• Percolation on sparse random graphs with given degree sequence
• Probability: a graduate course
• Random graphs and complex networks. Volume 1
• Rates of decay for the survival probability of a mutant gene
• Scaling limits for critical inhomogeneous random graphs with finite third moments
• The Average Distance in a Random Graph with Given Expected Degrees
• The average distances in random graphs with given expected degrees
• The birth of the giant component
• The component sizes of a critical random graph with given degree sequence
• The Critical Phase for Random Graphs with a Given Degree Sequence
• The Evolution of Random Graphs
• The phase transition in inhomogeneous random graphs
• The probability that a random multigraph is simple
• The probability that a random multigraph is simple. II
• The scaling window for a random graph with a given degree sequence
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• The Structure of a Random Graph at the Point of the Phase Transition
• The Volume of the Giant Component of a Random Graph with Given Expected Degrees
• Universality for first passage percolation on sparse random graphs

Cited in

(12)

• The asymptotic variance of the giant component of configuration model random graphs
• Universality for critical heavy-tailed network models: metric structure of maximal components
• Heavy-tailed configuration models at criticality
• Preferential attachment without vertex growth: emergence of the giant component
• Anatomy of the giant component: the strictly supercritical regime
• Critical percolation on scale-free random graphs: new universality class for the configuration model
• Random graphs with given vertex degrees and switchings
• Critical window for the configuration model: finite third moment degrees
• A probabilistic approach to the leader problem in random graphs
• Largest component of subcritical random graphs with given degree sequence
• scientific article; zbMATH DE number 7731163 (Why is no real title available?)
• Barely supercritical percolation on Poissonian scale-free networks

This page was built for publication: Component structure of the configuration model: barely supercritical case

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