Containing Epidemic Outbreaks by Message-Passing Techniques

The problem of targeted network immunization can be defined as the one of finding a subset of nodes in a network to immunize or vaccinate in order to minimize a tradeoff between the cost of vaccination and the final (stationary) expected infection under a given epidemic model. Although computing the expected infection is a hard computational problem, simple and efficient mean-field approximations have been put forward in the literature in recent years. The optimization problem can be recast into a constrained one in which the constraints enforce local mean-field equations describing the average stationary state of the epidemic process. For a wide class of epidemic models, including the susceptible-infected-removed and the susceptible-infected-susceptible models, we define a message-passing approach to network immunization that allows us to study the statistical properties of epidemic outbreaks in the presence of immunized nodes as well as to find (nearly) optimal immunization sets for a given choice of parameters and costs. The algorithm scales linearly with the size of the graph, and it can be made efficient even on large networks. We compare its performance with topologically based heuristics, greedy methods, and simulated annealing on both random graphs and real-world networks.

Popular Summary

Viruses due to both malware and pathogens can incur severe economic losses. The reliance of societal and technological infrastructure on electronic data has prompted a new era in computational epidemiology against malware virus epidemics. While complete immunization is not always feasible or economically viable, network topology information and viral spreading dynamics can be used to design partial immunization strategies to effectively contain epidemic outbreaks. In this study, we examine targeted immunization as an optimization problem aimed at minimizing the trade-off between immunization costs and the expected number of infections.

Elementary immunization strategies are based on purely topological information, meaning that the most central nodes are chosen for vaccination. However, these techniques are generally far from optimal. We adopt a mean-field description of the stationary state of the epidemic process on networks, thus reducing the original optimization problem to an approximated one that can be computationally analyzed. The resulting algorithm, referred to as “message passing” because it relies on nodes communicating local information via messages, provides an efficient and decentralized method to find (nearly) optimal immunization sets for a given choice of parameters and costs.

Our message-passing method is extremely general and can be efficient even for large networks. As data archives continue to grow, efficient computational methods for immunization will become increasingly important for protecting epidemic outbreaks in social, technological, and financial networks.

Figure 1

Black circles represent the average density $f$ of nodes that have been infected by the final (infinite) time in the SIR dynamics on a random regular graph of $N={10}^3$ nodes and degree $K=4$, as a function of the transmission probability $p$ for $q=0.1$, 0.01, 0.001 (from left to right). The symmetric bars indicate the fluctuations around the average value computed on ${10}^4$ realizations of the stochastic process. The red solid line is computed from the solution of Eqs. (2) and (3).

Figure 2

Black circles represent the average density $f$ of infected nodes in the stationary state ($\tau ={10}^4$ steps) of the SIS dynamics on a random regular graph of $N={10}^3$ nodes and degree $K=4$, as a function of the transmission probability $p$ for $q$ between ${10}^{-1}$ and ${10}^{-4}$. The symmetric bars indicate the fluctuations around the average value computed on ${10}^4$ realizations of the stochastic process. The red dashed line is computed from the solution of Eq. (7).

Figure 3

Factor-graph representation of the BP equations for the optimal immunization problem in the SIR model. Variable nodes are of two types: One type includes pairs of auxiliary variables $\{(m_{ij},m_{ji})\}$; the other includes the immunization variables $\{s_i\}$. There is a factor node for each node $i$ of the original graph, including the energetic term ${\mathcal{E}}_i$ and all hard constraints $\{{\mathrm{\Psi }}_{i\ell }\}$ involving node $i$ as a first label.

Figure 4

Factor-graph representation of the BP equations for the optimal immunization problem in the SIS model. Variable nodes are of two types: One type includes pairs of auxiliary variables $\{(m_i,m_j)\}$; the other includes the immunization variables $\{s_i\}$. There is a factor node for each node $i$ of the original graph, including the energetic term ${\mathcal{E}}_i$ and the hard constraint ${\mathrm{\Psi }}_i$.

