Takeover times for a simple model of network infection
arXiv:1702.00881 · doi:10.1103/PhysRevE.96.012313
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 does it take to completely infect a network of nodes, starting from a single infected node? An analogy to the classic "coupon collector" problem of probability theory reveals that the takeover time 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 , the takeover time 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 -dimensional lattices with (these distributions approach the sum of two Gumbels as 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.
arXiv comment19 pages, 10 figures
References in corpus (16)
- Epidemic processes in complex networks
- Random graphs with arbitrary degree distributions and their applications
- The spread of epidemic disease on networks
- Scaling and percolation in the small-world network model
- The power of a good idea: quantitative modeling of the spread of ideas from epidemiological models
- Evolutionary dynamics on degree-heterogeneous graphs
- Most undirected random graphs are amplifiers of selection for Birth-death dynamics, but suppressors of selection for death-Birth dynamics
- Counterintuitive properties of the fixation time in network-structured populations
- Exact numerical calculation of fixation probability and time on graphs
- Arrival Time Statistics in Global Disease Spread
- Interacting particle systems as stochastic social dynamics
- When the mean is not enough: Calculating fixation time distributions in birth-death processes
- Long paths in first passage percolation on the complete graph I. Local PWIT dynamics
- Weak disorder in the stochastic mean-field model of distance II
- Approximation Theorems Related to the Coupon Collector's Problem
- Long paths in first passage percolation on the complete graph II. Global branching dynamics
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