Takeover times for a simple model of network infection

We study a stochastic model of infection spreading on a network. At each time step a node is chosen at random, along with one of its neighbors. If the node is infected and the neighbor is susceptible, the neighbor becomes infected. How many time steps $T$ does it take to completely infect a network of $N$ nodes, starting from a single infected node? An analogy to the classic “coupon collector” problem of probability theory reveals that the takeover time $T$ is dominated by extremal behavior, either when there are only a few infected nodes near the start of the process or a few susceptible nodes near the end. We show that for $N\gg 1$, the takeover time $T$ is distributed as a Gumbel distribution for the star graph, as the convolution of two Gumbel distributions for a complete graph and an Erdős-Rényi random graph, as a normal for a one-dimensional ring and a two-dimensional lattice, and as a family of intermediate skewed distributions for $d$-dimensional lattices with $d\ge 3$ (these distributions approach the convolution of two Gumbel distributions as $d$ approaches infinity). Connections to evolutionary dynamics, cancer, incubation periods of infectious diseases, first-passage percolation, and other spreading phenomena in biology and physics are discussed.

Figure 1

Simple model of infection spreading on a network. (a) A typical current state of the network. Solid dots represent infected nodes, and open dots represent susceptible nodes. Links represent potential interactions. (b) At each time step, a random node is selected. (c) One of the node's neighbors is also selected at random. The infection spreads only if the node chosen in (b) happens to be infected and its neighbor chosen in (c) happens to be susceptible, as is the case here; then the state of the network is updated accordingly as in (d). Otherwise, if the node is not infected or the neighbor is not susceptible, nothing happens and the state of the network remains unchanged. In that case the time step is wasted.

Figure 2

Distribution of takeover times for 1D lattices with $N=750$ nodes, obtained from $1\times {10}^6$ simulations. The mean takeover time is $\mu =N(N-1)$ and its variance is ${\sigma }^2=N{(N-1)}^2$, both found analytically. The simulation results are well approximated by a normal distribution, as expected. The diagram in the upper left schematically shows a 1D lattice.

Figure 3

Distribution of takeover times for a star graph with $N=120$ spoke nodes, obtained from $1\times {10}^6$ simulation runs. The mean $\mu$ and characteristic width $L$ are given by $\mu =(N+1)\left(N\right){\sum }_{m=1}^{N}1/m$ and $L=N(N+1)$. The numerically generated histogram of takeover times closely follows the predicted Gumbel distribution, even for the small $N$ used here. The schematic diagram in the upper left shows a star network.

Figure 4

Distribution of takeover times for a complete graph with $N=450$ nodes. The histogram is based on $1\times {10}^6$ simulation runs. The mean takeover time is $\mu ={\sum }_{m=1}^{N-1}1/p_m$ exactly. Here, the numerically generated distribution fits closely to the convolution of two Gumbel distributions, produced using $5\times {10}^6$ samples. The schematic diagram in the upper left shows a complete graph.

Figure 5

Snapshots of our infection dynamics on a two-dimensional (2D) periodic cubic lattice. Black pixels show infected nodes, and grey pixels show susceptible nodes. (a) Snapshot near the beginning of the dynamics and (b) snapshot near the end. Notice how the blob of infected nodes in the top panel has a fairly simple shape, and most of the susceptible nodes lie in a single cluster in the bottom panel.

Figure 6

Distribution of takeover times $T$ for a 3D lattice with a side length of $n=15$. The numerically generated distribution is based on $1\times {10}^6$ simulation runs. The solid line shows the distribution of $(F^{\prime }+F^{\prime })/\sqrt{2}$, with $F^{\prime }$ being summed up to $M=40$ and using $5\times {10}^6$ repetitions. The empirical quantities $\mu$ and ${\sigma }^2$ are the numerically calculated mean and variance of $T$. The schematic diagram in the upper left shows a 3D lattice.

Figure 7

Distribution of takeover times $T$ for a 2D lattice with a side length of $n=100$. The numerical results are obtained from $1.5\times {10}^5$ simulations. The solid line is the standard normal distribution. The empirical quantities $\mu$ and ${\sigma }^2$ are the numerically calculated mean and variance of $T$. The schematic diagram in the upper left shows a 2D lattice.

Figure 8

Distribution of takeover times $T$ for an Erdős-Rényi random graph on $N=600$ nodes with an edge probability of $\rho =0.5$. Simulation results were compiled from $1\times {10}^6$ runs, all using the same realization of the random graph and all with the initial infection starting at the same node. The solid line was generated numerically by adding $5\times {10}^6$ pairs of $\text{Gumbel}\left(-\gamma \sqrt{3}/\pi ,\sqrt{3}/\pi \right)$ random variables together. Similarly, $\mu$ and ${\sigma }^2$ are the numerically calculated mean and variance of $T$.

Figure 9

Normalized distribution of takeover times for an Erdős-Rényi random graph on $N=600$ nodes with an edge probability of $\rho =0.5$, obtained from $1\times {10}^6$ simulation runs. For the sake of convenience, each $T$ is rescaled to have a mean of zero and a variance of 1. (a) Normalized times required to infect 90% of the population, and (b) times for complete takeover. Here, the convolution of two Gumbel distributions plotted on the right was generated using $5\times {10}^6$ samples.

Figure 10

A properly chosen three-parameter lognormal distribution can closely approximate (a) a Gumbel distribution or (b) a convolution of two Gumbel distributions. The parameters in these lognormals were chosen to fit the first three moments of the Gumbel or Gumbel+Gumbel distributions.

Figure 11

Distribution of takeover times $T$ for a Barabasi-Albert scale-free network with a minimum degree of 3 and $N=75$ nodes. Simulation results were compiled from $1\times {10}^6$ runs, all using the same realization of the random graph and all with the initial infection starting at the same node. The solid line is the $\text{Gumbel}\left(-\gamma \sqrt{3}/\pi ,\sqrt{3}/\pi \right)$ distribution for reference. $\mu$ and ${\sigma }^2$ are the numerically calculated mean and variance of $T$.