The relative importance of structure and dynamics on node influence in reversible spreading processes

Abstract

The reversible spreading processes with repeated infection widely exist in nature and human society, such as gonorrhea propagation and meme spreading. Identifying influential spreaders is an important issue in the reversible spreading dynamics on complex networks, which has been given much attention. Except for structural centrality, the nodes’ dynamical states play a significant role in their spreading influence in the reversible spreading processes. By integrating the number of outgoing edges and infection risks of node’s neighbors into structural centrality, a new measure for identifying influential spreaders is articulated which considers the relative importance of structure and dynamics on node influence. The number of outgoing edges and infection risks of neighbors represent the positive effect of the local structural characteristic and the negative effect of the dynamical states of nodes in identifying influential spreaders, respectively. We find that an appropriate combination of these two characteristics can greatly improve the accuracy of the proposed measure in identifying the most influential spreaders. Notably, compared with the positive effect of the local structural characteristic, slightly weakening the negative effect of dynamical states of nodes can make the proposed measure play the best performance. Quantitatively understanding the relative importance of structure and dynamics on node influence provides a significant insight into identifying influential nodes in the reversible spreading processes.

Graphical abstract

Keywords

reversible spreading process / node influence / local structure / dynamical state

References

[1] D. Koschützki, K. A. Lehmann, L. Peeters, S. Richter, D. Tenfelde-Podehl, and O. Zlotowski,in: Network Analysis, Springer, 2005, pp 16–61

[2] L. Lü, D. Chen, X. Ren, Q. Zhang, Y. Zhang, and T. Zhou, Vital nodes identification in complex networks, Phys. Rep. 650, 1 (2016)

[3] S. Pei, J. Wang, F. Morone, and H. A. Makse, Influencer identification in dynamical complex systems, J. Complex Netw. 8(2), cnz029 (2020)

[4] J. Leskovec, L. A. Adamic, and B. A. Huberman, The dynamics of viral marketing, ACM Trans. Web 1(1), 5 (2007)

[5] A. Bovet and H. A. Makse, Influence of fake news in Twitter during the 2016 US presidential election, Nat. Commun. 10(1), 1 (2019)

[6] Y. T. Lin, X. P. Han, B. K. Chen, J. Zhou, and B. H. Wang, Evolution of innovative behaviors on scale-free networks, Front. Phys. 13(4), 130308 (2018)

[7] A. E. Motter and Y. Lai, Cascade-based attacks on complex networks, Phys. Rev. E 66(6), 065102 (2002)

[8] R. Albert, I. Albert, and G. L. Nakarado, Structural vulnerability of the North American power grid, Phys. Rev. E 69(2), 025103 (2004)

[9] R. Pastor-Satorras and A. Vespignani, Immunization of complex networks, Phys. Rev. E 65(3), 036104 (2002)

[10] S. V. Scarpino and G. Petri, On the predictability of infectious disease outbreaks,Nat. Commun . 10(1), 898 (2019)

[11] J. Zhou and Z. H. Liu, Epidemic spreading in complex networks, Front. Phys. 3(3), 331 (2008)

[12] F. Morone and H. A. Makse, Influence maximization in complex networks through optimal percolation, Nature 524(7563), 65 (2015)

[13] S. Pei, F. Morone, and H. A. Makse, in: Complex Spreading Phenomena in Social Systems, Springer, 2018, pp 125–148

[14] Y. Hu, S. Ji, Y. Jin, L. Feng, H. E. Stanley, and S. Havlin, Local structure can identify and quantify influential global spreaders in large scale social networks, Proc. Natl. Acad. Sci. USA 115(29), 7468 (2018)

[15] A. Y. Lokhov and D. Saad, Optimal deployment of resources for maximizing impact in spreading processes, Proc. Natl. Acad. Sci. USA 114(39), E8138 (2017)

[16] K. Zheng, Y. Liu, Y. Wang, and W. Wang, k-core percolation on interdependent and interconnected multiplex networks, arXiv: 2101.02335 (2021)

[17] G. Poux-Médard, R. Pastor-Satorras, and C. Castellano, Influential spreaders for recurrent epidemics on networks, Phys. Rev. Res.2(2), 023332 (2020)

[18] S. Erkol, D. Mazzilli, and F. Radicchi, Influence maximization on temporal networks, Phys. Rev. E 102(4), 042307 (2020)

[19] S. Aral and P. S. Dhillon, Social influence maximization under empirical influence models, Nat. Hum. Behav. 2(6), 375 (2018)

[20] K. Klemm, M. Á. Serrano, V. M. Eguíluz, and M. S. Miguel, A measure of individual role in collective dynamics, Sci. Rep. 2(1), 1 (2012)

