[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Advertisement

Springer Nature Link
Log in

IC-SNI: measuring nodes’ influential capability in complex networks through structural and neighboring information

  • Regular Paper
  • Published:
Knowledge and Information Systems Aims and scope Submit manuscript

Abstract

Influential nodes are the important nodes that most efficiently control the propagation process throughout the network. Among various structural-based methods, degree centrality, k-shell decomposition, or their combination identify influential nodes with relatively low computational complexity, making them suitable for large-scale network analysis. However, these methods do not necessarily explore nodes’ underlying structure and neighboring information, which poses a significant challenge for researchers in developing timely and efficient heuristics considering appropriate network characteristics. In this study, we propose a new method (IC-SNI) to measure the influential capability of the nodes. IC-SNI minimizes the loopholes of the local and global centrality and calculates the topological positional structure by considering the local and global contribution of the neighbors. Exploring the path structural information, we introduce two new measurements (connectivity strength and effective distance) to capture the structural properties among the neighboring nodes. Finally, the influential capability of a node is calculated by aggregating the structural and neighboring information of up to two-hop neighboring nodes. Evaluated on nine benchmark datasets, IC-SNI demonstrates superior performance with the highest average ranking correlation of 0.813 with the SIR simulator and a 34.1% improvement comparing state-of-the-art methods in identifying influential spreaders. The results show that IC-SNI efficiently identifies the influential spreaders in diverse real networks by accurately integrating structural and neighboring information.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Schweitzer F, Fagiolo G, Sornette D, Vega-Redondo F, Vespignani A, White DR (2009) Economic networks: the new challenges. Science 325(5939):422–425. https://doi.org/10.1126/science.1173644

    Article  MathSciNet  MATH  Google Scholar 

  2. Vitak J, Zube P, Smock A, Carr CT, Ellison N, Lampe C (2011) It’s complicated: Facebook users’ political participation in the 2008 election. Cyberpsychol Behav Soc Netw 14(3):107–114. https://doi.org/10.1089/cyber.2009.0226

    Article  Google Scholar 

  3. Wei X, Zhao J, Liu S, Wang Y (2022) Identifying influential spreaders in complex networks for disease spread and control. Sci Rep 12(1):5550. https://doi.org/10.1038/s41598-022-09341-3

    Article  MATH  Google Scholar 

  4. Borge-Holthoefer J, Moreno Y (2012) Absence of influential spreaders in rumor dynamics. Phys Rev E 85:026116. https://doi.org/10.1103/PhysRevE.85.026116

    Article  MATH  Google Scholar 

  5. Zhao Z, Wang X, Zhang W, Zhu Z (2015) A community-based approach to identifying influential spreaders. Entropy 17(4):2228–2252. https://doi.org/10.3390/e17042228

    Article  MATH  Google Scholar 

  6. Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining. KDD ’09, pp 199–208. Association for Computing Machinery, New York, NY, USA. https://doi.org/10.1145/1557019.1557047

  7. Zhang J-X, Chen D-B, Dong Q, Zhao Z-D (2016) Identifying a set of influential spreaders in complex networks. Sci Rep 6(1):27823. https://doi.org/10.1038/srep27823

    Article  MATH  Google Scholar 

  8. Gong Y, Liu S, Bai Y (2021) Efficient parallel computing on the game theory-aware robust influence maximization problem. Knowl Based Syst 220:106942. https://doi.org/10.1016/j.knosys.2021.106942

    Article  MATH  Google Scholar 

  9. Arruda GF, Barbieri AL, Rodríguez PM, Rodrigues FA, Moreno Y, Costa LDF (2014) Role of centrality for the identification of influential spreaders in complex networks. Phys Rev E 90:032812. https://doi.org/10.1103/PhysRevE.90.032812

    Article  MATH  Google Scholar 

  10. Namtirtha A, Dutta A, Dutta B (2020) Weighted kshell degree neighborhood: a new method for identifying the influential spreaders from a variety of complex network connectivity structures. Expert Syst Appl 139:112859. https://doi.org/10.1016/j.eswa.2019.112859

    Article  MATH  Google Scholar 

  11. Morone F, Makse HA (2015) Influence maximization in complex networks through optimal percolation. Nature 524(7563):65–68. https://doi.org/10.1038/nature14604

    Article  MATH  Google Scholar 

  12. Kitsak M, Gallos LK, Havlin S, Liljeros F, Muchnik L, Stanley HE, Makse HA (2010) Identification of influential spreaders in complex networks. Nat Phys 6(11):888–893. https://doi.org/10.1038/nphys1746

    Article  MATH  Google Scholar 

  13. Sheikhahmadi A, Nematbakhsh MA (2017) Identification of multi-spreader users in social networks for viral marketing. J Inf Sci 43(3):412–423. https://doi.org/10.1177/0165551516644171

    Article  MATH  Google Scholar 

  14. Medo M, Zhang Y-C, Zhou T (2009) Adaptive model for recommendation of news. Europhys Lett 88(3):38005. https://doi.org/10.1209/0295-5075/88/38005

    Article  MATH  Google Scholar 

  15. Gupta M, Mishra R (2021) Spreading the information in complex networks: identifying a set of top-n influential nodes using network structure. Decis Support Syst 149:113608. https://doi.org/10.1016/j.dss.2021.113608

    Article  MATH  Google Scholar 

  16. Zhao Z, Li D, Sun Y, Zhang R, Liu J (2023) Ranking influential spreaders based on both node k-shell and structural hole. Knowl Based Syst 260:110163. https://doi.org/10.1016/j.knosys.2022.110163

    Article  Google Scholar 

  17. Maji G, Dutta A, Malta MC, Sen S (2021) Identifying and ranking super spreaders in real world complex networks without influence overlap. Expert Syst Appl 179:115061. https://doi.org/10.1016/j.eswa.2021.115061

    Article  Google Scholar 

  18. Namtirtha A, Dutta A, Dutta B (2018) Identifying influential spreaders in complex networks based on kshell hybrid method. Physica A 499:310–324. https://doi.org/10.1016/j.physa.2018.02.016

    Article  MATH  Google Scholar 

  19. Namtirtha A, Dutta B, Dutta A (2022) Semi-global triangular centrality measure for identifying the influential spreaders from undirected complex networks. Expert Syst Appl 206:117791. https://doi.org/10.1016/j.eswa.2022.117791

    Article  MATH  Google Scholar 

  20. Bonacich P (1972) Factoring and weighting approaches to status scores and clique identification. J Math Sociol 2(1):113–120. https://doi.org/10.1080/0022250X.1972.9989806

    Article  MATH  Google Scholar 

  21. Chen D-B, Gao H, Lü L, Zhou T (2013) Identifying influential nodes in large-scale directed networks: the role of clustering. PLoS ONE 8(10):1–10. https://doi.org/10.1371/journal.pone.0077455

    Article  MATH  Google Scholar 

  22. Freeman LC (1977) A set of measures of centrality based on betweenness. Sociometry. https://doi.org/10.2307/3033543

    Article  MATH  Google Scholar 

  23. Sabidussi G (1966) The centrality index of a graph. Psychometrika 31(4):581–603. https://doi.org/10.1007/BF02289527

    Article  MathSciNet  MATH  Google Scholar 

  24. Bonacich P, Lloyd P (2001) Eigenvector-like measures of centrality for asymmetric relations. Soc Netw 23(3):191–201. https://doi.org/10.1016/S0378-8733(01)00038-7

    Article  MATH  Google Scholar 

  25. Bae J, Kim S (2014) Identifying and ranking influential spreaders in complex networks by neighborhood coreness. Physica A 395:549–559. https://doi.org/10.1016/j.physa.2013.10.047

    Article  MathSciNet  MATH  Google Scholar 

  26. Pei S, Muchnik L, Andrade JS Jr, Zheng Z, Makse HA (2014) Searching for superspreaders of information in real-world social media. Sci Rep 4(1):5547. https://doi.org/10.1038/srep05547

    Article  MATH  Google Scholar 

  27. Berahmand K, Bouyer A, Samadi N (2018) A new centrality measure based on the negative and positive effects of clustering coefficient for identifying influential spreaders in complex networks. Chaos Solitons Fractals 110:41–54. https://doi.org/10.1016/j.chaos.2018.03.014

    Article  MATH  Google Scholar 

  28. Sheng J, Dai J, Wang B, Duan G, Long J, Zhang J, Guan K, Hu S, Chen L, Guan W (2020) Identifying influential nodes in complex networks based on global and local structure. Physica A 541:123262. https://doi.org/10.1016/j.physa.2019.123262

    Article  MATH  Google Scholar 

  29. Ullah A, Wang B, Sheng J, Long J, Khan N, Sun Z (2021) Identification of nodes influence based on global structure model in complex networks. Sci Rep 11(1):1–11. https://doi.org/10.1038/s41598-021-84684-x

    Article  MATH  Google Scholar 

  30. Wang M, Li W, Guo Y, Peng X, Li Y (2020) Identifying influential spreaders in complex networks based on improved k-shell method. Physica A 554:124229. https://doi.org/10.1016/j.physa.2020.124229

    Article  MATH  Google Scholar 

  31. Maji G, Mandal S, Sen S (2020) A systematic survey on influential spreaders identification in complex networks with a focus on k-shell based techniques. Expert Syst Appl 161:113681. https://doi.org/10.1016/j.eswa.2020.113681

    Article  MATH  Google Scholar 

  32. Nandi S, Malta MC, Maji G, Dutta A (2023) IS-PEW: identifying influential spreaders using potential edge weight in complex networks. In: International conference on complex networks and their applications. Springer, pp 309–320. https://doi.org/10.1007/978-3-031-53472-0_26

  33. Li Z, Huang X (2021) Identifying influential spreaders in complex networks by an improved gravity model. Sci Rep 11(1):22194. https://doi.org/10.1038/s41598-021-01218-1

    Article  MATH  Google Scholar 

  34. Ma L-L, Ma C, Zhang H-F, Wang B-H (2016) Identifying influential spreaders in complex networks based on gravity formula. Physica A 451:205–212. https://doi.org/10.1016/j.physa.2015.12.162

    Article  MATH  Google Scholar 

  35. Zareie A, Sheikhahmadi A, Jalili M, Fasaei MSK (2020) Finding influential nodes in social networks based on neighborhood correlation coefficient. Knowl Based Syst 194:105580. https://doi.org/10.1016/j.knosys.2020.105580

    Article  MATH  Google Scholar 

  36. Chen D-B, Gao H, Lü L, Zhou T (2013) Identifying influential nodes in large-scale directed networks: the role of clustering. PLoS ONE 8(10):77455

    Article  Google Scholar 

  37. Shang Q, Deng Y, Cheong KH (2021) Identifying influential nodes in complex networks: effective distance gravity model. Inf Sci 577:162–179. https://doi.org/10.1016/j.ins.2021.01.053

    Article  MathSciNet  MATH  Google Scholar 

  38. Daud NN, Ab Hamid SH, Saadoon M, Sahran F, Anuar NB (2020) Applications of link prediction in social networks: a review. J Netw Comput Appl 166:102716. https://doi.org/10.1016/j.jnca.2020.102716

    Article  Google Scholar 

  39. Kumar A, Singh SS, Singh K, Biswas B (2020) Link prediction techniques, applications, and performance: a survey. Physica A 553:124289. https://doi.org/10.1016/j.physa.2020.124289

    Article  MathSciNet  MATH  Google Scholar 

  40. Zhang J, Wang B, Sheng J, Dai J, Hu J, Chen L (2019) Identifying influential nodes in complex networks based on local effective distance. Information. https://doi.org/10.3390/info10100311

    Article  MATH  Google Scholar 

  41. Maji G, Namtirtha A, Dutta A, Curado Malta M (2020) Influential spreaders identification in complex networks with improved k-shell hybrid method. Expert Syst Appl 144:113092. https://doi.org/10.1016/j.eswa.2019.113092

    Article  Google Scholar 

  42. Lü L, Zhou T, Zhang Q-M, Stanley HE (2016) The h-index of a network node and its relation to degree and coreness. Nat Commun 7(1):10168. https://doi.org/10.1038/ncomms10168

    Article  MATH  Google Scholar 

  43. Hansen DL, Shneiderman B, Smith MA, Himelboim I (2020) Chapter 6—calculating and visualizing network metrics. In: Hansen DL, Shneiderman B, Smith MA, Himelboim I (eds) Analyzing social media networks with NodeXL, 2nd edn. Morgan Kaufmann, Burlington, pp 79–94. https://doi.org/10.1016/B978-0-12-817756-3.00006-6

    Chapter  Google Scholar 

  44. Chen D, Lü L, Shang M-S, Zhang Y-C, Zhou T (2012) Identifying influential nodes in complex networks. Physica A 391(4):1777–1787. https://doi.org/10.1016/j.physa.2011.09.017

    Article  MATH  Google Scholar 

  45. Li Z, Ren T, Ma X, Liu S, Zhang Y, Zhou T (2019) Identifying influential spreaders by gravity model. Sci Rep 9(1):1–7. https://doi.org/10.1038/s41598-019-44930-9

    Article  MATH  Google Scholar 

  46. Namtirtha A, Dutta A, Dutta B, Sundararajan A, Simmhan Y (2021) Best influential spreaders identification using network global structural properties. Sci Rep 11(1):1–15. https://doi.org/10.1038/s41598-021-81614-9

    Article  MATH  Google Scholar 

  47. Yang X-H, Xiong Z, Ma F, Chen X, Ruan Z, Jiang P, Xu X (2021) Identifying influential spreaders in complex networks based on network embedding and node local centrality. Physica A 573:125971. https://doi.org/10.1016/j.physa.2021.125971

    Article  Google Scholar 

  48. Ullah A, Wang B, Sheng J, Long J, Khan N, Sun Z (2021) Identifying vital nodes from local and global perspectives in complex networks. Expert Syst Appl 186:115778. https://doi.org/10.1016/j.eswa.2021.115778

    Article  MATH  Google Scholar 

  49. Liu F, Wang Z, Deng Y (2020) Gmm: a generalized mechanics model for identifying the importance of nodes in complex networks. Knowl Based Syst 193:105464. https://doi.org/10.1016/j.knosys.2019.105464

    Article  MATH  Google Scholar 

  50. Sotoodeh H, Falahrad M (2019) Relative degree structural hole centrality, CRD-SH: a new centrality measure in complex networks. J Syst Sci Complex 32:1306–1323. https://doi.org/10.1007/s11424-018-7331-5

    Article  MathSciNet  MATH  Google Scholar 

  51. Long H (2019) Edge intensity-based community measurement in complex networks. Phys Lett A 383(11):1167–1173. https://doi.org/10.1016/j.physleta.2019.01.022

    Article  MathSciNet  MATH  Google Scholar 

  52. Li M, Zhou S, Wang D, Chen G (2023) Identifying influential nodes based on resistance distance. J Comput Sci 67:101972. https://doi.org/10.1016/j.jocs.2023.101972

    Article  MATH  Google Scholar 

  53. Wang J-E, Liu S-Y, Aljmiai A, Bai Y-G (2021) Detection of influential nodes with multi-scale information. Chin Phys B 30(8):088902. https://doi.org/10.1088/1674-1056/abff2d

    Article  Google Scholar 

  54. Bai Y, Liu S, Li Q, Yuan J (2022) Cost-aware deployment of check-in nodes in complex networks. IEEE Trans Syst Man Cybern Syst 52(6):3378–3390. https://doi.org/10.1109/TSMC.2020.3034485

    Article  MATH  Google Scholar 

  55. Zhao G, Jia P, Huang C, Zhou A, Fang Y (2020) A machine learning based framework for identifying influential nodes in complex networks. IEEE Access 8:65462–65471. https://doi.org/10.1109/ACCESS.2020.2984286

    Article  MATH  Google Scholar 

  56. Asgharian Rezaei A, Munoz J, Jalili M, Khayyam H (2023) A machine learning-based approach for vital node identification in complex networks. Expert Syst Appl 214:119086. https://doi.org/10.1016/j.eswa.2022.119086

    Article  MATH  Google Scholar 

  57. Zhao G, Jia P, Zhou A, Zhang B (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

    Article  MATH  Google Scholar 

  58. Yu E-Y, Wang Y-P, Fu Y, Chen D-B, Xie M (2020) Identifying critical nodes in complex networks via graph convolutional networks. Knowl Based Syst 198:105893. https://doi.org/10.1016/j.knosys.2020.105893

    Article  Google Scholar 

  59. Huang H, Xie L, Liu M, Lin J, Shen H (2024) An embedding model for temporal knowledge graphs with long and irregular intervals. Knowl Based Syst 296:111893. https://doi.org/10.1016/j.knosys.2024.111893

    Article  MATH  Google Scholar 

  60. Yang X, Xiao F (2021) An improved gravity model to identify influential nodes in complex networks based on k-shell method. Knowl Based Syst 227:107198. https://doi.org/10.1016/j.knosys.2021.107198

    Article  MATH  Google Scholar 

  61. Wang F, Sun Z, Gan Q, Fan A, Shi H, Hu H (2022) Influential node identification by aggregating local structure information. Physica A 593:126885. https://doi.org/10.1016/j.physa.2022.126885

    Article  Google Scholar 

  62. Shetty RD, Bhattacharjee S, Dutta A, Namtirtha A (2023) GSI: an influential node detection approach in heterogeneous network using covid-19 as use case. IEEE Trans Comput Soc Syst 10(5):2489–2503. https://doi.org/10.1109/TCSS.2022.3180177

    Article  Google Scholar 

  63. Ullah A, Shao J, Yang Q, Khan N, Bernard CM, Kumar R (2023) LSS: a locality-based structure system to evaluate the spreader’s importance in social complex networks. Expert Syst Appl 228:120326. https://doi.org/10.1016/j.eswa.2023.120326

    Article  Google Scholar 

  64. Diop, M., Pham, C., Thiaré, O.: 2-Hop neighborhood information for cover set selection in mission-critical surveillance with wireless image sensor networks. In: 2013 IFIP wireless days (WD), pp 1–7 (2013). https://doi.org/10.1109/WD.2013.6686505

  65. Gao S, Ma J, Chen Z, Wang G, Xing C (2014) Ranking the spreading ability of nodes in complex networks based on local structure. Physica A 403:130–147. https://doi.org/10.1016/j.physa.2014.02.032

    Article  MATH  Google Scholar 

  66. Meghanathan N, Essien A, Lawrence R (2021) A two-hop neighbor preference-based random network graph model with high clustering coefficient for modeling real-world complex networks. Egypt Inform J 22(3):389–400. https://doi.org/10.1016/j.eij.2016.06.008

    Article  MATH  Google Scholar 

  67. Brockmann D, Helbing D (2013) The hidden geometry of complex, network-driven contagion phenomena. Science 342(6164):1337–1342. https://doi.org/10.1126/science.1245200

    Article  MATH  Google Scholar 

  68. Šubelj L, Bajec M (2011) Robust network community detection using balanced propagation. Eur Phys J B 81(3):353–362. https://doi.org/10.1140/epjb/e2011-10979-2

    Article  MATH  Google Scholar 

  69. Hopkin VD (2017) Human factors in air traffic control. CRC Press, Boca Raton, p 442. https://doi.org/10.1201/9780203751718

    Book  MATH  Google Scholar 

  70. Rossi R, Ahmed N (2015) The network data repository with interactive graph analytics and visualization. In: Proceedings of the AAAI conference on artificial intelligence, vol 29. https://doi.org/10.1609/aaai.v29i1.9277

  71. Bollacker KD, Lawrence S, Giles CL (1998) Citeseer: an autonomous web agent for automatic retrieval and identification of interesting publications. In: Proceedings of the second international conference on autonomous agents. Association for Computing Machinery, New York, pp 116–123. https://doi.org/10.1145/280765.280786

  72. Batagelj V, Mrvar A (2000) Some analyses of Erdos collaboration graph. Soc Netw 22(2):173–186. https://doi.org/10.1016/S0378-8733(00)00023-X

    Article  MathSciNet  MATH  Google Scholar 

  73. Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ networks. Nature 393(6684):440–442. https://doi.org/10.1038/30918

    Article  MATH  Google Scholar 

  74. Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data 1(1):2. https://doi.org/10.1145/1217299.1217301

    Article  MATH  Google Scholar 

  75. Pastor-Satorras R, Vespignani A (2001) Epidemic spreading in scale-free networks. Phys Rev Lett 86(14):3200. https://doi.org/10.1103/PhysRevLett.86.3200

    Article  MATH  Google Scholar 

  76. Kendall MG (1945) The treatment of ties in ranking problems. Biometrika 33(3):239–251. https://doi.org/10.2307/2332303

    Article  MathSciNet  MATH  Google Scholar 

  77. Madotto A, Liu J (2016) Super-spreader identification using meta-centrality. Sci Rep 6(1):1–10. https://doi.org/10.1038/srep38994

    Article  Google Scholar 

  78. Chen D, Lü L, Shang M-S, Zhang Y-C, Zhou T (2012) Identifying influential nodes in complex networks. Physica A 391(4):1777–1787. https://doi.org/10.1016/j.physa.2011.09.017

    Article  MATH  Google Scholar 

  79. Maji G (2020) Influential spreaders identification in complex networks with potential edge weight based k-shell degree neighborhood method. J Comput Sci 39:101055. https://doi.org/10.1016/j.jocs.2019.101055

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This work is financed by National Funds through the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia, within Project UIDB/50014/2020 DOI 10.54499/UIDB/50014/2020. This work is financed by the Erasmus + ICM (International Credit Mobility) program under the Project 2020-1-PT01-KA107-078161.

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, National Institute of Technology Durgapur, Durgapur, West Bengal, 713209, India

    Suman Nandi & Animesh Dutta

  2. Faculty of Engineering, INESC TEC, 4099-002, Porto, Portugal

    Mariana Curado Malta

  3. Department of Electrical Engineering, Asansol Polytechnic, Asansol, West Bengal, 713302, India

    Giridhar Maji

Authors
  1. Suman Nandi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mariana Curado Malta
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Giridhar Maji
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Animesh Dutta
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Suman Nandi.

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Nandi, S., Curado Malta, M., Maji, G. et al. IC-SNI: measuring nodes’ influential capability in complex networks through structural and neighboring information. Knowl Inf Syst 67, 1309–1350 (2025). https://doi.org/10.1007/s10115-024-02262-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10115-024-02262-9

Keywords

Search

Navigation