Figure 5

Results for the analysis of the SIR and SIS models on random regular graphs of degree $K=4$, with uniform self-infection probability $q=0.1$ and uniform transmission probability $p=0.5$. (a) For the SIR model, we plot the average density of nodes that got infected during the epidemic spreading $⟨f⟩$ as a function of the average density $⟨v⟩$ of immunized nodes. BP results on infinitely large graphs are reported for $\epsilon =0$ and $\beta =1$ (black solid line) and for $\epsilon =1$ and $\beta =1$ (red dashed line), 5 (green dot-dashed line), 10 (blue double-dot-dashed line), and 20 (violet dot-double-dashed line). Results of sampling over Eqs. (5a) and (5b) (orange circles), corresponding to random immunization, are also displayed. (b) For the SIS model, we plot the average density $⟨f⟩$ of infected nodes in the stationary state as a function of the average density $⟨v⟩$ of immunized nodes. BP results on infinitely large graphs are reported for $\epsilon =0$ and $\beta =1$ (black solid line) and for $\epsilon =1$ and $\beta =1$ (red dashed line), 5 (green dot-dashed line), 10 (blue double-dot-dashed line), and 20 (violet dot-double-dashed line). Results of sampling over Eq. (7) (orange circles), corresponding to random immunization, are also displayed.

Figure 6

Results for the analysis of the SIR and SIS models on random regular graphs of degree $K=4$, with uniform self-infection probability $q=0.1$. 0.01 and uniform transmission probability $p=0.5$. For the SIR model (a,b), we plot the average density of nodes that got infected during the epidemic spreading $⟨f⟩$ as a function of the average density $⟨v⟩$ of immunized nodes, both in the random case (open circles) and under optimization (full circles). For the SIS model (c,d), we plot the average density $⟨f⟩$ of infected nodes in the stationary state as a function of the average density $⟨v⟩$ of immunized nodes, both in the random case (open circles) and under optimization (full circles).

Figure 7

Distribution $P(m)$ of the probability $m$ that a node got infected during the SIR process on random regular graphs of degree $K=4$ for $⟨v⟩=0.05$, 0.2, 0.4, 0.6. Results are computed using BP by means of Eq. (17) (black solid line) on infinite networks, by sampling solutions of Eqs. (5a) and (5b) (red dashed lines) and by means of simulations of the stochastic dynamics, both on a finite network of $N={10}^3$ nodes and with a sample of ${10}^4$ immunization sets.

Figure 8

Distribution $P(m)$ of the probability $m$ that a node is infected in the stationary state of the SIS process on random regular graphs of degree $K=4$ for $⟨v⟩=0.1$, 0.4, 0.6, 0.8. Results are computed using BP by means of Eq. (32) (black solid line) on infinite networks, by sampling solutions of Eq. (7) (red dashed lines), and by means of simulations of the stochastic dynamics, both on a finite network of $N={10}^3$ nodes and with a sample of ${10}^4$ immunization sets.

Figure 9

(a) Distribution $P(m)$ of the probability $m$ that a node got infected during the SIR process on random regular graphs of degree $K=4$, $q=0.1$, $p=0.5$, $⟨v⟩=0.6$, and different values of $\beta$ and $\epsilon$. (b) Entropy of immunization sets of density $⟨v⟩=0.6$ as a function of $⟨f⟩$ (obtained by increasing $\beta$ for $\epsilon =1$).

Figure 10

(a) Distribution $P(m)$ of the probability $m$ that a node is infected in the stationary state of the SIS process on random regular graphs of degree $K=4$, $q=0.1$, $p=0.5$, $⟨v⟩=0.6$, and different values of $\beta$ and $\epsilon$. (b) Entropy of immunization sets of density $⟨v⟩=0.6$ as a function of $⟨f⟩$ (obtained by increasing $\beta$ for $\epsilon =1$).

Figure 11

