Percolation on random graphs with a fixed degree sequence

DOI10.1137/20M1347607MaRDI QIDQ5020830zbMATH OpenFDO

Authors Nikolaos Fountoulakis, Felix Joos, Guillem Perarnau

Publication date 7 January 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

bond percolationgiant componentpower lawrandom graphs with given degrees

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We consider bond percolation on random graphs with given degrees and bounded average degree. In particular, we consider the order of the largest component after the random deletion of the edges of such a random graph. We give a rough characterisation of those degree distributions for which bond percolation with high probability leaves a component of linear order, known usually as a giant component. We show that essentially the critical condition has to do with the tail of the degree distribution. Our proof makes use of recent technique introduced by Joos et al. [FOCS 2016, pp. 695--703], which is based on the switching method and avoids the use of the classic configuration model as well as the hypothesis of having a limiting object. Thus our results hold for sparse degree sequences without the usual restrictions that accompany the configuration model.

Recommendations

• Percolation on sparse random graphs with given degree sequence
• On percolation in random graphs with given vertex degrees
• Percolation in general graphs
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• The Critical Phase for Random Graphs with a Given Degree Sequence

Cites work

• A critical point for random graphs with a given degree sequence
• A new approach to the giant component problem
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A random graph model for massive graphs
• A randomized embedding algorithm for trees
• An old approach to the giant component problem
• Bootstrap percolation and the geometry of complex networks
• Complex networks: structure and dynamics
• Critical percolation on random regular graphs
• Edge percolation on a random regular graph of low degree
• Enumeration of Labelled Graphs I: 3-Connected Graphs
• Graph colouring and the probabilistic method
• How to determine if a random graph with a fixed degree sequence has a giant component
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• Nonuniversality of weighted random graphs with infinite variance degree
• On percolation in random graphs with given vertex degrees
• Percolation on sparse random graphs with given degree sequence
• Robustness and Vulnerability of Scale-Free Random Graphs
• Statistical mechanics of complex networks
• The asymptotic number of labeled graphs with given degree sequences
• The Critical Phase for Random Graphs with a Given Degree Sequence
• The giant component threshold for random regular graphs with edge faults H. Prodinger
• The phase transition in the configuration model
• 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 and Function of Complex Networks

Cited in

(18)

• On percolation in random graphs with given vertex degrees
• Percolation on dense graph sequences
• The threshold for jigsaw percolation on random graphs
• Critical percolation on scale-free random graphs: new universality class for the configuration model
• Compatible Sequences and a Slow Winkler Percolation
• Percolation and best-choice problem for powers of paths
• Jigsaw percolation on random hypergraphs
• Fixed price of groups and percolation
• Interference percolation
• Monotonicity of the probability of percolation for Bernoulli random fields on periodic graphs
• Percolation on Sparse Random Graphs with Given Degree Sequence
• Percolation on sparse random graphs with given degree sequence
• Absence of percolation in graphs based on stationary point processes with degrees bounded by two
• Percolation on dense random graphs with given degrees
• Percolation in invariant Poisson graphs with i.i.d. degrees
• Components, large and small, are as they should be. II: Supercritical percolation on regular graphs of constant degree
• Large induced subgraphs of random graphs with given degree sequences
• The disk-percolation model on graphs

This page was built for publication: Percolation on random graphs with a fixed degree sequence

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