基于邻域中心性和重力模型的关键节点识别算法

Key Node Identification Algorithm Based on Neighborhood Centrality and Gravity Model

摘要: 识别复杂网络中的关键节点对促进信息传播、阻断谣言传播、管理交通运输和预防电网灾难性破坏等都具有很强的理论意义和应用价值。在对现有关键节点识别算法的研究分析基础上，受K-shell分解方法和重力模型的启发，本文提出了一种基于邻域中心性和重力模型的改进算法NCGM。NCGM算法不仅考虑了节点与处于核心位置节点之间的连接程度，还考虑了节点与其他节点之间的最短路径长度。为了评估所提出的NCGM算法，本文在7个常用数据集上使用易感–感染–恢复(SIR)传播动力学模型进行了实验仿真，将所提出的NCGM算法和5个对比算法的传播范围和肯德尔相关系数进行了比较分析。实验结果表明，所提出的NCGM算法能够更准确地识别不同类型网络中的关键节点。

Abstract: Identifying key nodes in complex networks has strong theoretical significance and practical value in promoting information dissemination, blocking rumor spread, managing transportation, and preventing catastrophic damage to the power grid. Based on the analysis and research of existing key node recognition algorithms, inspired by the K-shell decomposition method and gravity model, this article proposes an improved algorithm NCGM based on neighborhood centrality and gravity model. The NCGM algorithm not only considers the degree of connection between nodes and nodes at the core position, but also takes into account the shortest path distance between nodes and other nodes. To evaluate the proposed NCGM algorithm, this article conducted experimental simulations using the Susceptible-Infected-Recovered (SIR) propagation dynamics model on seven commonly used datasets, and compared and analyzed the propagation range and Knedall’s tau correlation coefficient of the proposed NCGM algorithm with five existing algorithms. The experimental results show that the proposed NCGM algorithm can more accurately identify key nodes in different types of networks.