Research ArticleNETWORK SCIENCE

Effective approach to epidemic containment using link equations in complex networks

See allHide authors and affiliations

Science Advances  05 Dec 2018:
Vol. 4, no. 12, eaau4212
DOI: 10.1126/sciadv.aau4212
  • 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, (Cr), as functions of the occupation probability, (Lr/L0), where L0 is the number of links of the network and Lr 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, Pi = 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 Pi = 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.

Supplementary Materials

  • Supplementary material for this article is available at http://advances.sciencemag.org/cgi/content/full/4/12/eaau4212/DC1

    Section S1. Link epidemic importance and connected components

    Section S2. Linearization of the ELE model

    Section S3. Epidemic threshold

    Section S4. Data description

    Fig. S1. Ratio between the link epidemic importance IA of a link in a subnetwork A and the link epidemic importance IAB of a link that acts as the only bridge between subnetworks A and B.

    Fig. S2. Epidemic containment for a network with 5000 nodes, power-law degree distribution of exponent 3, and average degree 〈k〉 = 6.

    Fig. S3. Epidemic containment for a network with 5000 nodes, power-law degree distribution of exponent 3, high clustering coefficient, and average degree 〈k〉 = 6.

    Fig. S4. Epidemic containment for the air transportation network.

    Fig. S5. Epidemic containment for the general relativity collaborations network.

    Fig. S6. Epidemic containment for an ER network with 5000 nodes and average degree 〈k〉 = 6.

    Fig. S7. Epidemic containment for a network with 5000 nodes generated with a stochastic block model, with four blocks of 250 nodes, two blocks of 1000 nodes, and one block of 2000 nodes, average degree of 5, and mixing probability of 0.3.

    Fig. S8. Epidemic containment for a network with 5000 nodes generated using the LFR algorithm, with average degree of 6, exponent of 3, and mixing probability of 0.1.

    Fig. S9. Original air transportation network (top) and the results after a removal of 33.3% of the links using link epidemic importance (middle) and edge betweenness (bottom).

    Fig. S10. Comparison of the number of connected components after total containment between the link epidemic importance strategy and the other four methods, calculated for the synthetic networks and parameters as in Fig. 4.

    Fig. S11. Comparison of the number of connected components after total containment between the link epidemic importance and eigenscore strategies, calculated for the real networks and parameters as in Fig. 5.

    Fig. S12. Graphical representation of the determination of the epidemic threshold.

    Fig. S13. Computational time invested for each method to perform a single ranking and removal for BA networks ranging from 100 to 400,000 nodes, averaged over 36 repetitions.

    Table S1. Structural characteristics of the 27 real networks obtained from the Network Repository (http://networkrepository.com) and used in Fig. 6 and fig. S11.

    Data file S1. Air transportation network data.

  • Supplementary Materials

    The PDF file includes:

    • Section S1. Link epidemic importance and connected components
    • Section S2. Linearization of the ELE model
    • Section S3. Epidemic threshold
    • Section S4. Data description
    • Fig. S1. Ratio between the link epidemic importance IA of a link in a subnetwork A and the link epidemic importance IAB of a link that acts as the only bridge between subnetworks A and B.
    • Fig. S2. Epidemic containment for a network with 5000 nodes, power-law degree distribution of exponent 3, and average degree 〈k〉 = 6.
    • Fig. S3. Epidemic containment for a network with 5000 nodes, power-law degree distribution of exponent 3, high clustering coefficient, and average degree 〈k〉 = 6.
    • Fig. S4. Epidemic containment for the air transportation network.
    • Fig. S5. Epidemic containment for the general relativity collaborations network.
    • Fig. S6. Epidemic containment for an ER network with 5000 nodes and average degree 〈k〉 = 6.
    • Fig. S7. Epidemic containment for a network with 5000 nodes generated with a stochastic block model, with four blocks of 250 nodes, two blocks of 1000 nodes, and one block of 2000 nodes, average degree of 5, and mixing probability of 0.3.
    • Fig. S8. Epidemic containment for a network with 5000 nodes generated using the LFR algorithm, with average degree of 6, exponent of 3, and mixing probability of 0.1.
    • Fig. S9. Original air transportation network (top) and the results after a removal of 33.3% of the links using link epidemic importance (middle) and edge betweenness (bottom).
    • Fig. S10. Comparison of the number of connected components after total containment between the link epidemic importance strategy and the other four methods, calculated for the synthetic networks and parameters as in Fig. 4.
    • Fig. S11. Comparison of the number of connected components after total containment between the link epidemic importance and eigenscore strategies, calculated for the real networks and parameters as in Fig. 5.
    • Fig. S12. Graphical representation of the determination of the epidemic threshold.
    • Fig. S13. Computational time invested for each method to perform a single ranking and removal for BA networks ranging from 100 to 400,000 nodes, averaged over 36 repetitions.
    • Table S1. Structural characteristics of the 27 real networks obtained from the Network Repository ( http://networkrepository.com) and used in Fig. 6 and fig. S11.

    Download PDF

    Other Supplementary Material for this manuscript includes the following:

    • Data file S1 (.graphml format). Air transportation network data.

    Files in this Data Supplement:

Stay Connected to Science Advances


Editor's Blog

Navigate This Article