Immunization strategy based on the critical node in percolation transition. (English) Zbl 1349.92143
Summary: The problem of finding a better immunization strategy for controlling the spreading of the epidemic with limited resources has attracted much attention since its great theoretical significance and wide application. In this letter, we propose a novel and successful targeted immunization strategy based on percolation transition. Our strategy repeatedly looks for the critical nodes for immunizing. The critical node, which leads to the emergence of the giant connected component as the degree threshold increases, is determined when the maximal second-largest connected component disappears. To test the effectiveness of the proposed method, we conduct the experiments on several artificial networks and real-world networks. The results show that the proposed method outperforms the degree centrality strategy, the betweenness centrality strategy and the adaptive degree centrality strategy with 18% to 50% fewer immunized nodes for same amount of immunization.
References:
| [1] | Pastor-Satorras, R.; Vespignani, A., Epidemic spreading in scale-free networks, Phys. Rev. Lett., 86, 3200 (2001) |
| [2] | Saumell-Mendiola, A.; Serrano, M.Á.; Boguñá, M., Epidemic spreading on interconnected networks, Phys. Rev. E, 86, Article 026106 pp. (2012) |
| [3] | Zhou, J.; Xiao, G.; Cheong, S. A.; Fu, X.; Wong, L.; Ma, S.; Cheng, T. H., Epidemic reemergence in adaptive complex networks, Phys. Rev. E, 85, Article 036107 pp. (2012) |
| [4] | Buono, C.; Alvarez-Zuzek, L. G.; Macri, P. A.; Braunstein, L. A., Epidemics in partially overlapped multiplex networks, PLoS ONE, 9, Article e92200 pp. (2014) |
| [5] | Colizza, V.; Barrat, A.; Barthelemy, M.; Valleron, A.-J.; Vespignani, A., Modeling the worldwide spread of pandemic influenza: baseline case and containment interventions, PLoS Med., 4, 95-110 (2007) |
| [6] | Schneider, C. M.; Mihaljev, T.; Havlin, S.; Herrmann, H. J., Suppressing epidemics with a limited amount of immunization units, Phys. Rev. E, 84, Article 061911 pp. (2011) |
| [7] | Bauch, C. T.; Earn, D. J., Vaccination and the theory of games, Proc. Natl. Acad. Sci. USA, 101, 13391-13394 (2004) · Zbl 1064.91029 |
| [8] | Hébert-Dufresne, L.; Allard, A.; Young, J.-G.; Dubé, L. J., Global efficiency of local immunization on complex networks, Sci. Rep., 3, 2171 (2013) |
| [9] | Vespignani, A., Modelling dynamical processes in complex socio-technical systems, Nat. Phys., 8, 32-39 (2012) |
| [10] | Pastor-Satorras, R.; Vespignani, A., Immunization of complex networks, Phys. Rev. E, 65, Article 036104 pp. (2002) |
| [11] | Cohen, R.; Havlin, S.; Ben-Avraham, D., Efficient immunization strategies for computer networks and populations, Phys. Rev. Lett., 91, Article 247901 pp. (2003) |
| [12] | Gallos, L. K.; Liljeros, F.; Argyrakis, P.; Bunde, A.; Havlin, S., Improving immunization strategies, Phys. Rev. E, 75, Article 045104 pp. (2007) |
| [13] | Fu, X.; Small, M.; Walker, D. M.; Zhang, H., Epidemic dynamics on scale-free networks with piecewise linear infectivity and immunization, Phys. Rev. E, 77, Article 036113 pp. (2008) |
| [14] | Lü, L.; Zhang, Y.-C.; Yeung, C. H.; Zhou, T., Leaders in social networks, the delicious case, PLoS ONE, 6, Article e21202 pp. (2011) |
| [15] | Gong, K.; Tang, M.; Hui, P. M.; Zhang, H. F.; Younghae, D.; Lai, Y.-C., An efficient immunization strategy for community networks, PLoS ONE, 8, Article e83489 pp. (2013) |
| [16] | Wang, W.; Tang, M.; Zhang, H.-F.; Gao, H.; Do, Y.; Liu, Z.-H., Epidemic spreading on complex networks with general degree and weight distributions, Phys. Rev. E, 90, Article 042803 pp. (2014) |
| [17] | Chen, Y.; Paul, G.; Havlin, S.; Liljeros, F.; Stanley, H. E., Finding a better immunization strategy, Phys. Rev. Lett., 101, Article 058701 pp. (2008) |
| [18] | Holme, P.; Kim, B. J.; Yoon, C. N.; Han, S. K., Attack vulnerability of complex networks, Phys. Rev. E, 65, Article 056109 pp. (2002) |
| [19] | Gallos, L. K.; Cohen, R.; Argyrakis, P.; Bunde, A.; Havlin, S., Stability and topology of scale-free networks under attack and defense strategies, Phys. Rev. Lett., 94, Article 188701 pp. (2005) |
| [20] | Cohen, R.; Havlin, S., Complex Networks: Structure, Robustness and Function (2010), Cambridge University Press · Zbl 1196.05092 |
| [21] | Zhao, D.; Wang, L.; Li, S.; Wang, Z.; Wang, L.; Gao, B., Immunization of epidemics in multiplex networks, PLoS ONE, 9 (2014) |
| [22] | Buono, C.; Braunstein, L., Immunization strategy for epidemic spreading on multilayer networks, Europhys. Lett., 109, 26001 (2015) |
| [23] | Kawamoto, H.; Takayasu, H.; Jensen, H. J.; Takayasu, M., Precise calculation of a bond percolation transition and survival rates of nodes in a complex network, PLoS ONE, 10 (2015) |
| [24] | Li, D.; Fu, B.; Wang, Y.; Lu, G.; Berezin, Y.; Stanley, H. E.; Havlin, S., Percolation transition in dynamical traffic network with evolving critical bottlenecks, Proc. Natl. Acad. Sci. USA, 112, 669-672 (2015) |
| [25] | Zhao, J.-H.; Zhou, H.-J.; Liu, Y.-Y., Inducing effect on the percolation transition in complex networks, Nat. Commun., 4 (2013) |
| [26] | Colomer-de Simón, P.; Boguñá, M., Double percolation phase transition in clustered complex networks, Phys. Rev. X, 4, Article 041020 pp. (2014) |
| [27] | Erdős, P.; Rényi, A., On the evolution of random graphs, Magy. Tud. Akad. Mat. Kut. Intéz. Közl., 5, 17-61 (1960) · Zbl 0103.16301 |
| [28] | Erdős, P.; Rényi, A., On random graphs I, Publ. Math. (Debr.), 6, 290-297 (1959) · Zbl 0092.15705 |
| [29] | Barabási, A.-L.; Albert, R.; Jeong, H., Mean-field theory for scale-free random networks, Physica A, 272, 173-187 (1999) |
| [30] | Newman, M. J.E., Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E, 74, Article 036104 pp. (2006) |
| [31] | (2015) |
| [32] | Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139 |
| [33] | Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512 (1999) · Zbl 1226.05223 |
| [34] | (2015) |
| [35] | Boguñá, M.; Pastor-Satorras, R.; Díaz-Guilera, A.; Arenas, A., Models of social networks based on social distance attachment, Phys. Rev. E, 70, Article 056122 pp. (2004) |
| [36] | Duch, J.; Arenas, A., Community detection in complex networks using extremal optimization, Phys. Rev. E, 72, Article 027104 pp. (2005) |
| [37] | Lü, Z.; Huang, W., Iterated tabu search for identifying community structure in complex networks, Phys. Rev. E, 80, Article 026130 pp. (2009) |
| [38] | (2015) |
| [39] | Leskovec, J.; Kleinberg, J.; Faloutsos, C., Graph evolution: densification and shrinking diameters, ACM Trans. Knowl. Discov. Data, 1, 2 (2007) |
| [40] | (2015) |
| [41] | Klimt, B.; Yang, Y., Introducing the Enron corpus, (Proceedings of the CEAS 2004. Proceedings of the CEAS 2004, Mountain View, CA (2004)) · Zbl 1132.68562 |
| [42] | Leskovec, J.; Lang, K. J.; Dasgupta, A.; Mahoney, M. W., Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters, Internet Math., 6, 29-123 (2009) · Zbl 1205.91144 |
| [43] | (2015) |
| [44] | Newman, M. E.J., Spread of epidemic disease on networks, Phys. Rev. E, 66, Article 016128 pp. (2002) · Zbl 1001.68931 |
| [45] | Castellano, C.; Pastor-Satorras, R., Thresholds for epidemic spreading in networks, Phys. Rev. Lett., 105, Article 218701 pp. (2010) |
| [46] | Newman, M. E.J., Assortative mixing in networks, Phys. Rev. Lett., 89, Article 208701 pp. (2002) · Zbl 1001.68931 |
| [47] | Foster, D. V.; Foster, J. G.; Grassberger, P.; Paczuski, M., Clustering drives assortativity and community structure in ensembles of networks, Phys. Rev. E, 84, Article 066117 pp. (2011) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
