Contagious sets in random graphs

DOI10.1214/16-AAP1254MaRDI QIDQ1688015zbMATH OpenFDO

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, https://projecteuclid.org/euclid.aoap/1509696032

zbMATH Keywords

bootstrap percolationcontagious setsminimum contagious setrandom graphs

Mathematics Subject Classification ID

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

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

Review text

The authors consider the classical bootstrap percolation process on a binomial random graph \(G(n,p)\). A set of vertices is called contagious, if the bootstrap process percolates when this set is the set of initially active vertices. The authors of this paper consider the typical size of a smallest percolating set in a \(G(n,p)\) random graph. Expressing \(p=d/n\), they give the typical order of magnitude of a smallest contagious set in \(G(n,d/n)\), for \(d\gg 1\) but \(d\) growing at most like a polynomial of order \(n^{(r-1)/r}\) (together with some logarithmic factors), where \(r\) is the activation parameter of the bootstrap process. They also consider the question about when this minimum size of a contagious set could be equal to \(r\), that is, there exists a set of only \(r\) vertices such that if only these are active in the beginning of the process, then it percolates. They give the critical function \(p^\ast=p^\ast(n)\) (up to multiplicative constants) such that when \(p \gg p^\ast\), then such a set of size \(r\) exists, but when \(p\ll p^\ast\), it does not.

Recommendations

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

Cited in

(22)

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

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)