Estimating the Expected Influence Capacities of Nodes in Complex Networks under the Susceptible-Infectious-Recovered Model

Abstract

In recent years, epidemic modeling in complex networks has found many applications, including modeling of information or gossip spread in online social networks, modeling of malware spread in communication networks, and the most recent model of the COVID-19 pandemic. If the information disseminated is accurate, for example, maximizing its distribution is desirable, whereas if it is a rumor or a virus, its spread should be minimized. In this context, it is very important to identify super-spreaders that maximize or minimize propagation. Lately, studies for detecting super-spreaders have gained momentum. Most of the studies carried out aim to distinguish the influences of nodes under a specific propagation model (such as SIR) using network centrality measures and subsequently, to rank the nodes accordingly. However, in this study, we developed an algorithm that approximates the expected influence of nodes under the popular SIR model. By considering the behavior of the SIR model and only the shortest paths between nodes, the algorithm ranks the nodes according to this approximated value. Our developed algorithm is named the Expected Value Estimation (EVE). We compared the performance of EVE, using different SIR settings on real-world datasets, with that of many current well-known centrality measures. The experimental studies demonstrated that the solution quality (ranking capability) of EVE is superior to that of its competitors.

Keywords

• Complex networks
• Susceptible-Infectious-Recovered model
• Expected influence
• Centrality Measures
• Node ranking

References

1. [1] J. Gao, B. Barzel, and A.-L. Barabási, “Universal resilience patterns in complex networks,” Nature, vol. 530, no. 7590, pp. 307–312, Feb. 2016, doi: 10.1038/nature16948.
2. [2] A.-L. Barabási, N. Gulbahce, and J. Loscalzo, “Network medicine: a network-based approach to human disease,” Nat. Rev. Genet., vol. 12, no. 1, pp. 56–68, Jan. 2011, doi: 10.1038/nrg2918.
3. [3] H. Alasmary et al., “Analyzing and Detecting Emerging Internet of Things Malware: A Graph-Based Approach,” IEEE Internet Things J., vol. 6, no. 5, pp. 8977–8988, 2019, doi: 10.1109/JIOT.2019.2925929.
4. [4] J. Yang, C. Yao, W. Ma, and G. Chen, “A study of the spreading scheme for viral marketing based on a complex network model,” Phys. A Stat. Mech. its Appl., vol. 389, no. 4, pp. 859–870, Feb. 2010, doi: 10.1016/j.physa.2009.10.034.
5. [5] İ. Tuğal and A. Karcı, “Comparisons of Karcı and Shannon entropies and their effects on centrality of social networks,” Phys. A Stat. Mech. its Appl., vol. 523, pp. 352–363, Jun. 2019, doi: 10.1016/j.physa.2019.02.026.
6. [6] J. Leskovec, D. Huttenlocher, and J. Kleinberg, “Predicting positive and negative links in online social networks,” in Proceedings of the 19th international conference on World wide web - WWW ’10, 2010, p. 641. doi: 10.1145/1772690.1772756.
7. [7] S. P. Borgatti, A. Mehra, D. J. Brass, and G. Labianca, “Network Analysis in the Social Sciences,” Science (80-. )., vol. 323, no. 5916, pp. 892–895, Feb. 2009, doi: 10.1126/science.1165821.
8. [8] S. Chang et al., “Mobility network models of COVID-19 explain inequities and inform reopening,” Nature, vol. 589, no. 7840, pp. 82–87, Jan. 2021, doi: 10.1038/s41586-020-2923-3.

