Influential Nodes Identification in Complex Networks: Sampling Approach
Keywords:
Complex Network, Influential node, Centrality indices, Sampling, SIR model.Abstract
Accurately identifying influential nodes within complex networks is crucial for understanding information and influence propagation. Existing state-of-the-art algorithms, while powerful, often rank all nodes, which can be computationally expensive and unnecessary for many applications. In this paper, we propose a simple yet efficient approach that overcomes these limitations. Initially, a systematic sampling methodology was employed to strategically select a subset of nodes from the network, representing a small fraction of its entirety. Subsequently, the betweenness centrality of these sampled nodes was estimated to facilitate their ranking. To assess the performance of our sampling method alongside alternative algorithms, we employ the stochastic Susceptible–Infected–Recovered (SIR) information diffusion model to compute various metrics including the infection scale, the final infected scale over time, and the average distance between spreaders. Our experimental findings, conducted on real-world networks, indicate that our proposed method accurately identifies influential nodes while maintaining significant computational efficiency.
Downloads
References
K. Taha, “Static and Dynamic Community Detection Methods That Optimize a Specific Objective Function: A Survey and Experimental Evaluation,” IEEE Access, vol. 8. Institute of Electrical and Electronics Engineers Inc., pp. 98330–98358, 2020. doi: 10.1109/ACCESS.2020.2996595.
F. Zhu et al., “A context-aware trust-oriented influencers finding in online social networks,” in 2015 IEEE International Conference on Web Services, IEEE, 2015, pp. 456–463.
A. Sheikhahmadi and M. A. Nematbakhsh, “Identification of multi-spreader users in social networks for viral marketing,” J. Inf. Sci., vol. 43, no. 3, pp. 412–423, 2017.
J. Gu, L. C. Abroms, D. A. Broniatowski, and W. D. Evans, “An investigation of influential users in the promotion and marketing of heated tobacco products on Instagram: a social network analysis,” Int. J. Environ. Res. Public Health, vol. 19, no. 3, p. 1686, 2022.
X. Wei, J. Zhao, S. Liu, and Y. Wang, “Identifying influential spreaders in complex networks for disease spread and control,” Sci. Rep., vol. 12, no. 1, p. 5550, 2022.
A. Susarla, J.-H. Oh, and Y. Tan, “Influentials, imitables, or susceptibles? Virality and word-of-mouth conversations in online social networks,” J. Manag. Inf. Syst., vol. 33, no. 1, pp. 139–170, 2016.
F. J. Arenas-Márquez, M. del R. Martínez-Torres, and S. L. Toral, “How can trustworthy influencers be identified in electronic word-of-mouth communities?,” Technol. Forecast. Soc. Change, vol. 166, p. 120596, 2021.
L. C. Freeman, “Centrality in social networks: Conceptual clarification,” Soc. Netw. Crit. concepts Sociol. Londres Routledge, vol. 1, pp. 238–263, 2002.
L. C. Freeman, “A set of measures of centrality based on betweenness,” Sociometry, pp. 35–41, 1977.
G. Sabidussi, “The centrality index of a graph,” Psychometrika, vol. 31, no. 4, pp. 581–603, 1966.
D. Chen, L. Lü, M.-S. Shang, Y.-C. Zhang, and T. Zhou, “Identifying influential nodes in complex networks,” Phys. a Stat. Mech. its Appl., vol. 391, no. 4, pp. 1777–1787, 2012.
R. Zafarani, M. A. Abbasi, and H. Liu, Social media mining: an introduction. Cambridge University Press, 2014.
R. Bhattacharya, N. K. Nagwani, and S. Tripathi, “Detecting influential nodes with topological structure via Graph Neural Network approach in social networks,” Int. J. Inf. Technol., vol. 15, no. 4, pp. 2233–2246, 2023.
K. Hajarathaiah, M. K. Enduri, S. Anamalamudi, and A. R. Sangi, “Algorithms for finding influential people with mixed centrality in social networks,” Arab. J. Sci. Eng., vol. 48, no. 8, pp. 10417–10428, 2023.
S. M. V Reddy, D. Annapurna, and A. Narasimhamurthy, “Influence node analysis based on neighborhood influence vote rank method in social network,” Sci. Temper, vol. 14, no. 04, pp. 1537–1543, 2023.
F. Bloch, M. O. Jackson, and P. Tebaldi, “Centrality measures in networks,” Soc. Choice Welfare, vol. 61, no. 2, pp. 413–453, 2023.
Q. Liu et al., “An influence propagation view of pagerank,” ACM Trans. Knowl. Discov. from Data, vol. 11, no. 3, pp. 1–30, 2017.
Y. Wang, G. Yan, Q. Ma, Y. Wu, and D. Jin, “Identifying influential spreaders on weighted networks based on ClusterRank,” in 2017 10th International Symposium on Computational Intelligence and Design (ISCID), IEEE, 2017, pp. 476–479.
L. Lü, Y.-C. Zhang, C. H. Yeung, and T. Zhou, “Leaders in social networks, the delicious case,” PLoS One, vol. 6, no. 6, p. e21202, 2011.
G. Huang, J. Liu, X. Chen, and J. Ren, “A New Method of Identifying Influential Nodes in Complex Software Network Based on LeaderRank,” 2016.
G. Maji, S. Mandal, and S. Sen, “A systematic survey on influential spreaders identification in complex networks with a focus on K-shell based techniques,” Expert Syst. Appl., vol. 161, p. 113681, 2020.
M. Gupta and R. Mishra, “Spreading the information in complex networks: Identifying a set of top-N influential nodes using network structure,” Decis. Support Syst., vol. 149, p. 113608, 2021.
Z. Zhao, D. Li, Y. Sun, R. Zhang, and J. Liu, “Ranking influential spreaders based on both node k-shell and structural hole,” Knowledge-Based Syst., vol. 260, p. 110163, 2023.
M. E. J. Newman, “Analysis of weighted networks,” Phys. Rev. E, vol. 70, no. 5, p. 56131, 2004.
D.-B. Chen, H. Gao, L. Lü, and T. Zhou, “Identifying influential nodes in large-scale directed networks: the role of clustering,” PLoS One, vol. 8, no. 10, p. e77455, 2013.
Y. Liu, M. Tang, T. Zhou, and Y. Do, “Identify influential spreaders in complex networks, the role of neighborhood,” Phys. A Stat. Mech. its Appl., vol. 452, pp. 289–298, 2016.
J.-X. Zhang, D.-B. Chen, Q. Dong, and Z.-D. Zhao, “Identifying a set of influential spreaders in complex networks,” Sci. Rep., vol. 6, no. 1, p. 27823, 2016.
S. Kumar and B. S. Panda, “Identifying influential nodes in Social Networks: Neighborhood Coreness based voting approach,” Phys. A Stat. Mech. its Appl., vol. 553, p. 124215, 2020.
P. Liu, L. Li, S. Fang, and Y. Yao, “Identifying influential nodes in social networks: A voting approach,” Chaos, Solitons & Fractals, vol. 152, p. 111309, 2021.
L. Ma, C. Ma, H.-F. Zhang, and B.-H. Wang, “Identifying influential spreaders in complex networks based on gravity formula,” Phys. A Stat. Mech. its Appl., vol. 451, pp. 205–212, 2016.
Z. Li et al., “Identification of a promoter element mediating kisspeptin-induced increases in GnRH gene expression in sheep,” Gene, vol. 699, pp. 1–7, 2019.
X. Yang and F. Xiao, “An improved gravity model to identify influential nodes in complex networks based on k-shell method,” Knowledge-Based Syst., vol. 227, p. 107198, 2021.
S. Wang, Y. Du, and Y. Deng, “A new measure of identifying influential nodes: Efficiency centrality,” Commun. Nonlinear Sci. Numer. Simul., vol. 47, pp. 151–163, 2017.
M. M. Tulu, R. Hou, and T. Younas, “Identifying influential nodes based on community structure to speed up the dissemination of information in complex network,” IEEE access, vol. 6, pp. 7390–7401, 2018.
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, 2014.
M. Li, R. Zhang, R. Hu, F. Yang, Y. Yao, and Y. Yuan, “Identifying and ranking influential spreaders in complex networks by combining a local-degree sum and the clustering coefficient,” Int. J. Mod. Phys. B, vol. 32, no. 06, p. 1850118, 2018.
A. Zareie, A. Sheikhahmadi, and M. Jalili, “Influential node ranking in social networks based on neighborhood diversity,” Futur. Gener. Comput. Syst., vol. 94, pp. 120–129, 2019.
A. Zareie, A. Sheikhahmadi, M. Jalili, and M. S. K. Fasaei, “Finding influential nodes in social networks based on neighborhood correlation coefficient,” Knowledge-based Syst., vol. 194, p. 105580, 2020.
A. Namtirtha, A. Dutta, and B. Dutta, “Identifying influential spreaders in complex networks based on kshell hybrid method,” Phys. A Stat. Mech. its Appl., vol. 499, pp. 310–324, 2018.
A. Namtirtha, A. Dutta, and B. Dutta, “Weighted kshell degree neighborhood: A new method for identifying the influential spreaders from a variety of complex network connectivity structures,” Expert Syst. Appl., vol. 139, p. 112859, 2020.
C. Guo, L. Yang, X. Chen, D. Chen, H. Gao, and J. Ma, “Influential nodes identification in complex networks via information entropy,” Entropy, vol. 22, no. 2, pp. 1–19, 2020, doi: 10.3390/e22020242.
X. Xu, C. Zhu, Q. Wang, X. Zhu, and Y. Zhou, “Identifying vital nodes in complex networks by adjacency information entropy,” Sci. Rep., vol. 10, no. 1, pp. 1–12, 2020, doi: 10.1038/s41598-020-59616-w.
F. Liu, Z. Wang, and Y. Deng, “GMM: A generalized mechanics model for identifying the importance of nodes in complex networks,” Knowledge-Based Syst., vol. 193, p. 105464, 2020.
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, p. 8387, 2019.
J. Zhao, Y. Wang, and Y. Deng, “Identifying influential nodes in complex networks from global perspective,” Chaos, Solitons & Fractals, vol. 133, p. 109637, 2020.
Y. Liu, X. Wei, W. Chen, L. Hu, and Z. He, “A graph-traversal approach to identify influential nodes in a network,” Patterns, vol. 2, no. 9, 2021.
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, 2023.
L. Qiu, Y. Liu, and J. Zhang, “A New Method for Identifying Influential Spreaders in Complex Networks,” Comput. J., vol. 67, no. 1, pp. 362–375, 2024.
M. E. Berberler, “Global and local structure‐based influential nodes identification in wheel‐type networks,” Numer. Methods Partial Differ. Equ., vol. 40, no. 1, p. e22709, 2024.
U. Brandes, “A faster algorithm for betweenness centrality,” J. Math. Sociol., vol. 25, no. 2, pp. 163–177, 2001.
R. M. May, Infectious diseases of humans: dynamics and control. Oxford University Press, 1991.
G. Xu and C. Dong, “CAGM: A communicability-based adaptive gravity model for influential nodes identification in complex networks,” Expert Syst. Appl., vol. 235, p. 121154, 2024.
J. Leskovec and A. Krevl, “Stanford large network dataset collection (snap),” URL http//snap. stanford. edu/data/index. html, 2010.
J. Kunegis, “Konect: the koblenz network collection,” in Proceedings of the 22nd international conference on world wide web, 2013, pp. 1343–1350.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.
IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.
