Zombie outbreak on a $k$-regular graph

Suppose we have a zombie outbreak on a connected $k$-regular graph of order $n$. There are $n_0$ initially infected zombie nodes, and each turn, each zombie infects its neighbors with probability $p$. Let $z(t)$ denote the number of infected nodes on turn $t$.

1. What is the expected number of turns until zombies have taken over the world? (that is, until $z(t)=n$?)

2. Is it true that $z(t)\approx \dfrac{n}{1+(n-n_0)e^{-rt}}$? If so, what is $r$?

Solution 1:

Once $k>2$ the answer to #1 depends on the graph; even in the limiting determinstic case of $p=1$, and taking $n_0=1$, the expected time till full zombification can range from about $C \log n$ (for an expander graph) to at least $n/k$ (when $k$ is even, the node set is ${\bf Z}/n{\bf Z}$, and each node is joined to its $k$ nearest neighbors).

As to #2: for large $t$, the probability that there is still an uninfected node $-$ which is essentially the difference between $n$ and the expected value of $z(t)$ $-$ decays exponentially with $t$. The base of the exponent is $(1-p)^{b_{\min}}$, where $b_{\min}$ is the minimum number $b(S)$ of edges connecting $S$ and its complement, and $S$ ranges over all nonempty sets of nodes that are initially uninfected and might become the set of yet-uninfected nodes at some point. (This assumes of course that $n_0<n$: if $n_0=n$ then $z(t)=n$ for all $n$.) Usually $b=k$, realized by singleton sets; but $b$ can be smaller if the graph has a bottleneck, e.g. for this cubic graph

_{(source: harvard.edu)}

the base is $1-p$ as long as the zombies were initially on just one side of the graph.

To obtain the $(1-p)^{b_{\min}}$ formula, regard the outbreak as a dynamical system on the subsets $S$ of the set $S_0$ of initially uninfected nodes. At each $t$ the system's state is the set of nodes not yet infected by time $t$. The probability that $S$ goes to itself is $(1-p)^{b(S)}$, and otherwise $S$ goes to a proper subset. Thus the dynamical system is triangular (with respect to the partial order of set inclusion), with eigenvalues equal to the diagonal entries $(1-p)^{b(S)}$. The dominant eigenvalue of $1$ occurs only for $S=\emptyset$ because the graph is connected. The next eigenvalue is $(1-p)^{b_{\min}}$, and occurs for all nonempty $S$ minimizing $b(S)$; these are usually but not always the singletons in $S_0$. (Sometimes not every $S \subset S_0$ can be reached from $S_0$, but clearly at one singleton is reachable unless $n_0=n$.)