Message-passing approach for recurrent-state epidemic models on networks

Epidemic processes are common out-of-equilibrium phenomena of broad interdisciplinary interest. Recently, dynamic message-passing (DMP) has been proposed as an efficient algorithm for simulating epidemic models on networks, and in particular for estimating the probability that a given node will become infectious at a particular time. To date, DMP has been applied exclusively to models with one-way state changes, as opposed to models like SIS and SIRS where nodes can return to previously inhabited states. Because many real-world epidemics can exhibit such recurrent dynamics, we propose a DMP algorithm for complex, recurrent epidemic models on networks. Our approach takes correlations between neighboring nodes into account while preventing causal signals from backtracking to their immediate source, and thus avoids “echo chamber effects” where a pair of adjacent nodes each amplify the probability that the other is infectious. We demonstrate that this approach well approximates results obtained from Monte Carlo simulation and that its accuracy is often superior to the pair approximation (which also takes second-order correlations into account). Moreover, our approach is more computationally efficient than the pair approximation, especially for complex epidemic models: the number of variables in our DMP approach grows as $2mk$ where $m$ is the number of edges and $k$ is the number of states, as opposed to $m{k}^2$ for the pair approximation. We suspect that the resulting reduction in computational effort, as well as the conceptual simplicity of DMP, will make it a useful tool in epidemic modeling, especially for high-dimensional inference tasks.

Figure 1

We define messages on the directed edges of a network to carry causal information of the flow of contagion; e.g., $I_{j\to i}$ is the probability that $j$ is infectious because it received the infection from a neighbor $k$ other than $i$. This prevents signals from immediately backtracking to the node they came from and thus prevents what we term “echo chamber” infections.

Figure 2

Two simple, yet illustrative, cases of networks, where the darker node is initially infectious. As we discuss, in these simple cases one can see the motivation for our approach to prevent infection signals from backtracking.

Figure 3

Results on the SIS model. On the left, the marginal probability that node 29 in Zachary's karate club (see inset on right) is infectious as a function of time. We compare the true marginal derived by ${10}^5$ independent Monte Carlo simulations with that estimated by $\mathrm{rDMP}$, the independent node approximation, and the pair approximation. In the inset, we show the fraction $f$ of infectious nodes as a function of time. On the right is the $L_1$ error, averaged over all nodes; we see that $\mathrm{rDMP}$ is the most accurate of the three methods. Here the transmission rate is $\lambda =0.1$, the waning rate is $\rho =0.05$, and vertex 0 (colored red) was initially infected.

Figure 4

A scatter plot of the steady-state marginals $I_i$ for the $n=33$ nodes in Zachary's karate club, with the same parameters as described in the caption of Fig. 3. The vertical axis is the true marginal computed by Monte Carlo simulations; the horizontal axis is the estimated marginals from $\mathrm{rDMP}$ (black $☆$) and the pair approximation (blue $\times$). Both methods overestimate the marginal, but $\mathrm{rDMP}$ is closer to the true value (the line $y=x$) for every node.

Figure 5

The difference between $L_1^{\mathrm{rDMP}}$ and $L_1^{\mathrm{pair}}$ on Zachary's karate club for various values of the ratio $\rho /\lambda$. We rescale time so that $\lambda =0.1$ as before. In the blue region, $L_1^{\mathrm{rDMP}}<L_1^{\mathrm{pair}}$ and $\mathrm{rDMP}$ is more accurate; in the red region, $L_1^{\mathrm{rDMP}}>L_1^{\mathrm{pair}}$. We see that $\mathrm{rDMP}$ is more accurate except at early times or when $\rho /\lambda$ is small.

Figure 6

On the left, we show the fraction $f$ of infectious nodes as a function of time in the SIS model on an Erdős-Rényi graph (inset) with $n=100$ and average degree 3. Here, $\lambda =0.4, \rho =0.1$, and the initial condition consists of a single infectious node (colored red). Monte Carlo results were averaged over ${10}^3$ independent runs. On the right is the same as the figure on the left, except we show the results from a larger but random geometric graph with ${10}^5$ nodes, where the average clustering coefficient is 0.6. Monte Carlo results here were averaged over 100 independent runs. Except at early times, $\mathrm{rDMP}$ tracks the true trajectory more closely.

Figure 7

The SIRS model on the karate club. On the left, we show the true and estimated marginal probability that a node 29 is infectious (main figure) or recovered (inset) as a function of time. On the right is the average $L_1$ error for the infectious and recovered (inset) states. The transmission rate is $\lambda =0.1$, and the transition rates from infectious to recovered and from recovered to susceptible are $\rho =0.05$ and $\gamma =0.2$, respectively. Node 0 (colored red) was initially infected. Monte Carlo results were averaged over ${10}^5$ runs. As for the SIS model, $\mathrm{rDMP}$ is significantly more accurate than the first-order model where nodes are independent and is more accurate than the pair approximation except at early times.

Figure 8

Same as described in the caption of Fig. 3, but with transmission rate $\lambda =0.1$ and waning rate $\rho =0.54$. A well-known upper bound on the epidemic threshold of the SIS model can be computed from the leading eigenvalue $A_1$ of the adjacency matrix (the Jacobian matrix of first-moment-closure approach) of a network. In other words, if $\frac{\rho }{\lambda }<A_1$, it is known from the first-moment-method that an infection-free state becomes unstable and epidemics become widespread and endemic. Here we show the results from SIS model in Zachary's karate club, where $A_1\approx 6.7$. Even though $\frac{\rho }{\lambda }=5.4<A_1$, which is well below the threshold from the first-moment method, the contagion fades away eventually, which is correctly captured by our DMP approach.