摘要：

关键节点识别已经成为复杂网络领域的一个重要研究范畴, 但目前关键节点识别方法存在时间复杂度较高、得到的关键节点集不够准确以及节点中心性指标考虑不够充分等问题。基于此, 提出一种基于层级划分和节点特征的关键节点识别框架, 在该框架内, 为避免选取节点初始覆盖集时效率低下的问题, 提出一种基于层级划分的关键节点初始覆盖集选取方法, 该方法可在线性时间内计算出初始节点覆盖集, 随后通过节点中心性指标向原网络中回添节点, 直到解集中的节点数满足预定义阈值数。为解决回添节点过程中易陷于局部最优解的问题, 综合考虑网络拓扑结构和节点的多种属性, 提出一种节点综合特征的中心性指标。对比5种初始覆盖集选取算法以及5个中心性指标, 在真实网络上进行方法的应用和分析, 结果表明, 所提基于层级划分和节点特征的方法能够在不同类型的网络中更准确有效地识别关键节点, 且该方法的鲁棒性更好, 性能也优于其他方法。

关键词: 复杂网络, 关键节点, 层级划分, 节点中心性, 节点特征

Abstract:

Critical node detection has become an important research domain in complex networks; however, current critical node detection methods suffer from high algorithm time complexity, inaccurate critical node sets obtained, and insufficient consideration of node centrality indicators. Based on this, this study first presents a critical node-detection framework based on layer and node features. This framework introduces a layer-partitioning-based method to enhance the efficiency of selecting the initial coverage set of critical nodes, allowing for the calculation of the initial node set in linear time. Subsequently, the nodes were added back to the original network through node centrality feature indicators until the number of nodes in the solution set met a predefined threshold. To overcome the challenge of local optima during node re-addition, a node centrality index was developed, taking into account the network topology and various node attributes. Experimental results from real networks, after comparing five initial coverage set selection algorithms and five centrality indices, indicate that the proposed method, utilizing layer partitioning and node features, offers more accurate and efficient detection of critical nodes in different network types with enhanced robustness and performance over existing methods.

Key words: complex network, key node, layer partitioning, node centrality, node feature