Key node recognition in complex networks based on the K-shell method
XIE Lixia1, SUN Honghong1, YANG Hongyu1,2, ZHANG Liang3
1. College of Computer Science and Technology, Civil Aviation University of China, Tianjin 300300, China; 2. College of Safety Science and Engineering, Civil Aviation University of China, Tianjin 300300, China; 3. College of Information, University of Arizona, Tucson 85721, USA
Abstract：Key node recognition methods for complex networks often have insufficient resolution and accuracy. This study developed a K-shell based key node recognition method for complex networks that first stratifies the network to obtain the K-shell (Ks) values for each node that indicate the influence of the global structure of the complex network. A comprehensive degree (CD) was then defined that balances the various influences of neighboring nodes and sub-neighboring nodes. A dynamic adjustable influence coefficient, μi, was also defined. Nodes with the same Ks but larger comprehensive degrees are more important. Tests show that this method more effectively identifies key nodes than several classical key node recognition methods and a risk assessment method, and has high accuracy and resolution in different complex networks. This method provides network node risk assessments that can be used to protect important nodes and to determine the risk disposal priority of the network nodes.
谢丽霞, 孙红红, 杨宏宇, 张良. 基于K-shell的复杂网络关键节点识别方法[J]. 清华大学学报（自然科学版）, 2022, 62(5): 849-861.
XIE Lixia, SUN Honghong, YANG Hongyu, ZHANG Liang. Key node recognition in complex networks based on the K-shell method. Journal of Tsinghua University(Science and Technology), 2022, 62(5): 849-861.
[1] YU E Y, FU Y, TANG Q, et al. A re-ranking algorithm for identifying influential nodes in complex networks[J]. IEEE Access, 2020, 8:211281-211290. [2] YAN X L, CUI Y P, NI S J. Identifying influential spreaders in complex networks based on entropy weight method and gravity law[J]. Chinese Physics B, 2020, 29(4):048902. [3] ULLAH A, WANG B, SHENG J F, et al. Identification of influential nodes via effective distance-based centrality mechanism in complex networks[J]. Complexity, 2021, 2021:8403738. [4] QIU L Q, ZHANG J Y, TIAN X B. Ranking influential nodes in complex networks based on local and global structures[J]. Applied Intelligence, 2021, 51(7):4394-4407. [5] LIU J G, REN Z M, GUO Q. Ranking the spreading influence in complex networks[J]. Physica A:Statistical Mechanics and its Applications, 2013, 392(18):4154-4159. [6] ZENG A, ZHANG C J. Ranking spreaders by decomposing complex networks[J]. Physics Letters A, 2013, 377(14):1031-1035. [7] NAMTIRTHA A, DUTTA A, DUTTA B. Weighted K-shell degree neighborhood:A new method for identifying the influential spreaders from a variety of complex network connectivity structures[J]. Expert Systems with Applications, 2020, 139:112859. [8] BERAHMAND K, BOUYER A, SAMADI N. A new local and multidimensional ranking measure to detect spreaders in social networks[J]. Computing, 2019, 101(11):1711-1733. [9] BAE J, KIM S. Identifying and ranking influential spreaders in complex networks by neighborhood coreness[J]. Physica A:Statistical Mechanics and its Applications, 2014, 395:549-559. [10] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11):888-893. [11] IBNOULOUAFI A, EL HAZITI M, CHERIFI H. M-centrality:Identifying key nodes based on global position and local degree variation[J]. Journal of Statistical Mechanics:Theory and Experiment, 2018, 2018(7):073407. [12] MAJI G. Influential spreaders identification in complex networks with potential edge weight based K-shell degree neighborhood method[J]. Journal of Computational Science, 2020, 39:101055. [13] MAJI G, MANDAL S, SEN S. A systematic survey on influential spreaders identification in complex networks with a focus on K-shell based techniques[J]. Expert Systems with Applications, 2020, 161:113681. [14] ZHANG D Y, WANG Y, ZHANG Z X. Identifying and quantifying potential super-spreaders in social networks[J]. Scientific Reports, 2019, 9(1):14811. [15] 中华人民共和国国家质量监督检验检疫总局, 中国国家标准化管理委员会. 信息安全技术信息安全风险评估规范:GB/T 20984-2007[S]. 北京:中国标准出版社, 2007. General Administration of Quality Supervision, Inspection and Quarantine of the People's Republic of China, Standardization Administration of the People's Republic of China. Information security technology-Risk assessment specification for information security:GB/T 20984-2007[S]. Beijing:Standards Press of China, 2007. (in Chinese) [16] 彭俊好, 徐国爱, 杨义先, 等. 基于效用的安全风险度量模型[J]. 北京邮电大学学报, 2006, 29(2):59-61, 69. PENG J H, XU G A, YANG Y X, et al. Measure model of security risk based on utility[J]. Journal of Beijing University of Posts and Telecommunications, 2006, 29(2):59-61, 69. (in Chinese)
2022, Vol. 62 
