Contagious sets in expanders

DOI10.1137/1.9781611973730.131MaRDI QIDQ5363074zbMATH OpenOpenAlexFDO

Authors Amin Coja-Oghlan, Michael Krivelevich, Daniel Reichman, Uriel Feige

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Vertex degrees (05C07) Graph theory (05C99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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, where $r>1$ is the activation threshold. 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. Computing $m(G,r)$ is NP-hard. It is known that for every $d$-regular or nearly $d$-regular graph on $n$ vertices, $m(G,r)leO(fracnrd)$. We consider such graphs that additionally have expansion properties, parameterized by the spectral gap and/or the girth of the graphs. The general flavor of our results is that sufficiently strong expansion (e.g., $lambda(G)=O(sqrtd)$, or girth $Omega(loglogd)$) implies that $m(G,2)leO(fracn{d}^2)$ (and more generally, $m(G,r)leO(fracn{d}^{r/(r-1)})$). Significantly weaker expansion properties suffice in order to imply that $m(G,2)leO(fracnlogd{d}^2)$. For example, we show this for graphs of girth at least~7, and for graphs with $lambda(G)<(1-epsilon)d$, provided the graph has no 4-cycles. Nearly $d$-regular expander graphs can be obtained by considering the binomial random graph $G(n,p)$ with $psimeqfracdn$ and $d>logn$. For such graphs we prove that $Omega(fracn{d}^{2}logd)lem(G,2)leO(fracnloglogd{d}^{2}logd)$ almost surely. Our results are algorithmic, entailing simple and efficient algorithms for selecting contagious sets.

Recommendations

• Contagious sets in random graphs
• New bounds for contagious sets
• On the spread of influence in graphs

Cited in

(26)

• Discovering small target sets in social networks: a fast and effective algorithm
• Contagious sets in random graphs
• Active influence spreading in social networks
• On the spread of influence in graphs
• Large deviations for subcritical bootstrap percolation on the Erdős-Rényi graph
• Accelerated information dissemination on networks with local and global edges
• Minimum degree conditions for small percolating sets in bootstrap percolation
• Smallest percolating sets in bootstrap percolation on grids
• Fast and frugal targeting with incentives
• Opinion forming in Erdős-Rényi random graph and expanders
• Influence diffusion in social networks under time window constraints
• Spread of influence in weighted networks under time and budget constraints
• Minimal contagious sets in random regular graphs
• Latency-bounded target set selection in social networks
• Evangelism in social networks
• Optimizing spread of influence in social networks via partial incentives
• A fast and effective heuristic for discovering small target sets in social networks
• New bounds for contagious sets
• The Zero Forcing Number of Graphs
• Deterministic bootstrap percolation on trees
• Opinion Forming in Erdös-Rényi Random Graph and Expanders
• Fuzzification of Zero Forcing Process
• Groups burning: analyzing spreading processes in community-based networks
• Hierarchical cycle-tree packing model for optimal K-core attack
• Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation
• Graph burning in community-based networks

This page was built for publication: Contagious sets in expanders

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