9. [9] Y. Yang, X. Wang, Y. Chen, M. Hu, and C. Ruan, “A Novel Centrality of Influential Nodes Identification in Complex Networks,” IEEE Access, vol. 8, pp. 58742–58751, 2020, doi: 10.1109/ACCESS.2020.2983053.
10. [10] J. Zhang, C. Yang, Z. Jin, and J. Li, “Dynamics analysis of SIR epidemic model with correlation coefficients and clustering coefficient in networks,” J. Theor. Biol., vol. 449, pp. 1–13, 2018, doi: 10.1016/j.jtbi.2018.04.007.
11. [11] S. Banerjee, M. Jenamani, and D. K. Pratihar, “A survey on influence maximization in a social network,” Knowl. Inf. Syst., 2020, doi: 10.1007/s10115-020-01461-4.
12. [12] D. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network,” in Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD ’03, 2003, p. 137. doi: 10.1145/956750.956769.
13. [13] S. P. Borgatti, “Identifying sets of key players in a social network,” Comput. Math. Organ. Theory, vol. 12, no. 1, pp. 21–34, Apr. 2006, doi: 10.1007/s10588-006-7084-x.
14. [14] L. C. Freeman, “A Set of Measures of Centrality Based on Betweenness,” Sociometry, vol. 40, no. 1, p. 35, Mar. 1977, doi: 10.2307/3033543.
15. [15] L. Katz, “A new status index derived from sociometric analysis,” Psychometrika, vol. 18, no. 1, pp. 39–43, Mar. 1953, doi: 10.1007/BF02289026.
16. [16] L. Page, S. Brin, R. Motwani, and T. Winograd, “The PageRank Citation Ranking: Bringing Order to the Web.,” Stanford InfoLab, 1999. [Online]. Available: http://ilpubs.stanford.edu:8090/422/
17. [17] J. Sheng et al., “Identifying influential nodes in complex networks based on global and local structure,” Phys. A Stat. Mech. its Appl., vol. 541, p. 123262, 2020, doi: 10.1016/j.physa.2019.123262.
18. [18] C. Salavati, A. Abdollahpouri, and Z. Manbari, “Ranking nodes in complex networks based on local structure and improving closeness centrality,” Neurocomputing, vol. 336, pp. 36–45, 2019, doi: 10.1016/j.neucom.2018.04.086.
19. [19] Z. Ghalmane, M. El Hassouni, C. Cherifi, and H. Cherifi, “Centrality in modular networks,” EPJ Data Sci., vol. 8, no. 1, 2019, doi: 10.1140/epjds/s13688-019-0195-7.
20. [20] J. Zhao, Y. Song, and Y. Deng, “A novel model to identify the influential nodes: Evidence theory centrality,” IEEE Access, vol. 8, pp. 46773–46780, 2020, doi: 10.1109/ACCESS.2020.2978142.
21. [21] Z. Lv, N. Zhao, F. Xiong, and N. Chen, “A novel measure of identifying influential nodes in complex networks,” Phys. A Stat. Mech. its Appl., vol. 523, pp. 488–497, 2019, doi: 10.1016/j.physa.2019.01.136.
22. [22] M. Curado, L. Tortosa, and J. F. Vicent, “A novel measure to identify influential nodes: Return Random Walk Gravity Centrality,” Inf. Sci. (Ny)., vol. 628, pp. 177–195, May 2023, doi: 10.1016/j.ins.2023.01.097.
23. [23] Z. Zhao, X. Wang, W. Zhang, and Z. Zhu, “A community-based approach to identifying influential spreaders,” Entropy, vol. 17, no. 4, pp. 2228–2252, 2015, doi: 10.3390/e17042228.
24. [24] Z. Ghalmane, C. Cherifi, H. Cherifi, and M. El Hassouni, “Centrality in Complex Networks with Overlapping Community Structure,” Sci. Rep., vol. 9, no. 1, pp. 1–29, 2019, doi: 10.1038/s41598-019-46507-y.
25. [25] Y. Zhao, S. Li, and F. Jin, “Identification of influential nodes in social networks with community structure based on label propagation,” Neurocomputing, vol. 210, pp. 34–44, 2016, doi: 10.1016/j.neucom.2015.11.125.
26. [26] Y. Y. Keng, K. H. Kwa, and C. McClain, “Convex combinations of centrality measures,” J. Math. Sociol., 2020, doi: 10.1080/0022250X.2020.1765776.
27. [27] S. S. Ali, T. Anwar, and S. A. M. Rizvi, “A Revisit to the Infection Source Identification Problem under Classical Graph Centrality Measures,” Online Soc. Networks Media, vol. 17, no. xxxx, p. 100061, May 2020, doi: 10.1016/j.osnem.2020.100061.
28. [28] M. Alshahrani, Z. Fuxi, A. Sameh, S. Mekouar, and S. Huang, “Efficient algorithms based on centrality measures for identification of top-K influential users in social networks,” Inf. Sci. (Ny)., vol. 527, pp. 88–107, Jul. 2020, doi: 10.1016/j.ins.2020.03.060.
29. [29] M. Şimşek and H. Meyerhenke, “Combined centrality measures for an improved characterization of influence spread in social networks,” J. Complex Networks, vol. 8, no. 1, Feb. 2020, doi: 10.1093/comnet/cnz048.
30. [30] L. Ma, C. Ma, H. Zhang, and B. Wang, “Identifying influential spreaders in complex networks based on gravity formula,” Phys. A Stat. Mech. its Appl., vol. 451, pp. 205–212, Jun. 2016, doi: 10.1016/j.physa.2015.12.162.
31. [31] X.-L. Yan, Y.-P. Cui, and S.-J. Ni, “Identifying influential spreaders in complex networks based on entropy weight method and gravity law,” Chinese Phys. B, vol. 29, no. 4, p. 048902, Apr. 2020, doi: 10.1088/1674-1056/ab77fe.
32. [32] A. Şimşek, “Lexical sorting centrality to distinguish spreading abilities of nodes in complex networks under the Susceptible-Infectious-Recovered (SIR) model,” J. King Saud Univ. - Comput. Inf. Sci., Jun. 2021, doi: 10.1016/j.jksuci.2021.06.010.
33. [33] X. Wen, C. Tu, M. Wu, and X. Jiang, “Fast ranking nodes importance in complex networks based on LS-SVM method,” Phys. A Stat. Mech. its Appl., vol. 506, pp. 11–23, Sep. 2018, doi: 10.1016/j.physa.2018.03.076.
34. [34] L. Sabah and M. Şimşek, “A new fast entropy‐based method to generate composite centrality measures in complex networks,” Concurr. Comput. Pract. Exp., vol. 35, no. 10, May 2023, doi: 10.1002/cpe.7657.
35. [35] J. Liu, J. Lin, Q. Guo, and T. Zhou, “Locating influential nodes via dynamics-sensitive centrality,” Sci. Rep., vol. 6, no. 1, p. 21380, Feb. 2016, doi: 10.1038/srep21380.
36. [36] D. Tolić, K.-K. Kleineberg, and N. Antulov-Fantulin, “Simulating SIR processes on networks using weighted shortest paths,” Sci. Rep., vol. 8, no. 1, p. 6562, Dec. 2018, doi: 10.1038/s41598-018-24648-w.
37. [37] M. G. Kendall, “A New Measure of Rank Correlation,” Biometrika, vol. 30, no. 1–2, pp. 81–93, Jun. 1938, doi: 10.1093/biomet/30.1-2.81.
38. [38] J. Bae and S. Kim, “Identifying and ranking influential spreaders in complex networks by neighborhood coreness,” Phys. A Stat. Mech. its Appl., vol. 395, pp. 549–559, Feb. 2014, doi: 10.1016/j.physa.2013.10.047.
39. [39] G. Rossetti, L. Milli, S. Rinzivillo, A. Sîrbu, D. Pedreschi, and F. Giannotti, “NDlib: a python library to model and analyze diffusion processes over complex networks,” Int. J. Data Sci. Anal., vol. 5, no. 1, pp. 61–79, Feb. 2018, doi: 10.1007/s41060-017-0086-6.
40. [40] M. Newman, Networks, Second. Oxford, UK: Oxford University Press, 2018.
41. [41] P. Bonacich, “Power and Centrality: A Family of Measures,” Am. J. Sociol., vol. 92, no. 5, pp. 1170–1182, Mar. 1987, doi: 10.1086/228631.
42. [42] G. Sabidussi, “The centrality index of a graph,” Psychometrika, vol. 31, no. 4, pp. 581–603, Dec. 1966, doi: 10.1007/BF02289527.
43. [43] T. Wen, D. Pelusi, and Y. Deng, “Vital spreaders identification in complex networks with multi-local dimension,” Knowledge-Based Syst., vol. 195, p. 105717, 2020, doi: 10.1016/j.knosys.2020.105717.
44. [44] R. A. Rossi and N. K. Ahmed, “The Network Data Repository with Interactive Graph Analytics and Visualization,” 2015. [Online]. Available: http://networkrepository.com
45. [45] Z. Li, T. Ren, X. Ma, S. Liu, Y. Zhang, and T. Zhou, “Identifying influential spreaders by gravity model,” Sci. Rep., vol. 9, no. 1, pp. 1–7, 2019, doi: 10.1038/s41598-019-44930-9.
46. [46] A. A. Hagberg, D. A. Schult, and P. J. Swart, “Exploring Network Structure, Dynamics, and Function using NetworkX,” in Proceedings of the 7th Python in Science Conference, 2008, pp. 11–15.