Key Nodes Identification Method Based on Neighborhood K-shell Distribution

doi:10.3778/j.issn.1002-8331.2305-0181

Abstract

Abstract: Accurate identification of key nodes in complex networks plays a crucial role in network structure stability and information dissemination. The traditional K-shell algorithm only evaluates the importance of nodes’ location, resulting in low differentiation. Considering the influence of global information and local information of nodes comprehensively, an identification algorithm of key nodes based on the K-shell distribution of neighborhood is proposed. The entropy of the node is defined by the [Ks] value of neighborhood to reflect the K-shell distribution characteristics of the neighbors. The results on 11 network datasets demonstrate the accuracy of proposed method.

Key words: complex network, key nodes, K-shell, susceptible-infected-recovered (SIR) model

摘要： 复杂网络中关键节点的精准识别对于网络结构稳定和信息传播起着至关重要的作用。传统K-shell方法仅通过节点在网络中所处位置对节点的重要性进行评估，导致区分度不高。基于此，综合考虑了节点的全局信息和局部信息对节点重要性的影响，提出一种基于邻域K-shell分布的关键节点识别方法。该方法通过节点邻域[Ks]值定义节点的熵，从而反映邻居节点的K-shell分布特征。通过11个网络数据集上的仿真实验，验证了所提方法能够更准确地识别并区分复杂网络中的关键节点。

关键词: 复杂网络, 关键节点, K-shell, 易感-感染-恢复模型（SIR）

WU Yali, REN Yuanguang, DONG Ang, ZHOU Aoran, WU Xuejin, ZHENG Shuailong. Key Nodes Identification Method Based on Neighborhood K-shell Distribution[J]. Computer Engineering and Applications, 2024, 60(2): 87-95.

吴亚丽, 任远光, 董昂, 周傲然, 吴学金, 郑帅龙. 基于邻域K-shell分布的关键节点识别方法[J]. 计算机工程与应用, 2024, 60(2): 87-95.

References

