Abstract
The study of influential spreaders has become a growing area of interest within network sciences due to its critical implications in understanding the robustness and vulnerability of complex networks. There is a significant degree of focus on the factors that dictate the decision-making process for identifying these influential spreaders in highly complex networks, given their crucial role in network performance and security. Previous research methodologies have offered a deep understanding of the importance of spreaders, also referred to as nodes. These methods, however, have primarily depended on either neighborhood or path information to identify these spreaders. They have often studied local network data, or adopted a more broad-based, global view of the network. Such an approach may not provide a comprehensive understanding of the overall network structure and the relationships between nodes. Addressing this limitation, our research introduces Neighborhood and Path Information-based Centrality (NPIC) algorithm. This innovative centrality algorithm combines both neighborhood and path information to identify influential spreaders in a complex network. By incorporating these two significant aspects, NPIC provides a more holistic analysis of network centrality, enabling a more accurate identification of influential spreaders. We have subjected NPIC to rigorous testing using numerous simulations on both real and artificially-created datasets. These simulations applied an epidemic model to calculate the spreading efficiency of each node within its given environment. Our simulations, conducted across a wide range of synthetic and real-world datasets, demonstrated that NPIC outperforms existing methodologies in identifying influential spreaders in corresponding networks.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Availability of data and materials/Availability of supporting data
The datasets generated during and/or analyzed during the current study are publicly available at the following http://networkrepository.com/.
Code Availability
The code will be made available upon request.
References
Al-garadi, M. A., Varathan, K. D., & Ravana, S. D. (2017). Identification of influential spreaders in online social networks using interaction weighted k-core decomposition method. Physica A: Statistical Mechanics and its Applications, 468, 278–288. https://doi.org/10.1016/j.physa.2016.11.002
Amancio, D., Nunes, M., Oliveira, O., et al. (2011). Using metrics from complex networks to evaluate machine translation. Physica A: Statistical Mechanics and its Applications, 390(1), 131–142. https://doi.org/10.1016/j.physa.2010.08.052
Bakhat, K., Kifayat, K., Islam, M. S., et al. (2023). Katz centrality based approach to perform human action recognition by using OMKZ. Signal Image Video Process., 17(4), 1677–1685. https://doi.org/10.1007/s11760-022-02378-x
Batagelj, V., & Zaversnik, M. (2011). Fast algorithms for determining (generalized) core groups in social networks. Advances in Data Analysis and Classification, 5(2), 129–145. https://doi.org/10.1007/s11634-010-0079-y
Brin, S., & Page, L. (2012). Reprint of: the anatomy of a large-scale hypertextual web search engine. Computer Networks, 56(18), 3825–3833. https://doi.org/10.1016/j.comnet.2012.10.007
Chen, D., Lü, L., Shang, M.-S., et al. (2012). Identifying influential nodes in complex networks. Physica A: Statistical Mechanics and its Applications, 391(4), 1777–1787. https://doi.org/10.1016/j.physa.2011.09.017
Chouchani, N., & Abed, M. (2020). Online social network analysis: detection of communities of interest. Journal of Intelligent Information Systems, 54(1), 5–21. https://doi.org/10.1007/s10844-018-0522-7
Dai, J., Wang, B., Sheng, J., et al. (2019). Identifying influential nodes in complex networks based on local neighbor contribution. IEEE Access, 7, 131719–131731. https://doi.org/10.1109/ACCESS.2019.2939804
Du, Y., Gao, C., Hu, Y., et al. (2014). A new method of identifying influential nodes in complex networks based on topsis. Physica A: Statistical Mechanics and its Applications, 399, 57–69. https://doi.org/10.1016/j.physa.2013.12.031
Estrada, E., & Rodríguez-Velázquez, J.A. (2005, May). Subgraph centrality in complex networks. Physical Review E, 71, 056103. https://doi.org/10.1103/PhysRevE.71.056103
Fei, L., Zhang, Q., & Deng, Y. (2018). Identifying influential nodes in complex networks based on the inverse-square law. Physica A: Statistical Mechanics and its Applications, 512, 1044–1059. https://doi.org/10.1016/j.physa.2018.08.135
Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry,35–41. https://doi.org/10.2307/3033543
Freeman, L. C. (1978). Centrality in social networks conceptual clarification. Social Networks, 1(3), 215–239. https://doi.org/10.1016/0378-8733(78)90021-7
Gao, C., Wei, D., Hu, Y., et al. (2013). A modified evidential methodology of identifying influential nodes in weighted networks. Physica A: Statistical Mechanics and its Applications, 392(21), 5490–5500. https://doi.org/10.1016/j.physa.2013.06.059
García, S., Luengo, J., & Herrera, F. (2016). Tutorial on practical tips of the most influential data preprocessing algorithms in data mining. Knowledge-Based Systems, 98, 1–29. https://doi.org/10.1016/j.knosys.2015.12.006
Gupta, A., Khatri, I., Choudhry, A., et al. (2023). Mcd: a modified community diversity approach for detecting influential nodes in social networks. Journal of Intelligent Information Systems,1–23. https://doi.org/10.1007/s10844-023-00776-2
Hajibabaei, H., Seydi, V., & Koochari, A. (2023). Community detection in weighted networks using probabilistic generative model. Journal of Intelligent Information Systems, 60(1), 119–136. https://doi.org/10.1007/s10844-022-00740-6
Hou, B., Yao, Y., & Liao, D. (2012). Identifying all-around nodes for spreading dynamics in complex networks. Physica A: Statistical Mechanics and its Applications, 391(15), 4012–4017. https://doi.org/10.1016/j.physa.2012.02.033
Ibnoulouafi, A., & El Haziti, M. (2018). Density centrality: identifying influential nodes based on area density formula. Chaos, Solitons & Fractals, 114, 69–80. https://doi.org/10.1016/j.chaos.2018.06.022
Kai-Quan, C., Jun, Z., Wen-Bo, D., et al. (2012). Analysis of the chinese air route network as a complex network. Chinese Physics B, 21(2), 028903. https://doi.org/10.1088/1674-1056/21/2/028903
Kitsak, M., Gallos, L. K., Havlin, S., et al. (2010). Identification of influential spreaders in complex networks. Nature Physics, 6(11), 888–893. https://doi.org/10.1038/nphys1746
Kleinberg, J. M. (1999). Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM), 46(5), 604–632. https://doi.org/10.1145/324133.324140
ling Ma, L., Ma, C., Zhang, H.-F., et al. (2016). Identifying influential spreaders in complex networks based on gravity formula. Physica A: Statistical Mechanics and its Applications, 451, 205–212. https://doi.org/10.1016/j.physa.2015.12.162
Liu, F., Wang, Z., & Deng, Y. (2020). Gmm: a generalized mechanics model for identifying the importance of nodes in complex networks. Knowledge-Based Systems, 193,. https://doi.org/10.1016/j.knosys.2019.105464
Li, S., & Xiao, F. (2021). The identification of crucial spreaders in complex networks by effective gravity model. Information Sciences, 578, 725–749. https://doi.org/10.1016/j.ins.2021.08.026
Lü, L., Zhang, Y.-C., Yeung, C. H., et al. (2011). Leaders in social networks, the delicious case. PloS one, 6(6), e21202. https://doi.org/10.1371/journal.pone.0021202
Lü, L., Zhou, T., Zhang, Q.-M., et al. (2016). The h-index of a network node and its relation to degree and coreness. Nature Communications, 7(1), 1–7. https://doi.org/10.1038/ncomms10168
Mahapatra, R., Samanta, S., & Pal, M. (2023). Detecting influential node in a network using neutrosophic graph and its application. Soft Computing, 27(14), 9247–9260. https://doi.org/10.1007/s00500-023-08234-5
Ma, Q., & Ma, J. (2017). Identifying and ranking influential spreaders in complex networks with consideration of spreading probability. Physica A: Statistical Mechanics and its Applications, 465, 312–330. https://doi.org/10.1016/j.physa.2016.08.041
Mo, H., Gao, C., & Deng, Y. (2015). Evidential method to identify influential nodes in complex networks. Journal of Systems Engineering and Electronics, 26(2), 381–387. https://doi.org/10.1109/JSEE.2015.00044
Newman, M.E.J. (2001, Jun). Scientific collaboration networks. ii. shortest paths, weighted networks, and centrality. Physical Review E, 64, 016132, https://doi.org/10.1103/PhysRevE.64.016132
Pei, S., Teng, X., Shaman, J., et al. (2017). Efficient collective influence maximization in cascading processes with first-order transitions. Scientific Reports, 7(1), 45240. https://doi.org/10.1038/srep45240
Ruhnau, B. (2000). Eigenvector-centrality-a node-centrality? Social Networks, 22(4), 357–365. https://doi.org/10.1016/S0378-8733(00)00031-9
Shetty, R. D., Bhattacharjee, S., Dutta, A., et al. (2022). Gsi: an influential node detection approach in heterogeneous network using covid-19 as use case. IEEE Transactions on Computational Social Systems,1–15. https://doi.org/10.1109/TCSS.2022.3180177
Şimşek, A. (2022). Lexical sorting centrality to distinguish spreading abilities of nodes in complex networks under the susceptible-infectious-recovered (sir) model. Journal of King Saud University - Computer and Information Sciences, 34(8, Part A), 4810-4820, https://doi.org/10.1016/j.jksuci.2021.06.010
Sun, Z., Sun, Y., Chang, X., et al. (2023). Finding critical nodes in a complex network from information diffusion and matthew effect aggregation. Expert Systems with Applications, 233, 120927. https://doi.org/10.1016/j.eswa.2023.120927
Sun, Z., Wang, B., Sheng, J., et al. (2017). Identifying influential nodes in complex networks based on weighted formal concept analysis. IEEE Access, 5, 3777–3789. https://doi.org/10.1109/ACCESS.2017.2679038
Tian, S., Mo, S., Wang, L., et al. (2020). Deep reinforcement learning-based approach to tackle topic-aware influence maximization. Data Science and Engineering, 5, 1–11. https://doi.org/10.1007/s41019-020-00117-1
Ullah, A., Shao, J., Yang, Q., et al. (2023). Lss: a locality-based structure system to evaluate the spreader’s importance in social complex networks. Expert Systems with Applications, 228,. https://doi.org/10.1016/j.eswa.2023.120326
Ullah, A., Wang, B., Sheng, J., et al. (2021). Identification of influential nodes via effective distance-based centrality mechanism in complex networks. Complexity, 2021, 1–16. https://doi.org/10.1155/2021/8403738
Ullah, A., Wang, B., Sheng, J., et al. (2021). Identification of nodes influence based on global structure model in complex networks. Scientific Reports, 11(1), 1–11. https://doi.org/10.1038/s41598-021-84684-x
Ullah, A., Wang, B., Sheng, J., et al. (2021). Identifying vital nodes from local and global perspectives in complex networks. Expert Systems with Applications, 186, 115778. https://doi.org/10.1016/j.eswa.2021.115778
Ullah, A., Wang, B., Sheng, J., et al. (2022). Escape velocity centrality: escape influence-based key nodes identification in complex networks. Applied Intelligence, 52(14), 16586–16604. https://doi.org/10.1007/s10489-022-03262-4
Ullah, A., Wang, B., Sheng, J., et al. (2022). A novel relevance-based information interaction model for community detection in complex networks. Expert Systems with Applications, 196, 116607. https://doi.org/10.1016/j.eswa.2022.116607
Venunath, M., Sujatha, P., Dharavath, S., et al. (2023). Efficient method for identifying prominent supplier in large-scale healthcare information networks in medicare. Soft Computing,1–12. https://doi.org/10.1007/s00500-023-08391-7
Wang, Y., Li, H., Zhang, L., et al. (2022). Identifying influential nodes in social networks: centripetal centrality and seed exclusion approach. Chaos, Solitons & Fractals, 162,. https://doi.org/10.1016/j.chaos.2022.112513
Wang, L., Ma, L., Wang, C., et al. (2021). Identifying influential spreaders in social networks through discrete moth-flame optimization. IEEE Transactions on Evolutionary Computation, 25(6), 1091–1102. https://doi.org/10.1109/TEVC.2021.3081478
Yang, P., Meng, F., Zhao, L., et al. (2023). Aogc: an improved gravity centrality based on an adaptive truncation radius and omni-channel paths for identifying key nodes in complex networks. Chaos, Solitons & Fractals, 166,. https://doi.org/10.1016/j.chaos.2022.112974
Yang, X., & Xiao, F. (2021). An improved gravity model to identify influential nodes in complex networks based on k-shell method. Knowledge-Based Systems, 227, 107198. https://doi.org/10.1016/j.knosys.2021.107198
Yan, G., Zhou, T., Hu, B., Fu, Z.-Q., & Wang, B.-H. (2006). Efficient routing on complex networks. Physical Review E, 73(4), 046108. https://doi.org/10.1103/PhysRevE.73.046108
Yu, Z., Shao, J., Yang, Q., et al. (2019). Profitleader: identifying leaders in networks with profit capacity. World Wide Web, 22(2), 533–553. https://doi.org/10.1007/s11280-018-0537-6
Zagenczyk, T. J., Scott, K. D., Gibney, R., et al. (2010). Social influence and perceived organizational support: A social networks analysis. Organizational Behavior and Human Decision Processes, 111(2), 127–138. https://doi.org/10.1016/j.obhdp.2009.11.004
Zareie, A., Sheikhahmadi, A., Jalili, M., et al. (2020). Finding influential nodes in social networks based on neighborhood correlation coefficient. Knowledge-Based Systems, 194, 105580. https://doi.org/10.1016/j.knosys.2020.105580
Zeng, A., & Zhang, C.-J. (2013). Ranking spreaders by decomposing complex networks. Physics Letters A, 377(14), 1031–1035. https://doi.org/10.1016/j.physleta.2013.02.039
Zhang, Q., Shuai, B., & Lü, M. (2022). A novel method to identify influential nodes in complex networks based on gravity centrality. Information Sciences, 618, 98–117. https://doi.org/10.1016/j.ins.2022.10.070
Zhang, H., Zhong, S., Deng, Y., et al. (2022). Lfic: Identifying influential nodes in complex networks by local fuzzy information centrality. IEEE Transactions on Fuzzy Systems, 30(8), 3284–3296. https://doi.org/10.1109/TFUZZ.2021.3112226
Zhao, G., Jia, P., Zhou, A., et al. (2020). Infgcn: identifying influential nodes in complex networks with graph convolutional networks. Neurocomputing, 414, 18–26. https://doi.org/10.1016/j.neucom.2020.07.028
Acknowledgements
This work is supported by the National Key Research and Development Program of China under grant No.2018YFB1003602.
Funding
This work is supported by the National Key Research and Development Program of China under grant No.2018YFB1003602.
Author information
Authors and Affiliations
Contributions
Aman Ullah: Method, Writing, original draft, conceptualization, investigation, software. Bin Wang: Supervision. JinFang Sheng: Supervision. Salah Ud Din: Visualization. NasrUlla Khan: Visualization.
Corresponding author
Ethics declarations
Conflict of interest/Competing interests
The authors declare that they have no conflicts of interest.
Ethics approval
Our study did not include any human and/ or animal studies. All datasets used in the paper are publicly available for research purposes. Details related to all datasets can be found in Section 4.2.
Consent to participate
This study did not involve any human or animal subjects; therefore, issues related to consent to participate are not applicable.
Consent for publication
As our study did not involve human or animal subjects, there were no related issues concerning consent for publication.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Ullah, A., Sheng, J., Wang, B. et al. Leveraging neighborhood and path information for influential spreaders recognition in complex networks. J Intell Inf Syst 62, 377–401 (2024). https://doi.org/10.1007/s10844-023-00822-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10844-023-00822-z