Percolation on dense graph sequences

Abstract

In this paper we determine the percolation threshold for an arbitrary sequence of dense graphs $(G_n)$. Let ${\lambda }_n$ be the largest eigenvalue of the adjacency matrix of $G_n$, and let $G_n(p_n)$ be the random subgraph of $G_n$ obtained by keeping each edge independently with probability $p_n$. We show that the appearance of a giant component in $G_n(p_n)$ has a sharp threshold at $p_n=1/{\lambda }_n$. In fact, we prove much more: if $(G_n)$ converges to an irreducible limit, then the density of the largest component of $G_n(c/n)$ tends to the survival probability of a multi-type branching process defined in terms of this limit. Here the notions of convergence and limit are those of Borgs, Chayes, Lovász, Sós and Vesztergombi. In addition to using basic properties of convergence, we make heavy use of the methods of Bollobás, Janson and Riordan, who used multi-type branching processes to study the emergence of a giant component in a very broad family of sparse inhomogeneous random graphs.

Published in at http://dx.doi.org/10.1214/09-AOP478 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (4)

• The phase transition in inhomogeneous random graphs
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Percolation on finite graphs and isoperimetric inequalities
• The emergence of a giant component in random subgraphs of pseudo-random graphs

Cited by in corpus (36)

• Statistical physics of inference: Thresholds and algorithms
• Percolation on sparse networks
• Percolation in real interdependent networks
• Effect of the Interconnected Network Structure on the Epidemic Threshold
• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
• Predicting percolation thresholds in networks
• Spectra of random graphs with arbitrary expected degrees
• Tight lower bound for percolation threshold on a quasi-regular graph
• Beyond the locally tree-like approximation for percolation on real networks
• Looplessness in networks is linked to trophic coherence
• Spectra of networks containing short loops
• Spectra of random networks with arbitrary degrees
• Sparse random graphs with clustering
• Network connectivity during mergers and growth: optimizing the addition of a module
• Dynamic range maximization in excitable networks
• The cut metric, random graphs, and branching processes
• Spectral estimation of the percolation transition in clustered networks
• Connectedness in graph limits
• A geometric entropy detecting the Erdös-Rényi phase transition
• Cliques in dense inhomogeneous random graphs
• The local limit of the uniform spanning tree on dense graphs
• Assessing Percolation Threshold Based on High-Order Non-Backtracking Matrices
• Multiple structural transitions in interacting networks
• Large Very Dense Subgraphs in a Stream of Edges
• Duality in inhomogeneous random graphs, and the cut metric
• Critical Percolation on Random Networks with Prescribed Degrees
• Pandemic Spread in Communities via Random Graphs
• Numerical assessment of the percolation threshold using complement networks
• Random minimum spanning tree and dense graph limits
• Connectivity of inhomogeneous random graphs
• Maximizing the Smallest Eigenvalue of Grounded Laplacian Matrix
• K-core in percolated dense graph sequences
• Spectral bounds for percolation on directed and undirected graphs
• Scaling limits and universality: Critical percolation on weighted graphs converging to an $L^3$ graphon
• Edge sampling using network local information
• Percolation of a strongly connected component in simple directed random graphs with a given degree distribution