Effects of the discretization of the BP marginals in the limit $q\to 0$. The curves represent the average density of nodes that got infected during the epidemic spreading $⟨f⟩$ as a function of the average density $⟨v⟩$ of immunized nodes for random immunization ($\epsilon =0$) in the SIR model on random regular graphs of degree $K=4$ and uniform transmission probability $p=0.5$. For $q=0$, a percolation-like phase transition is expected at $⟨v⟩\approx 1/3$. For low values of $N_B$, the BP equations (in the single-link approximation, in order to mimic an infinite graph) give a smooth crossover that approaches the correct threshold effect by increasing the number of bins.

Figure 12

Comparison between several immunization methods on a RRG with $N={10}^3$ nodes and degree $K=4$ for the SIR model (with $q=0.1$, $p=0.5$): (a) average fraction of infected nodes $⟨f⟩$ vs average fraction of immunized nodes $⟨v⟩$; (b) energy (for $\mu =1.0$) vs average fraction of immunized nodes $⟨v⟩$. Reported results include the following: Simulated annealing (red squares), eigenvectors centrality (blue solid line), degree centrality (green dot-dashed line), greedy (maroon dashed line), and the best obtained solving fixed-density BP equations (violet crosses) and MS (black vertical cross). Random immunization is also reported (black line for the BP results with $\epsilon =0$ and yellow circles for the results of direct stochastic simulations).

Figure 13

(a) Distribution $P(m)$ of the probability $m$ that a node got infected during the SIR process on random regular graphs of degree $K=4$, $q=0.1$, $p=0.5$, $⟨v⟩=0.6$, and different values of $\beta$ and $\epsilon$. (b) Entropy of immunization sets of density $⟨v⟩=0.363$ as a function of $⟨f⟩$ (obtained by increasing $\beta$ for $\epsilon =1$).

Figure 14

Comparison between several immunization methods for the SIR model on two synthetic networks of $N=1000$ nodes: (a) Erdös-Rényi random graph of average degree $z=10$ and parameters $q=0.1$, $p=0.5$, and $\mu =\epsilon =1.0$; (b) heterogeneous random graph with power-law degree distribution $P(k)\propto k^{-\gamma }$ with exponent $\gamma =2.2$ and parameters $q=0.1$, $p=0.9$, and $\epsilon =1$, $\mu =2$. The data represent the average energy as a function of the average fraction of immunized nodes $⟨v⟩$ for degree centrality (green line), eigenvector centrality (black dashed line), the greedy algorithm (blue dot-dashed line), and simulated annealing (red crosses). The black circles (with error bars) are the results obtained using the MS algorithm.

Figure 15

Comparison between several immunization methods for the SIR model on four real-world networks: (a) social network in a community of dolphins (parameters $q=0.1$, $p=0.5$, $\mu =0.3$, $\epsilon =1$), (b) network of characters of Les Misérables (parameters $q=0.1$, $p=0.5$, $\mu =0.2$, $\epsilon =1$), (c) the Sociopatterns contact network ($q=0.1$, $p=0.5$, $\mu =\epsilon =1$), (d) friendship network in a U.S. high school ($q=0.1$, $p=0.5$, $\mu =0.5$, $\epsilon =1$). The energy as a function of $⟨v⟩$ is shown, for immunization sets obtained using degree centrality (green line), eigenvector centrality (black dashed line), the greedy algorithm (blue dot-dashed line), and fixed-density simulated annealing (red vertical crosses). The optimal points found by Max-Sum are indicated by black crosses.

Figure 16

Energy as a function of $⟨v⟩$ for immunization sets obtained using degree (green triangles) and eigenvector centrality (black circles), the greedy algorithm (blue squares), and fixed-density simulated annealing (red crosses), for the SIR model ($p=0.5$) on Zachary’s karate club network of $N=34$ individuals. The MS results are indicated by black vertical crosses. The immunization cost was assumed to be half of the degree of a node.