LCD: IDENTIFYING INFLUENTIAL NODES IN COMPLEX NETWORKS WITH LAYERED CLUSTERING AND DEGREE
DOI:
https://doi.org/10.25271/sjuoz.2025.13.2.1483Keywords:
Complex Networks, Influential Nodes, SIR Model, Layered Clustering, DegreeAbstract
Identifying influential nodes in networks is a key challenge in understanding how information spreads. While numerous algorithms have been proposed in the literature, many struggle with either limited spreading efficiency or high computational complexity. To address this challenge, we present Layered Clustering Degree (LCD), an effective method for identifying a set of well-distributed spreaders with high spreading ability, while maintaining a computational complexity of making it highly suitable for large-scale networks where both efficiency and computational complexity are essential. The LCD approach operates in three main steps: (1) Layering, which organizes nodes hierarchically based on their shortest distances from a designated starting node; (2) Clustering, which groups nodes within each layer into connected substructures to capture local connectivity patterns; and (3) Degree computation and ranking, where node degrees are computed within the entire network (globally) but ranked iteratively across clusters (locally) to ensure maximum coverage and minimal overlap among selected spreaders. The significance of layered clustering in LCD method, is iteratively distributing spreaders across clusters to avoid over-representation of high-degree nodes from a single region of the network. Experimental results using the SIR model on nine real-world networks show that LCD outperforms several popular methods, including VoteRank, K-shell, VoteRank++, ClusterRank, H-Index, EnRenew, and DegreeRank, in terms of spreading rate and final affected scale
References
R. M. Anderson and R. M. May. Infectious diseases of humans: dynamics and control. Oxford university press, 1991. DOI: https://DOI.org/10.1093/oso/9780198545996.001.0001.
J. Bae and S. Kim. Identifying and ranking influential spreaders in complex networks by neighborhood coreness. Physica A: Statistical Mechanics and its Applications, 395:549–559, 2014. DOI: https://DOI.org/10.1016/j.physa.2013.10.047.
A. Buscarino, L. Fortuna, M. Frasca, and V. Latora. Disease spreading in populations of moving agents. Europhysics Letters, 82(3):38002, 2008. DOI: https://DOI.org/10.1209/02955075/82/38002.
C. Castellano and R. Pastor-Satorras. Thresholds for epidemic spreading in networks. Physical review letters, 105(21):218701, 2010. DOI: https://DOI.org/10.1103/PhysRevLett.105.218701.
D. Centola. The spread of behavior in an online social network experiment. science, 329(5996):1194–1197, 2010. DOI: https://DOI.org/10.1126/science.1185231.
D. Chen, L. L¨u, M.-S. Shang, Y.-C. Zhang, and T. Zhou. Identifying influential nodes in complex networks. Physica a: Statistical mechanics and its applications, 391(4):1777–1787, 2012. DOI: https://DOI.org/10.1016/j.physa.2011.09.017.
D.-B. Chen, H. Gao, L. L¨u, and T. Zhou. Identifying influential nodes in largescale directed networks: the role of clustering. PloS one, 8(10):e77455, 2013. DOI: https://DOI.org/10.1 371/journal.pone.0077455.
D.-B. Chen, R. Xiao, and A. Zeng. Predicting the evolution of spreading on complex networks. Scientific reports, 4(1):6108, 2014. DOI: https://DOI.org/10.1038/srep06108.
W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 199–208, 2009. DOI: https://DOI.org/10.1145/1557019.1557047.
V. Chepoi and F. Dragan. A note on distance approximating trees in graphs. European Journal of Combinatorics, 21(6):761–766, 2000. DOI: https://DOI.org/10.1006/eujc.1999.0381.
DIMACS. The center for discrete mathematics and theoretical computer science. Available at: https://sites.cc.gatech.edu/dimacs
/archive/clustering.shtml.
L. C. Freeman. A set of measures of centrality based on betweenness. Sociometry, pages 35–41, 1977. DOI: https://DOI.org/10.2307/3033543.
L. C. Freeman et al. Centrality in social networks: Conceptual clarification. Social network: critical concepts in sociology. Londres: Routledge, 1:238–263, 2002. DOI: https://DOI.org/10.1016/0378-8733(78)90021-7.
C. Guo, L. Yang, X. Chen, D. Chen, H. Gao, and J. Ma. Influential nodes identification in complex networks via information entropy. Entropy, 22(2): 242, 2020. DOI: https://doi
.org/10.3390/e22020242.
H. W. Hethcote. The mathematics of infectious diseases. SIAM review, 42(4): 599–653, 2000. DOI:https://DOI.org/10.1137/S0036144500371907.
Z.-L. Hu, J.-G. Liu, G.-Y. Yang, and Z.-M. Ren. Effects of the distance among multiple spreaders on the spreading. Europhysics Letters, 106(1):18002, 2014. DOI: https://DOI.org/10.1209/0295-5075/106/18002.
L. Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39–43, 1953. DOI: https://DOI.org/10.1007/BF02289026.
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. Nature physics, 6(11):888–893, 2010. DOI: https://DOI.org/10.1038/nphys1746.
S. Kumar and B. Panda. Identifying influential nodes in social networks: Neighborhood coreness based voting approach. Physica A: Statistical Mechanics and its Applications, 553:124215, 2020. DOI: https://DOI.org/10.1016/j.physa.2020.124215.
J. Kunegis. Konect: the koblenz network collection. In Proceedings of the 22nd international conference on world wide web, pages 1343–1350, 2013. Available at: http://konect.cc/networks/.
P. Liu, L. Li, S. Fang, and Y. Yao. Identifying influential nodes in social networks: A voting approach. Chaos, Solitons & Fractals, 152:111309, 2021. DOI: https://DOI.org/10.1016/j.chaos.2021.111309.
Y. Liu, M. Tang, T. Zhou, and Y. Do. Identify influential spreaders in complex networks, the role of neighborhood. Physica A: Statistical Mechanics and its Applications, 452:289–298, 2016. DOI: https://DOI.org/10.1016/j.physa.2016.02.028.
L. L¨u, D.-B. Chen, and T. Zhou. The small world yields the most effective information spreading. New Journal of Physics, 13(12):123005, 2011. DOI: https://dx.DOI.org/10.1088/1367-2630/13/12/123005.
L. L¨u, T. Zhou, Q.-M. Zhang, and H. E. Stanley. The h-index of a network node and its relation to degree and coreness. Nature communications, 7(1): 10168, 2016. DOI: https://DOI.org/10.1038/ncomms10168.
T. Ouboter, R. Meester, and P. Trapman. Stochastic sir epidemics in a population with households and schools. Journal of Mathematical Biology, 72(5): 1177–1193, 2016. DOI: https://DOI.org/10.1007/s00285-015-0901-4.
R. Pastor-Satorras and A. Vespignani. Epidemic spreading in scale-free networks. Physical review letters, 86(14):3200, 2001. DOI: https://DOI.org/10.1103/PhysRevLett.86.3200.
R. Pastor-Satorras, C. Castellano, P. Van Mieghem, and A. Vespignani. Epidemic processes in complex networks. Reviews of modern physics, 87(3): 925–979, 2015. DOI: https://DOI.org/10.1103/RevModPhys.87.925.
G. Sabidussi. The centrality index of a graph. Psychometrika, 31(4):581–603, 1966. DOI: https://Doi.org/10.1007/BF02289527.
A. Sheikhahmadi and M. A. Nematbakhsh. Identification of multi-spreader users in social networks for viral marketing. Journal of Information Science, 43(3): 412–423, 2017. DOI: https://DOI.org/10.1177/0165551516644171.
Stanford Large Network Dataset Collection (SNAP). Stanford large network dataset. Available at: http://snap.stanford.edu/data/index.html.
Z. Tao, F. Zhongqian, and W. Binghong. Epidemic dynamics on complex networks. Progress in Natural Science, 16(5):452–457, 2006. DOI: https://DOI.org/10.1080/10020070612330019.
F. Wang, Z. Sun, Q. Gan, A. Fan, H. Shi, and H. Hu. Influential node identification by aggregating local structure information. Physica A: Statistical Mechanics and its Applications, 593:126885, 2022. DOI: https://DOI.org/10.1016/j.physa.2022.126885.
G. Wang, S. B. Alias, Z. Sun, F. Wang, A. Fan, and H. Hu. Influential nodes identification method based on adaptive adjustment of voting ability. Heliyon, 9(5), 2023. DOI: https://DOI.org/10.1016/j.heliyon.2023.e16112.
G. Xu and C. Dong. Cagm: A communicability-based adaptive gravity model for influential nodes identification in complex networks. Expert Systems with Applications, 235:121154, 2024. DOI: https://DOI.org/10.1016/j.eswa.2023.121154.
Q. Yang, Y. Wang, S. Yu, and W. Wang. Identifying influential nodes through an improved k-shell iteration factor model. Expert Systems with Applications, 238:122077, 2024. DOI: https://DOI.org/10.1016/j.eswa.2023.122077.
X. Yang and F. Xiao. An improved gravity model to identify influential nodes in complex networks based on k-shell method. Knowledge-Based Systems, 227: 107198, 2021. DOI: https://DOI.org/10.1016/j.knosys.2021.107198.
A. Zeng and C.-J. Zhang. Ranking spreaders by decomposing complex networks. Physics letters A, 377(14):1031–1035, 2013. DOI: https://DOI.org/10.1016/j.physleta.2013.02.039.
J.-X. Zhang, D.-B. Chen, Q. Dong, and Z.-D. Zhao. Identifying a set of influential spreaders in complex networks. Scientific reports, 6(1):27823, 2016. DOI: https://doi.org/10.1038/srep27823.
L. Zhao, H. Cui, X. Qiu, X. Wang, and J. Wang. Sir rumor spreading model in the new media age. Physica A: Statistical Mechanics and its Applications, 392(4):995–1003, 2013. DOI: https://DOI.org/10.1016/j.physa.2012.09.030.
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 Systems, 260:110163, 2023. DOI: https://DOI.org/10.1016/j.knosys.2022.110163
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Abdulhakeem Othman Mohammed
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License [CC BY-NC-SA 4.0] that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work, with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online.
