Bootstrap percolation on the random graph $G_{n,p}$

Abstract

Bootstrap percolation on the random graph $G_{n,p}$ is a process of spread of "activation" on a given realization of the graph with a given number of initially active nodes. At each step those vertices which have not been active but have at least $r\ge 2$ active neighbors become active as well. We study the size $A^{\ast }$ of the final active set. The parameters of the model are, besides $r$ (fixed) and $n$ (tending to $\infty$), the size $a=a(n)$ of the initially active set and the probability $p=p(n)$ of the edges in the graph. We show that the model exhibits a sharp phase transition: depending on the parameters of the model, the final size of activation with a high probability is either $n-o(n)$ or it is $o(n)$. We provide a complete description of the phase diagram on the space of the parameters of the model. In particular, we find the phase transition and compute the asymptotics (in probability) for $A^{\ast }$; we also prove a central limit theorem for $A^{\ast }$ in some ranges. Furthermore, we provide the asymptotics for the number of steps until the process stops.

Published in at http://dx.doi.org/10.1214/11-AAP822 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (8)

• Bootstrap percolation in three dimensions
• Nucleation and growth for the Ising model in $d$ dimensions at very low temperatures
• Probability asymptotics: notes on notation
• Sharp metastability threshold for an anisotropic bootstrap percolation model
• Graph bootstrap percolation
• A sharper threshold for bootstrap percolation in two dimensions
• Linear algebra and bootstrap percolation
• A d dimensional nucleation and growth model

Cited by in corpus (48)

• Recent advances in percolation theory and its applications
• Mean curvature, threshold dynamics, and phase field theory on finite graphs
• A message-passing approach for threshold models of behavior in networks
• Bootstrap percolation in inhomogeneous random graphs
• Minimal contagious sets in random regular graphs
• (Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs
• Robustness of Complex Networks with Implications for Consensus and Contagion
• Self-Organization of Dragon Kings
• Fake news and rumors: a trigger for proliferation or fading away
• Bootstrap percolation on geometric inhomogeneous random graphs
• Bootstrap percolation on a graph with random and local connections
• A modified bootstrap percolation on a random graph coupled with a lattice
• Thresholds for contagious sets in random graphs
• Bootstrap percolation on the Hamming torus
• A small-world search for quantum speedup: How small-world interactions can lead to improved quantum annealer designs
• Graph Matching with Partially-Correct Seeds
• Large deviations for subcritical bootstrap percolation on the random graph
• Kinetically Constrained Models with Random Constraints
• The time of bootstrap percolation for dense initial sets
• Bootstrap percolation in directed and inhomogeneous random graphs
• How Complex Contagions Spread Quickly in the Preferential Attachment Model and Other Time-Evolving Networks
• De-anonymizing scale-free social networks by percolation graph matching
• Significance of Side Information in the Graph Matching Problem
• An Improved Upper Bound for Bootstrap Percolation in All Dimensions
• SPECTRE: Seedless Network Alignment via Spectral Centralities
• The time of bootstrap percolation with dense initial sets for all thresholds
• Financial Contagion in a Generalized Stochastic Block Model
• Ore and Chvátal-type Degree Conditions for Bootstrap Percolation from Small Sets
• Metastable Behavior of Bootstrap Percolation on Galton-Watson Trees
• A sharper threshold for bootstrap percolation in two dimensions
• Bootstrap percolation in random $k$-uniform hypergraphs
• Time Scales of the Fredrickson-Andersen Model on Polluted ${\mathbb{Z}}^2$ and ${\mathbb{Z}}^3$
• A simple proof of almost percolation on G(n;p)
• Cascading Failures in Finite-Size Random Geometric Networks
• Bootstrap percolation on G(n,p) revisited
• Bootstrap percolation on Galton-Watson trees
• Deterministic bootstrap percolation in high dimensional grids
• Colouring random subgraphs
• Tight Bounds on the Minimum Size of a Dynamic Monopoly
• Percolating sets in bootstrap percolation on the Hamming graphs
• Bounds on Minimum Number of Anchors for Iterative Localization and its Connections to Bootstrap Percolation
• A large deviation approach to super-critical bootstrap percolation on the random graph $G_{n,p}$
• Bootstrap percolation in power-law random graphs
• Generalized threshold-based epidemics in random graphs: the power of extreme values
• A Note on Bootstrap Percolation Thresholds in Plane Tilings using Regular Polygons
• On connectivity, conductance and bootstrap percolation for a random k-out, age-biased graph
• Impact of Clustering on the Performance of Network De-anonymization
• Bootstrap percolation on the stochastic block model with k communities