Predicting the Speed of Epidemics Spreading in Networks

Global transport and communication networks enable information, ideas, and infectious diseases to now spread at speeds far beyond what has historically been possible. To effectively monitor, design, or intervene in such epidemic-like processes, there is a need to predict the speed of a particular contagion in a particular network, and to distinguish between nodes that are more likely to become infected sooner or later during an outbreak. Here, we study these quantities using a message-passing approach to derive simple and effective predictions that are validated against epidemic simulations on a variety of real-world networks with good agreement. In addition to individualized predictions for different nodes, we find an overall sudden transition from low density to almost full network saturation as the contagion progresses in time. Our theory is developed and explained in the setting of simple contagions on treelike networks, but we are also able to show how the method extends remarkably well to complex contagions and highly clustered networks.

Figure 1

Left panels: simulation of distribution of scaled time $T_i^n/n$ for an epidemic to reach distance $n$ from a source node $i$ chosen to have degree 1 (dark) or degree 3 (pale); as $n\to \infty$, these distributions will converge to delta functions at some value $\tau$. Right panel: simulation of $F_i^n(t)$ for time to reach distance $n$ from a source node $i$ chosen to have degree 1, showing convergence to a standard form with a fixed offset $\tau$. In both cases, node-to-node transmission times are standard exponentials and the network is an Erdős-Rényi graph with mean degree 3 on $N={10}^4$ nodes.

Figure 2

Predicted and observed values of spreading delay $\tau$ for a unit rate exponential infection spreading on a variety of social and communication networks [25, 26, 27, 28, 29, 30, 31, 32] with different percolation thresholds ${\rho }_c$. Predicted values (red circles) are calculated using Eq. (6). Observed values (blue dots) show the average over ${10}^3$ simulations with random source nodes. Stars show results for Watts-Strogatz random graphs on ${10}^4$ nodes with degree 30 and rewiring probabilities of 0.1, 0.5, and 1. Full details of all simulations are given in the Supplemental Material [18].

Figure 3

Simulated (blue marked line) and predicted (red dashed line) spreading delays $\tau$ for infections with Weibull delay times with varying shape parameters $\kappa$ and a fixed mean 1 (example delay distributions shown in insets). Simulations follow the same method as Fig. 2, averaged over 100 samples on an Erdős-Rényi graph of ${10}^4$ nodes and a mean degree 3.

Figure 4

Non-backtracking centrality predicts time to infection. Left: scatter plot of centrality and average arrival time for nodes in a selection of networks using a contagion with Weibull ($\kappa =10$) infection times. Right: results for simulations of complex contagions with threshold $\theta$ in an Erdős-Rényi graph with ${10}^4$ nodes and a mean degree of six. Key: (a) an interpersonal contact network in an American high school [32], (b) “Epinions” social media, (c) “Deezer” Romanian social network [25], (d) an Erdős-Rényi graph with $N={10}^5$ nodes, (e) $\theta =1$, (f) $\theta =2$, and (g) $\theta =3$.

Figure 5

Fractional size of the cluster of infected node as a function of time in various Erdős-Rényi graphs of different sizes $N$ and mean degree $c$, averaged over 100 simulations from random seed nodes, with standard exponential infection times. The left panel shows real time, and the right has rescaled time showing convergence to a step function in limit $N\to \infty$, implying “instantaneous” spread to the bulk of the network.