Contagious sets in random graphs

DOI10.1214/16-AAP1254MaRDI QIDQ1688015zbMATHFDO

Authors Michael Krivelevich, Daniel Reichman, Uriel Feige

Publication date 4 January 2018

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

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

zbMATH Keywords

random graphsbootstrap percolationcontagious setsminimum contagious set

Mathematics Subject Classification ID

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

Abstract: We consider the following activation process in undirected graphs: a vertex is active either if it belongs to a set of initially activated vertices or if at some point it has at least $r$ active neighbors. A emph{contagious set} is a set whose activation results with the entire graph being active. Given a graph $G$, let $m(G,r)$ be the minimal size of a contagious set. We study this process on the binomial random graph $G:=G(n,p)$ with $p:=fracdn$ and $1lldllleft(fracnloglognlo{g}^{2}night{)}^{fracr-1r}$. Assuming $r>1$ to be a constant that does not depend on $n$, we prove that ${\displaystyle }$m(G,r) = Thetaleft(frac{n}{d^{frac{r}{r-1}}log d} ight),${\displaystyle }$ with high probability. We also show that the threshold probability for $m(G,r)=r$ to hold is $p^{\ast }=Thetaleft(frac1(nlo{g}^{r-1}n{)}^{1/r}ight)$.

Recommendations

• Contagious sets in expanders
• New bounds for contagious sets
• Sharp thresholds for contagious sets in random graphs

Cited in

(21)

• Stable sets of threshold-based cascades on the Erdős-Rényi random graphs
• Rumor spreading: A trigger for proliferation or fading away
• Bootstrap percolation with inhibition
• Dynamic monopolies in two-way bootstrap percolation
• Containing viral spread on sparse random graphs: bounds, algorithms, and experiments
• Smallest percolating sets in bootstrap percolation on grids
• Contagion in social networks: on contagion thresholds
• Deterministic bootstrap percolation on trees
• Sharp thresholds for contagious sets in random graphs
• Contagious sets in a degree-proportional bootstrap percolation process
• New ordering methods to construct contagious sets and induced degenerate subgraphs
• Minimal contagious sets in random regular graphs
• New bounds for contagious sets
• Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs
• Large deviations for subcritical bootstrap percolation on the Erdős-Rényi graph
• On the spread of influence in graphs
• Minimum degree conditions for small percolating sets in bootstrap percolation
• Bootstrap percolation on the stochastic block model
• The Maximum Label Propagation Algorithm on Sparse Random Graphs
• Contagious sets in expanders
• Threshold behavior of bootstrap percolation

This page was built for publication: Contagious sets in random graphs

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