Bootstrap percolation on the random graph G_n,p

DOI10.1214/11-AAP822zbMATH Open1254.05182arXiv1012.3535MaRDI QIDQ691111FDOQ691111

Authors: Svante Janson, Tomasz Łuczak, Thomas Vallier, Tatyana S. Turova 

Publication date: 29 November 2012

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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 $rgeq2$ 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.

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

Recommendations

• Bootstrap percolation on the random regular graph
• Bootstrap percolation on a graph with random and local connections
• Bootstrap percolation and diffusion in random graphs with given vertex degrees
• Bootstrap percolation on G(n,p) revisited
• Bootstrap percolation on the stochastic block model

zbMATH Keywords

random graphbootstrap percolationsharp threshold

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the asymptotic distribution of the size of a stochastic epidemic
• Asymptotic final-size distribution for some chain-binomial processes
• Threshold limit theorems for some epidemic processes
• Title not available (Why is that?)
• Probability: A Graduate Course
• Nucleation and growth for the Ising model in \(d\) dimensions at very low temperatures
• Sharp metastability threshold for an anisotropic bootstrap percolation model
• Phase transitions in the neuropercolation model of neural populations with mixed local and non-local interactions
• On the behavior of some cellular automata related to bootstrap percolation
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Finite size scaling in three-dimensional bootstrap percolation
• Stretched exponential fixation in stochastic Ising models at zero temperature
• The threshold regime of finite volume bootstrap percolation.
• Metastability effects in bootstrap percolation
• A sharper threshold for bootstrap percolation in two dimensions
• Bootstrap percolation in high dimensions
• The sharp threshold for bootstrap percolation in all dimensions
• Title not available (Why is that?)
• Zero-temperature Glauber dynamics on \({\mathbb{Z}^d}\)
• Bootstrap percolation on the hypercube
• Bootstrap percolation in three dimensions
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Majority Bootstrap Percolation on the Hypercube
• Remarks on bootstrap percolation in metric networks
• Orthogonal decompositions and functional limit theorems for random graph statistics
• Integrals, partitions, and cellular automata
• Random disease on the square grid
• Minimal percolating sets in bootstrap percolation
• Title not available (Why is that?)
• Bootstrap percolation on the random regular graph
• On percolation in random graphs with given vertex degrees
• Bootstrap percolation and diffusion in random graphs with given vertex degrees
• Linear algebra and bootstrap percolation
• A d-dimensional nucleation and growth model
• Symmetric sampling procedures, general epidemic processes and their threshold limit theorems
• Graph bootstrap percolation
• The final size of a nearly critical epidemic, and the first passage time of a Wiener process to a parabolic barrier
• An epidemic model with infector and exposure dependent severity
• An epidemic model with exposure-dependent severities

Cited In (78)

• Mean curvature, threshold dynamics, and phase field theory on finite graphs
• Structural phase transitions in neural networks
• New bounds for contagious sets
• Metastable behavior of bootstrap percolation on Galton-Watson trees
• Dynamic monopolies in two-way bootstrap percolation
• Best response dynamics on random graphs
• The time of bootstrap percolation with dense initial sets for all thresholds
• A large deviation approach to super-critical bootstrap percolation on the random graph \(G_{n, p}\)
• Title not available (Why is that?)
• Bootstrap percolation on random geometric graphs (extended abstract)
• A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs
• A modified bootstrap percolation on a random graph coupled with a lattice
• BOOTSTRAP PERCOLATION ON RANDOM GEOMETRIC GRAPHS
• Kinetically constrained models with random constraints
• On \(K_{2, t}\)-bootstrap percolation
• Bootstrap percolation and the geometry of complex networks
• The sharp threshold for making squares
• Bootstrap percolation in directed inhomogeneous random graphs
• Bootstrap percolation on homogeneous trees has 2 phase transitions
• A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs
• Sharp thresholds for contagious sets in random graphs
• Bootstrap percolation on a graph with random and local connections
• Bootstrap percolation in random \(k\)-uniform hypergraphs
• Inhomogeneous financial networks and contagious links
• The time of bootstrap percolation with dense initial sets
• The sharp threshold for bootstrap percolation in all dimensions
• Large deviations for subcritical bootstrap percolation on the Erdős-Rényi graph
• A sharper threshold for bootstrap percolation in two dimensions
• Bootstrap percolation on the stochastic block model
• \(K_{r,s}\) graph bootstrap percolation
• Bootstrap percolation on products of cycles and complete graphs
• Bootstrap percolation on the product of the two-dimensional lattice with a Hamming square
• Bootstrap percolation in living neural networks
• Rumor spreading: A trigger for proliferation or fading away
• Catastrophic event phenomena in communication networks: a survey
• Contagious sets in dense graphs
• Contagion risks and security investment in directed networks
• Deterministic bootstrap percolation on trees
• Bootstrap percolation and diffusion in random graphs with given vertex degrees
• On the spread of influence in graphs
• The sharp \(K_4\)-percolation threshold on the Erdős-Rényi random graph
• Bootstrap Percolation on Degenerate Graphs
• Polluted bootstrap percolation with threshold two in all dimensions
• Bootstrap percolation on the Hamming torus
• Triggering cascades on strongly connected directed graphs
• Bootstrap percolation on the random regular graph
• Minimal contagious sets in random regular graphs
• Managing Default Contagion in Inhomogeneous Financial Networks
• Majority bootstrap percolation on \(G(n,p)\)
• Mean field dynamics of stochastic cellular automata for random and small-world graphs
• Recent advances in percolation theory and its applications
• Bootstrap percolation in power-law random graphs
• A sharp threshold for bootstrap percolation in a random hypergraph
• Phase transition of the 2-choices dynamics on core-periphery networks
• Accelerated information dissemination on networks with local and global edges
• On the maximum running time in graph bootstrap percolation
• Threshold behavior of bootstrap percolation
• Financial contagion in a stochastic block model
• Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs
• Multiassociative memory: recurrent synapses increase storage capacity
• A note on bootstrap percolation thresholds in plane tilings using regular polygons
• Majority rule cellular automata
• Title not available (Why is that?)
• Polluted bootstrap percolation in three dimensions
• Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results
• Bootstrap percolation with inhibition
• Complex contagions on configuration model graphs with a power-law degree distribution
• Bootstrap percolation in random geometric graphs
• Transitive closure in a polluted environment
• Think globally, act locally: on the optimal seeding for nonsubmodular influence maximization
• Strong-majority bootstrap percolation on regular graphs with low dissemination threshold
• Byzantine-resilient distributed observers for LTI systems
• Strict majority bootstrap percolation in the \textit{r}-wheel
• A central limit theorem for diffusion in sparse random graphs
• New ordering methods to construct contagious sets and induced degenerate subgraphs
• An asynchronous linear-threshold innovation diffusion model
• Bootstrap percolation in inhomogeneous random graphs
• Universality for two‐dimensional critical cellular automata

This page was built for publication: Bootstrap percolation on the random graph \(G_{n,p}\)

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