Effective approach to epidemic containment using link equations in complex networks

Abstract

Epidemic containment is a major concern when confronting large-scale infections in complex networks. Many studies have been devoted to analytically understand how to restructure the network to minimize the impact of major outbreaks of infections at large scale. In many cases, the strategies are based on isolating certain nodes, while less attention has been paid to interventions on the links. In epidemic spreading, links inform about the probability of carrying the contagion of the disease from infected to susceptible individuals. Note that these states depend on the full structure of the network, and its determination is not straightforward from the knowledge of nodes' states. Here, we confront this challenge and propose a set of discrete-time governing equations that can be closed and analyzed, assessing the contribution of links to spreading processes in complex networks. Our approach allows a scheme for the containment of epidemics based on deactivating the most important links in transmitting the disease. The model is validated in synthetic and real networks, yielding an accurate determination of epidemic incidence and critical thresholds. Epidemic containment based on link deactivation promises to be an effective tool to maintain functionality of networks while controlling the spread of diseases, such as disease spread through air transportation networks.

Fig. 1. Incidence of the epidemic process ρ as a function of the infection probability β.

We show the incidence level for the ELE model (solid lines) and for Monte Carlo (MC) simulations (circles). The theoretical epidemic threshold calculated using Eq. 19 is marked with a vertical line. We have made use of two synthetic and two real networks: two scale-free networks (top) with an exponent of 3, one of them with high clustering coefficient; the world air transportation network; and the network of scientific collaborations in the field of general relativity (GR). We have set the recovery rate for all the networks to μ = 0.5 (see Methods for the description of the networks and the details of the MC simulations).

Fig. 2. Targeted bond percolation.

We show the incidence of the epidemics, (ρ), and the number of connected components, (C_r), as functions of the occupation probability, (L_r/L₀), where L₀ is the number of links of the network and L_r is the number of removed edges in the bond percolation process. We compare five different epidemic containment strategies: removing the edges of the node with the highest probability of being infected, P(σ_i = I) (orange dash-dash lines); a random edge removal (yellow dash-dot lines); removing the edge with the highest edge betweenness (light orange dotted lines); targeting the edge with the highest eigenscore (red dashed line); and, last, removing the edge that has the largest link epidemic importance (blue solid line). We apply these processes to the same networks as in Fig. 1 (see Methods). We have set the recovery rate to μ = 0.5 and have chosen the infection probability β such that the stationary incidence of the epidemics is about ρ_ini ≈ 0.2 for all the networks, that is, β = 0.1 for both power-law networks, β = 0.06 for air transportation network, and β = 0.11 for the collaboration network. The dots mark the achievement of total containment.

Fig. 3. Epidemic containment on the air transportation network.

We show the networks after 33.3% of the links have been removed using link epidemic importance (top) and edge betweenness (bottom). Nodes and edges with the same color belong to the same connected component, with subcritical components in gray scale and using darker gray for larger components. The area of the nodes is proportional to their probability of being infected P(σ_i = I) from 0.0 to 0.6. We have set the epidemic probabilities to μ = 0.5 and β = 0.06.

Fig. 4. Fraction of links removed for total epidemic containment on synthetic networks.

We show the fraction of links that have to be removed to obtain total epidemic containment using link epidemic importance, compared with the fractions for the other four strategies: (A) eigenscore, (B) edge betweenness, (C) node infectivity, and (D) random removal. Each point represents a configuration consisting of a network and a set of epidemic parameters. The networks have been generated with the model in (48), which interpolates between ER (α = 1) and BA networks (α = 0). We use four values of the interpolating parameter: α = 0.0, 0.33, 0.67, and 1.0. These networks are generated in four sizes (N = 1000, 2500, 5000, and 10, 000) and three average degrees (〈k〉 = 4, 8, and 16), thus amounting to 48 different networks. For each network, we apply the five containment strategies for three different values of the recovery probability (μ = 0.25, 0.50, and 0.75) and four values of the infection probability β selected such that, before removing links, the incidence of the epidemics at the stationary state is equal to ρ_ini = 0.05, 0.1, 0.2, and 0.4. Therefore, each plot contains 576 different configurations.

Fig. 5. Fraction of links removed for total epidemic containment on real networks.

We compare the link epidemic importance and eigenscore methods on a set of 27 real networks selected from the Network Repository (49) (see Methods), with sizes ranging from 410 to 404,719 nodes. The epidemic parameters are the same as in Fig. 4, thus amounting to 324 different configurations.