Takeover times for a simple model of network infection

Abstract

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 for the star graph; as the sum of two Gumbels 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 sum of two Gumbels 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.

19 pages, 10 figures

References in corpus (3)

• Counterintuitive properties of the fixation time in network-structured populations
• Arrival Time Statistics in Global Disease Spread
• Approximation Theorems Related to the Coupon Collector's Problem

Cited by in corpus (8)

• Fitness dependence of the fixation-time distribution for evolutionary dynamics on graphs
• Fractal aggregation of active particles
• Two-level modeling of quarantine
• Asymptotic absorption-time distributions in extinction-prone Markov processes
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Dynamically accelerated cover times
• Telling apart <I>Felidae</I> and <I>Ursidae</I> from the distribution of nucleotides in mitochondrial DNA
• Universal statistics of incubation periods and other detection times via diffusion models