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 [Formula: see text] does it take to completely infect a network of [Formula: see text] nodes, starting from a single infected node? An analogy to the classic “coupon collector” problem of probability theory reveals that the takeover time [Formula: see text] 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 [Formula: see text] , the takeover time [Formula: see text] 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 [Formula: see text]-dimensional lattices with [Formula: see text] (these distributions approach the convolution of two Gumbel distributions as [Formula: see text] 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.