基于K-shell的复杂网络关键节点识别方法  

Key node recognition in complex networks based on the K-shell method

作　　者：谢丽霞[1] 孙红红 杨宏宇[1,2] 张良 XIE Lixia;SUN Honghong;YANG Hongyu;ZHANG Liang(College of Computer Science and Technology,Civil Aviation University of China,Tianjin 300300,China;College of Safety Science and Engineering,Civil Aviation University of China,Tianjin 300300,China;College of Information,University of Arizona,Tucson 85721,USA)

机构地区：[1]中国民航大学计算机科学与技术学院,天津300300 [2]中国民航大学安全科学与工程学院,天津300300 [3]亚利桑那大学信息学院,图森85721

出　　处：《清华大学学报（自然科学版）》2022年第5期849-861,共13页Journal of Tsinghua University(Science and Technology)

基　　金：国家自然科学基金民航联合研究项目(U1833107)。

摘　　要：针对复杂网络中关键节点识别方法的分辨率和准确性不足的问题,该文提出了一种基于K-shell的复杂网络关键节点识别方法(K-shell based key node recognition method, KBKNR)。首先,采用K-shell方法将网络分层,获取每个节点的K壳(K-shell,K_(s))值,通过K_(s)值衡量复杂网络全局结构的影响。其次,提出综合度(comprehensive degree, CD)的概念,并设定可动态调整的影响系数μ_(i),通过平衡邻居节点和次邻居节点的不同影响程度,获取每个节点的综合度。在该方法中,当节点K_(s)值相同时,综合度较大的节点更重要。对比几种经典关键节点识别方法和一种风险评估方法,实验结果表明,该方法能够有效识别关键节点,在不同复杂网络中具有较高的准确率和分辨率。除此之外,KBKNR方法可以为网络节点的风险评估、重要节点保护和网络中节点的风险处置优先级排序提供依据。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(K_(s)) 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 K_(s)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 综合度 邻居节点 节点重要性 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]