[21] J. P. Gleeson, J. A. Ward, K. P. Osullivan, and W. T. Lee, Competition-induced criticality in a model of meme popularity, Phys. Rev. Lett. 112(4), 048701 (2014)

[22] R. Pastor-Satorras and A. Vespignani, Epidemic dynamics and endemic states in complex networks, Phys. Rev. E 63(6), 066117 (2001)

[23] S. K. Stavroglou, A. A. Pantelous, H. E. Stanley, and K. M. Zuev, Hidden interactions in financial markets, Proc. Natl. Acad. Sci. USA 116(22), 10646 (2019)

[24] B. Barzel and A. Barabási, Universality in network dynamics, Nat. Phys. 9(10), 673 (2013)

[25] R. Pastor-Satorras, and A. Vespignani, Epidemic Spreading in Scale-Free Networks, Phys. Rev. Lett. 86(14), 3200 (2001)

[26] R. Pastor-Satorras, and A. Vespignani, Epidemic dynamics and endemic states in complex networks, Phys. Rev. E 63(6), 066117 (2001)

[27] J. Qu, M. Tang, Y. Liu, and S. Guan, Identifying influential spreaders in reversible process, Chaos Solitons Fractals 140, 110197 (2020)

[28] P. Shu, W. Wang, M. Tang, P. Zhao, and Y. Zhang, Recovery rate affects the effective epidemic threshold with synchronous updating, Chaos 26(6), 063108 (2016)

[29] Y. Liu, M. Tang, T. Zhou, and Y. Do, Core-like groups result in invalidation of identifying super-spreader by kshell decomposition, Sci. Rep. 5(1), 9602 (2015)

[30] S. C. Ferreira, C. Castellano, and R. Pastor-Satorras, Epidemic thresholds of the susceptible-infected-susceptible model on networks: A comparison of numerical and theoretical results, Phys. Rev. E 86(4), 041125 (2012)

[31] P. Shu, W. Wang, M. Tang, and Y. Do, Numerical identification of epidemic thresholds for susceptible-infectedrecovered model on finite-size networks, Chaos 25(6), 063104 (2015)

[32] Y. Xu, M. Tang, Y. Liu, Y. Zou, and Z. Liu, Identifying epidemic threshold by temporal profile of outbreaks on networks, Chaos 29(10), 103141 (2019)

[33] Y. Liu, M. Tang, T. Zhou, and Y. Do, Identify influential spreaders in complex networks, the role of neighborhood, Physica A 452, 289 (2016)

[34] M. G. Kendall, A new measure of rank correlation, Biometrika 30(1–2), 81 (1938)

[35] M. E. Newman, Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E 74(3), 036104 (2006)

[36] N. Spring, R. Mahajan, and D. Wetherall, Measuring ISP topologies with rocketfuel, Comput. Commun. Rev. 32(4), 133 (2002)

[37] M. Boguñá, R. Pastorsatorras, A. Diazguilera, and A. Arenas, Models of social networks based on social distance attachment, Phys. Rev. E 70(5), 056122 (2004)

[38] M. E. Newman, The structure of scientific collaboration networks, Proc. Natl. Acad. Sci. USA 98(2), 404 (2001)

[39] M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse, Identification of influential spreaders in complex networks, Nat. Phys. 6(11), 888 (2010)

[40] M. Boguñá, C. Castellano, and R. Pastor-Satorras, Nature of the epidemic threshold for the susceptible-infectedsusceptible dynamics in networks, Phys. Rev. Lett. 111(6), 068701 (2013)

[41] C. Castellano and R. Pastor-Satorras, Competing activation mechanisms in epidemics on networks, Sci. Rep. 2(1), 371 (2012)

[42] H. Zhang, J. Xie, M. Tang, and Y. Lai, Suppression of epidemic spreading in complex networks by local information based behavioral responses, Chaos 24(4), 043106 (2014)

[43] X. Chen, R. Wang, M. Tang, S. Cai, H. E. Stanley, and L. A. Braunstein, Suppressing epidemic spreading in multiplex networks with social-support, New J. Phys. 20(1), 013007 (2018)

[44] W. Wang, M. Tang, H. Zhang, and Y. Lai, Dynamics of social contagions with memory of nonredundant information, Phys. Rev. E 92(1), 012820 (2015)

[45] Z. Lin, M. Feng, M. Tang, Z. Liu, C. Xu, P. M. Hui, and Y. Lai, Non-Markovian recovery makes complex networks more resilient against largescale failures, Nat. Commun. 11, 2490 (2020)

RIGHTS & PERMISSIONS

Higher Education Press