Contagious sets in random graphs

Uriel Feige, Michael Krivelevich, Daniel ReichmanThe Annals of Applied Probability 2017 · DOI · arXiv

This paper, titled "Contagious Sets in Random Graphs," by Uriel Feige, Michael Krivelevich, and Daniel Reichman, provides a rigorous mathematical analysis of how "contagion" spreads through a network. It specifically focuses on the minimum number of initial "seeds" required to eventually activate an entire random graph.

TL;DR

The authors determine the minimum size of a "contagious set"—the smallest group of nodes needed to trigger a full-graph cascade—in Erdős-Rényi random graphs. They prove that by strategically choosing seeds rather than picking them at random, one can trigger a total collapse of the network with significantly fewer nodes than previously thought possible.

What Problem Does This Paper Address?

The paper investigates bootstrap percolation, a process used to model everything from the spread of a virus or a rumor to the firing of neurons in the brain. In this model, a node becomes "active" if it is either an initial seed or if it has at least $r$ active neighbors.

While previous research focused on what happens when seeds are chosen randomly (e.g., "If 5% of people are randomly infected, will the whole population get sick?"), this paper asks a more fundamental combinatorial question: What is the absolute minimum number of seeds needed if we can choose them optimally? This is crucial for understanding the vulnerability of networks to targeted "attacks" or the efficiency of viral marketing campaigns.

Methods

The authors use probabilistic combinatorics to analyze the binomial random graph $G(n, p)$, where $n$ is the number of vertices and $p = d/n$ is the edge probability. Their primary tool is a novel iterative algorithm designed to find a small contagious set:

  1. Stage I (The Snowball): Start with a tiny set of seeds. In each step, look at the "external neighborhood" of the currently active nodes. Identify large connected components within the set of nodes that are just one neighbor away from becoming active (i.e., they have $r-1$ active neighbors). By adding just one seed to each of these components, the entire component "flips" to active.
  2. Stage II (The Tipping Point): Once the active set reaches a certain "critical mass," the authors leverage existing results in bootstrap percolation to show that the natural density of the random graph will take over and finish the activation process.
  3. Lower Bounds: To prove their results are tight, they use "first moment" probabilistic arguments to show that any set smaller than their calculated bound is highly unlikely to span enough edges to sustain a cascade.

Datasets

Not discussed in the paper. As a theoretical mathematics and computer science paper, it does not use empirical datasets. Instead, it performs proofs on the mathematical model of Erdős-Rényi random graphs ($G(n, p)$).

Key Insights and Ideas

  • Strategic vs. Random: The most striking insight is the power of choice. For many graph densities, the number of seeds needed to trigger a cascade is significantly smaller if you pick them carefully compared to picking them at random.
  • The Power of $r-1$: The "aha moment" in their algorithm is focusing on nodes that are almost active. By targeting connected clusters of nodes that only need one more active neighbor, a single well-placed seed can cause a massive chain reaction.
  • Threshold Behavior: The paper identifies a sharp "threshold probability." Below a certain edge density, you need many seeds; above it, a tiny constant number of seeds (just $r$) can infect the whole world.
  • Logarithmic Generations: They show that the contagion spreads very quickly—the entire graph becomes active in roughly $O(\log \log n)$ steps.

Key Results

The paper provides two main theorems for a constant threshold $r > 1$:

  1. Minimum Contagious Set Size: For a wide range of graph densities ($d$), the minimum size of a contagious set $m(G, r)$ is: $$m(G, r) = \Theta\left(\frac{n}{d^{\frac{r}{r-1}} \log d}\right)$$ This formula gives a precise scaling law for how many seeds you need as the graph gets denser.

  2. The $m(G, r) = r$ Threshold: They determine the exact point where the graph becomes so well-connected that the absolute minimum number of seeds (just $r$ nodes) is enough to trigger a full cascade. This happens when the edge probability $p$ reaches: $$p^* = \Theta\left(\frac{1}{(n \log^{r-1} n)^{1/r}}\right)$$

Limitations and Future Work

  • Specific Degree Ranges: The authors acknowledge they did not handle cases where the average degree $d$ is a very small constant or very large (approaching $n/\log n$). They suggest Theorem 1.1 likely extends to these ranges but requires different analytical "black boxes."
  • Tightness of Time Bounds: While they provide an upper bound on the number of "generations" (time steps) for the contagion to finish, they suspect their $O(\log d \log \log n)$ bound for the general case is not perfectly tight.
  • Non-Random Graphs: The study is limited to the $G(n, p)$ model. Real-world networks (like social media or power grids) often have "heavy-tailed" degree distributions or community structures that might change these results significantly.

Summary updated

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: = \frac{d}{n}$ and $1 \ll d \ll \left(\frac{n \log \log n}{\log^2 n}\right)^{\frac{r-1}{r}}$. Assuming $r > 1$ to be a constant that does not depend on $n$, we prove that $$m(G,r) = Θ\left(\frac{n}{d^{\frac{r}{r-1}}\log d}\right),$$ with high probability. We also show that the threshold probability for $m(G,r)=r$ to hold is $p^*=Θ\left(\frac{1}{(n \log^{r-1} n)^{1/r}}\right)$.
BibTeX
@article{feige2017contagious,
  author = {Uriel Feige and Michael Krivelevich and Daniel Reichman},
  title = {{Contagious sets in random graphs}},
  journal = {The Annals of Applied Probability},
  year = {2017},
  doi = {10.1214/16-aap1254},
}
Figure