The relative importance of structure and dynamics on node influence in reversible spreading processes
Jun-Yi Qu1, Ming Tang1,2(), Ying Liu3(), Shu-Guang Guan1()
1. School of Physics and Electronic Science, East China Normal University, Shanghai 200241, China 2. Shanghai Key Laboratory of Multidimensional Information Processing, East China Normal University, Shanghai 200241, China 3. School of Computer Science, Southwest Petroleum University, Chengdu 610500, China
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.
D. Koschützki, K. A. Lehmann, L. Peeters, S. Richter, D. Tenfelde-Podehl, and O. Zlotowski,in: Network Analysis, Springer, 2005, pp 16–61 https://doi.org/10.1007/978-3-540-31955-9_3
S. Pei, J. Wang, F. Morone, and H. A. Makse, Influencer identification in dynamical complex systems, J. Complex Netw. 8(2), cnz029 (2020) https://doi.org/10.1093/comnet/cnz029
A. Bovet and H. A. Makse, Influence of fake news in Twitter during the 2016 US presidential election, Nat. Commun. 10(1), 1 (2019) https://doi.org/10.1038/s41467-018-07761-2
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) https://doi.org/10.1007/s11467-018-0767-1
R. Albert, I. Albert, and G. L. Nakarado, Structural vulnerability of the North American power grid, Phys. Rev. E 69(2), 025103 (2004) https://doi.org/10.1103/PhysRevE.69.025103
F. Morone and H. A. Makse, Influence maximization in complex networks through optimal percolation, Nature 524(7563), 65 (2015) https://doi.org/10.1038/nature14604
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) https://doi.org/10.1073/pnas.1710547115
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) https://doi.org/10.1073/pnas.1614694114
16
K. Zheng, Y. Liu, Y. Wang, and W. Wang, k-core percolation on interdependent and interconnected multiplex networks, arXiv: 2101.02335 (2021) https://doi.org/10.1209/0295-5075/133/48003
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) https://doi.org/10.1103/PhysRevResearch.2.023332
S. Aral and P. S. Dhillon, Social influence maximization under empirical influence models, Nat. Hum. Behav. 2(6), 375 (2018) https://doi.org/10.1038/s41562-018-0346-z
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) https://doi.org/10.1038/srep00292
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) https://doi.org/10.1103/PhysRevLett.112.048701
22
R. Pastor-Satorras and A. Vespignani, Epidemic dynamics and endemic states in complex networks, Phys. Rev. E 63(6), 066117 (2001) https://doi.org/10.1103/PhysRevE.63.066117
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) https://doi.org/10.1073/pnas.1819449116
R. Pastor-Satorras, and A. Vespignani, Epidemic dynamics and endemic states in complex networks, Phys. Rev. E 63(6), 066117 (2001) https://doi.org/10.1103/PhysRevE.63.066117
27
J. Qu, M. Tang, Y. Liu, and S. Guan, Identifying influential spreaders in reversible process, Chaos Solitons Fractals 140, 110197 (2020) https://doi.org/10.1016/j.chaos.2020.110197
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) https://doi.org/10.1063/1.4953661
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) https://doi.org/10.1038/srep09602
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) https://doi.org/10.1103/PhysRevE.86.041125
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) https://doi.org/10.1063/1.4922153
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) https://doi.org/10.1063/1.5120491
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) https://doi.org/10.1016/j.physa.2016.02.028
N. Spring, R. Mahajan, and D. Wetherall, Measuring ISP topologies with rocketfuel, Comput. Commun. Rev. 32(4), 133 (2002) https://doi.org/10.1145/964725.633039
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) https://doi.org/10.1103/PhysRevE.70.056122
38
M. E. Newman, The structure of scientific collaboration networks, Proc. Natl. Acad. Sci. USA 98(2), 404 (2001) https://doi.org/10.1073/pnas.98.2.404
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) https://doi.org/10.1038/nphys1746
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) https://doi.org/10.1103/PhysRevLett.111.068701
41
C. Castellano and R. Pastor-Satorras, Competing activation mechanisms in epidemics on networks, Sci. Rep. 2(1), 371 (2012) https://doi.org/10.1038/srep00371
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) https://doi.org/10.1063/1.4896333
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) https://doi.org/10.1088/1367-2630/aa9cda
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) https://doi.org/10.1103/PhysRevE.92.012820
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) https://doi.org/10.1038/s41467-020-15860-2