[1] 任晓龙, 吕琳媛. 网络重要节点排序方法综述[J]. 科学通报, 2014, 59(13): 1175-1197.
REN X L, LYU L Y. Review of ranking nodes in complex networks[J]. Chinese Science Bulletin, 2014, 59(13): 1175-1197.
[2] 郭明健, 高岩. 基于复杂网络理论的电力网络抗毁性分析[J]. 复杂系统与复杂性科学, 2022, 19(4): 1-6.
GUO M J, GAO Y. Invulnerability analysis of power network based on complex network[J]. Complex Systems and Complexity Science, 2022, 19(4): 1-6.
[3] 董昂, 吴亚丽, 任远光, 等. 基于局部熵的级联故障模型初始负载定义方式[J/OL]. 复杂系统与复杂性科学: 1-10[2023-06-13]. http://kns.cnki.net/kcms/detail/37.1402.N.20230413.2027.
010.html.
DONG A, WU Y L, REN Y G, et al. Initial load definition of cascading failure model based on local entropy[J]. Complex Systems and Complexity Science: 1-10[2023-06-13]. http://kns.cnki.net/kcms/detail/37.1402.N.20230413.2027.010.html.
[4] 赖强, 张宏昊, 王徐盱. 基于复杂网络理论的城市公交网络鲁棒性分析与优化[J]. 计算机工程与应用, 2022, 58(10): 249-254.
LAI Q, ZHANG H H, WANG X X. Robustness analysis and optimization of urban public transport network based on complex network theory[J]. Computer Engineering and Applications, 2022, 58(10): 249-254.
[5] 杨景峰, 朱大鹏, 赵瑞琳. 城市轨道交通网络特性与级联失效鲁棒性分析[J]. 计算机工程与应用, 2022, 58(7): 250-258.
YANG J F, ZHU D P, ZHAO R L. Analysis on characteristics of urban rail transit network and robustness of cascading failure[J]. Computer Engineering and Applications, 2022, 58(7): 250-258.
[6] SATORRAS P R, VESPIGNI A. Immunization of complex networks[J]. Physical Review E, 2002, 65(3): 036104.
[7] COHEN R, HAVLIN S, BEN-AVRAHAM D. Efficient immunization strategies for computer networks and populations[J]. Physical Review Letters, 2003, 91(24): 247901.
[8] FREEMAN L C. Centrality in social networks conceptual clarification[J]. Social Network, 1978, 1: 215.
[9] BONACICH P, LLOYD P. Eigenvector-like measures of centrality for asymmetric relations[J]. Social Networks, 2001, 23(3): 191-201.
[10] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35-41.
[11] SABIDUSSI G. The centrality index of a graph[J]. Psychometrika, 1966, 31(4): 581-603.
[12] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893.
[13] ZENG A, ZHANG C J. Ranking spreaders by decomposing complex networks[J]. Physics Letters A, 2013, 377(14): 1031-1035.
[14] BAE J, KIM S. Identifying and ranking influential spreaders in complex networks by neighborhood coreness[J]. Physica A, 2014, 395: 549-559.
[15] WANG Z, ZHAO Y, XI J, et al. Fast ranking influential nodes in complex networks using a k-shell iteration factor[J]. Physica A, 2016, 461: 171-181.
[16] 朱晓霞, 胡小雪. 基于改进k-shell算法的节点影响力的识别[J]. 计算机工程与应用, 2019, 55(1): 35-41.
ZHU X X, HU X X. Identification of node influence based on improved k-shell algorithm[J]. Computer Engineering and Applications, 2019, 55(1): 35-41.
[17] QIU L, ZHANG J, TIAN X. Ranking influential nodes in complex networks based on local and global structures[J]. Applied Intelligence, 2021, 51: 4394-4407.
[18] LAI Q, ZHANG H H. Analysis of identification methods of key nodes in transportation network[J]. Chinese Physics B, 2022, 31(6): 068905.
[19] PASTOR-SATORRAS R, VESPIGNANI A. Epidemic spreading in scale-free networks[J]. Physical Review Letters, 2001, 86(14): 3200.
[20] NEWMAN M E J. Spread of epidemic disease on networks[J]. Physical Review E, 2002, 66(1): 016128.
[21] CASTELLANO C, PASTOR-SATORRAS R. Thresholds for epidemic spreading in networks[J]. Physical Review Letters, 2010, 105(21): 218701.
[22] LYU L, CHEN D, REN X L, et al. Vital nodes identification in complex networks[J]. Physics Reports, 2016, 650: 1-63.
[23] SHANNON C E. A mathematical theory of communication[J]. The Bell System Technical Journal, 1948, 27(3): 379-423.
[24] GAO S, MA J, CHEN Z, et al. Ranking the spreading ability of nodes in complex networks based on local structure[J]. Physica A: Statistical Mechanics and Its Applications, 2014, 403: 130-147.
[25] 孙百兵, 孙家政, 何泉, 等. 融入社区评估的节点重要性分析[J]. 计算机工程与应用, 2023, 59(3): 226-233.
SUN B B, SUN J Z, HE Q, et al. Node importance analysis integrated with community assessment[J]. Computer Engineering and Applications, 2023, 59(3): 226-233.
[26] 钱榕, 王嘉瑞, 邢方远, 等. 基于传播属性的社交网络重要节点发现[J]. 计算机工程与应用, 2022, 58(16): 184-193.
QIAN R, WANG J R, XING F Y, et al. Discovering critical nodes of social networks based on propagation features[J]. Computer Engineering and Applications, 2022, 58(16): 184-193.
[27] ZAREIE A, SHEIKHAHMADI A, FATEMI A. Influential nodes ranking in complex networks: an entropy-based approach[J]. Chaos, Solitons & Fractals, 2017, 104: 485-494.
[28] ZHU T, WANG B, WU B, et al. Maximizing the spread of influence ranking in social networks[J]. Information Sciences, 2014, 278: 535-544.