Contact-Based Model for Epidemic Spreading on Temporal Networks

We present a contact-based model to study the spreading of epidemics by means of extending the dynamic message-passing approach to temporal networks. The shift in perspective from node- to edge-centric quantities enables accurate modeling of Markovian susceptible-infected-recovered outbreaks on time-varying trees, i.e., temporal networks with a loop-free underlying topology. On arbitrary graphs, the proposed contact-based model incorporates potential structural and temporal heterogeneities of the contact network and improves analytic estimations with respect to the individual-based (node-centric) approach at a low computational and conceptual cost. Within this new framework, we derive an analytical expression for the epidemic threshold on temporal networks and demonstrate the feasibility of this method on empirical data.

Popular Summary

The spread of infection, information, computer malware, or any contagionlike process is often described by disease models on complex networks with a time-varying topology. Recurrent, or flulike, spreading can be modeled accurately by taking an “individual-based” approach that focuses on nodes in a network. Here, we instead focus on the interactions—the links in a network—and present a contact-based model that accurately describes a second group of contagion processes: those that lead to permanent immunization. Taking this new perspective, we derive a criterion that separates local outbreaks from global epidemics, a crucial tool for risk assessment and control of, for instance, viral marketing.

To develop our model, we integrate time-varying network topologies into dynamic message passing, a widely used approach to describe unidirectional contagion processes. Based on this generalized model, we derive a spectral criterion for the stability of the disease-free solution, which determines the critical disease parameters. Through numerous numerical studies, we provide evidence that the contact-based perspective improves the individual-based approach. Finally, we investigate the epidemic risk based on the German cattle-trade network with over 180 000 nodes. Results from the individual-based and contact-based approaches deviate considerably, and thus justify this paradigmatic shift.

Our contact-based model is conceptually similar to those that focus on individuals, so we expect that numerous individual-based findings as well as results from networks with a static topology can be transferred in the future. These may include general epidemic models with a non-Poissonian transition process that go beyond the assumption of treelike topologies, stochastic effects, and temporal networks that evolve continuously in time.

Figure 1

Illustrative examples of a simulated epidemic outbreak from a single initially infected node. Colors give the probability that another arbitrarily selected node is in the susceptible (yellow), infected (red), or recovered (green) state, respectively. Simulation parameters: $\mu =2.85\times {10}^{-4}$, $\beta =100\mu$, $10^4$ MC realizations.

Figure 2

Epidemic trajectories for four exemplary individual nodes. We compare the cumulative infection probability from MC simulations (blue line) with estimations from the CB model (red dashed line) and the IB approach (green dotted line). Simulated results are averaged over $10^4$ MC realizations with the same outbreak location and disease parameters as in Fig. 1.

Figure 3

Left column: Time-resolved and normalized outbreak-size distributions for three different initially infected nodes. Epidemic parameters are as in Fig. 1 and $10^4$ MC realizations. The expectation value (blue line) assumes a cutoff at 20% of the population size (black dashed line). The CB and IB models are presented as a red dashed and green dotted line, respectively. Right column: Outbreak-size distribution at the final observation time in logarithmic scale with corresponding expectation values.

Figure 4

Distribution of final outbreak sizes as a function of the infection probability $\beta$. We perform $10^5$ MC realizations for every value of $\beta$, each starting with one randomly chosen outbreak location. For $\beta >0.02$, we show the averaged final outbreak size (blue line) with a cutoff at 20% of the population size. Estimations from the CB and IB models are presented as red dashed and green dotted lines, respectively. Labeled arrows at the bottom mark infection probabilities that correspond to Figs. 5, respectively.

Figure 5

Distribution of final outbreak sizes for $\beta =0.003$, 0.01, 0.02, and 0.1, respectively. For $\beta =0.02$ and 0.1, we mark part of the distribution with outbreak sizes below the given threshold of 20% by a lighter color tone and neglect this contribution to the averaged value (blue vertical line). The expected outbreak size from MC simulations and the estimations from the CB and IB models are plotted as blue, red dashed, and green dotted vertical lines, respectively.

Figure 6

Estimation of the critical infection probability ${\beta }_{\text{crit}}$. (a) Outbreak-size distribution as in Fig. 4 for small values of $\beta$. The vertical blue, red dashed, and green dotted lines mark the critical value according to MC simulations (${\beta }_{\text{crit}}^{(\mathrm{MC})}$), the CB model (${\beta }_{\text{crit}}^{(\mathrm{CB})}$), and the IB approach (${\beta }_{\text{crit}}^{(\mathrm{IB})}$), respectively. (b) From the distribution in (a), we derive the coefficient of variation (blue line, left axis) and the mean outbreak size (grey dashed line, right axis).

Figure 7

(a) Cattle trade within Germany. Weighted edges correspond to directed trade relations within the year 2010, whereas the color indicates the accumulated number of traded animals. (b) Cattle trade within the federal states of Germany. We confine the underlying time-aggregated graph to the GSCC and visualize here only edges with a flux of at least 50 animals.

Figure 8

Detailed threshold analysis for six selected federal states with $\mu =1/28$ (cf. Table 1). We show the simulated mean outbreak size (grey line, right axis) and coefficient of variation (blue line, left axis) averaged over all initially infected nodes. The critical infection probability from MC simulations are shown, and the IB and CB models are presented as vertical blue, green dotted, and red dashed lines, respectively.

Figure 9

(a) Spatial variation of epidemic risk due to cattle trade in Germany for $\mu =1/28$. Federal states are colored according to the critical infection probability ${\beta }_{\text{crit}}$ as determined from MC simulations, the CB and IB models, respectively (see Figs. 8 and 19 for details). The city states Berlin (B), Hamburg (HH), and Bremen (HB), as well as Saarland (SL), are excluded due to the small network size (see Table 1). (b) Critical infection probability ${\beta }_{\text{crit}}$ in logarithmic scale, sorted from high (left) to low risk (right). Results from MC simulations, and the CB and IB models are presented as groups of blue, red, and green bars, respectively. Disclaimer: A realistic vulnerability analysis requires, for instance, heterogeneous recovery probabilities and complex countermeasures (see Appendix pp2 for details).

Figure 10

Degree and weight analysis of cattle trade in the year 2010. Trade data are aggregated from 2010-01-01 to 2010-12-31. (a) Visualization of edges using geolocation with at least 50 animals traded along each link. The color and edge width indicate the aggregated edge weight. (b) Complementary cumulative distribution function (CCDF) of in, out, and total degree. (c) CCDF of the edge-weight distribution.

Figure 11

Node strength and flux analysis of cattle trade in the year 2010. (a) Geographic location of all 183 454 premises that have been recorded. (b) Color indicates net animal flux, i.e., the difference between in- and out-directed animal flux. Node size corresponds to the sum of both [see diagram (c)]. (c) Color and size indicate the total node strength, i.e., the sum of incoming and outgoing animals. (d) CCDF of the in, out, and total strength.

Figure 12

Temporal analysis cattle trade in the year 2010. (a) Number of premises that trade at least once on a given day. (b) Interevent time distribution, i.e., the interval between subsequent trade events of an arbitrary farm. Vertical lines indicate 7, 14, and 21 days.

Figure 13

Error estimation after restricting trade to the federal states. (a) Intrastate trade in terms of trade volume relative to total trade as red bars. Yellow bars on the top indicate the fraction of incoming animals. All bars together sum up to 100%. (b) Sum of internal and incoming trade volume normalized for each federal state. See Table 1 for a list of states and their abbreviations.

Figure 14

(a) Comparison between simulated and estimated mean infection arrival times. We extend the data set periodically in time until the outbreak dies out. The discrete derivative of the cumulative infection probabilities (see Fig. 2) yields the infection arrival probabilities of which we take the average value for every node. Results according to the CB and IB models are visualized as red circles and green crosses, respectively. The epidemic starts from the same outbreak origin and disease parameters as in Fig. 1. (b) Histogram over the relative deviation from the simulated infection arrival times. The numerical values are averaged over $10^5$ realizations.

Figure 15

(a) Comparison between simulated and estimated vulnerability. We compute the cumulative infection probability in the limit $t\to \infty$, also denoted as vulnerability. The comparison with CB and IB estimations is visualized by red circles and green crosses, respectively. Each value corresponds to the vulnerability of a node given the same outbreak location and disease parameters as in Fig. 1. (b) Relative deviation of the estimated values with respect to MC simulations. The numerical values are averaged over $10^5$ realizations.

Figure 16

Cumulative infection probability with a large fraction of initially infected nodes for three different values of $\beta$ and the same outbreak location as in Fig. 3. Left column [panels (a1)–(c1)]: Time-evolving distribution (linear scale) of cumulatively infected individuals for infection probabilities $\beta =0.01$, 0.02, and 0.1, respectively. We average over outbreak locations with 20% of the network initially infected at random. The mean outbreak size (blue line), averaged over $10^5$ realizations and with a standard deviation below ${10}^{-4}$, can thus be compared to the CB and IB models (red dashed and green dotted lines, respectively) with no threshold applied. Right column [panels (a2)–(c2)]: Final distribution (logarithmic scale) together with the averaged values.

Figure 17

Vulnerability as a function of the infection probability $\beta$ estimated from the CB model. Each curve represents the vulnerability of a node, i.e., the probability to contract the infection from a set of randomly chosen outbreak locations. Here, we estimate the vulnerability according to the CB model. Starting from an initial infection probability of $1-z=0.2$, we propagate the infection over time until convergence. We stop when the largest increase in vulnerability after 24 h falls below ${10}^{-3}$. The colors indicate the degree of each node in the underlying time-aggregated graph. Moreover, the behavior of one selected node is highlighted.

Figure 18

Comparison between MC simulations and the mean-field models for different values of $\mu$. Every row assumes a fixed recovery probability $\mu$ with decreasing values from top to bottom: $\mu =4.63\times {10}^{-4}$, $\mu =3.47\times {10}^{-4}$, $\mu =2.78\times {10}^{-4}$, $\mu =2.31\times {10}^{-4}$, and $\mu =1.16\times {10}^{-4}$. These values correspond to an expected infection period of 12, 16, 20, 24, and 48 h. The left column, middle column, and right column correspond to Figs. 4, 6, and 6, respectively, of the main text.

Figure 19

Detailed analysis of the epidemic threshold for the cattle-trade network with $\mu =1/28$. The central black line separates the figure into two panels. Every row (in a panel) provides results for a single federal state in Germany, excluding the city states Berlin, Bremen, and Hamburg. Left column: Outbreak-size distribution as a function of the infection probability $\beta$. Vertical blue, red, and green lines mark the critical infection probability according to MC simulations, and the CB and IB models, respectively. Middle column: Coefficient of variation $c_v$ (blue line, left axis), mean outbreak size (green dashed line, right axis). Right column: Selected values of $c_v$ for infection probabilities close to the critical value. The quadratic fit (green line) estimates the maximum and hence ${\beta }_{\text{crit}}$.

Figure 20

Detailed analysis of the epidemic threshold for the cattle-trade network with $\mu =1/120$. The analysis is akin to Fig. 19.

Figure 21

(a) Spatial variation of epidemic risk for $\mu =1/120$. The critical infection probability ${\beta }_{\text{crit}}$ determines the color of the federal states (see Fig. 20 for details). The visualization is akin to Fig. 9 of the main text.