为解决许多关键节点识别算法在评估网络节点重要性时,忽视节点与其邻居节点间的相互关系,导致对网络鲁棒性和脆弱性的评估结果不准确的问题,提出一种改良的局部加权密度度量方式CPR-WCCN,旨在以较低的计算成本准确识别复杂网络中的关键...为解决许多关键节点识别算法在评估网络节点重要性时,忽视节点与其邻居节点间的相互关系,导致对网络鲁棒性和脆弱性的评估结果不准确的问题,提出一种改良的局部加权密度度量方式CPR-WCCN,旨在以较低的计算成本准确识别复杂网络中的关键节点.首先,借助节点间的最短路径长度和数量,定义节点间的通信概率序列.其次,通过结合通信概率和相对熵(Communication Probability and Relative Entropy,CPR),将传统的二元邻接矩阵转化为网络归一化相关矩阵.再次,结合加权聚类系数和邻居节点的影响(Weighted Clustering Coefficients and Neighbor Influence,WCCN),得到改进的考虑邻居影响的局部加权密度.最后,为验证CPRWCCN算法的效果,在故意攻击和随机攻击下进行模拟实验,利用传播模型在4种实际网络上对CPR-WCCN与其他5种算法进行对比分析.实验结果表明:当网络遭受故意攻击,导致前15个关键节点失效时,网络的连通性、效率、最大连接子图以及自然连通性等关键指标较随机攻击出现了更显著的下降;相较于其他5种算法,CPR-WCCN算法表现出最优的整体性能,能够准确且高效地识别出网络中的关键节点.展开更多
基于引力模型的关键节点识别方法是常见的一类识别方法,但该类方法存在以下两方面不足,一是衡量节点“质量”时考虑的因素单一,二是所需的运行时间代价较高。通过优化这两方面不足,本文提出了一种改进的引力模型识别方法。首先,综合考...基于引力模型的关键节点识别方法是常见的一类识别方法,但该类方法存在以下两方面不足,一是衡量节点“质量”时考虑的因素单一,二是所需的运行时间代价较高。通过优化这两方面不足,本文提出了一种改进的引力模型识别方法。首先,综合考虑节点的度、H指数中心性和聚类系数以衡量节点“质量”,并利用信息熵对节点“质量”进行区分。然后,重新考虑节点的影响范围以减少所提方法的运行时间代价。最后,将本文提出的方法与六种基准方法在八个数据集上进行比较。实验结果表明,本文提出的方法在单调性、鲁棒性和准确性方面均表现出明显优势。与基于引力模型的识别方法相比,本文提出方法的运行时间可以降低18.97%~87.65%。The key node identification method based on gravity model is a common type of identification method, but this type of method has the following two shortcomings: the first is the single factor considered when measuring “mass” of the node;the second is the high cost of required running time. Therefore, this paper proposes an improved gravity model identification method by optimizing these two shortcomings. Initially, “mass” of the node is measured by comprehensively considering the degree, the H-index centrality and the clustering coefficient, and the information entropy is used to distinguish “mass” of the node. Then, the influence range of the node is being reconsidered to reduce the runtime cost of the proposed method. Finally, the method proposed in this paper is compared with six benchmark methods on eight datasets. Experimental results show that the proposed method has obvious advantages in monotonicity, robustness and accuracy. The running time of the proposed method in this paper can be reduced by 18.97% - 87.65% compared with the identification method based on the gravity model.展开更多
识别复杂网络中的关键节点对促进信息传播、阻断谣言传播、管理交通运输和预防电网灾难性破坏等都具有很强的理论意义和应用价值。在对现有关键节点识别算法的研究分析基础上,受K-shell分解方法和重力模型的启发,本文提出了一种基于邻...识别复杂网络中的关键节点对促进信息传播、阻断谣言传播、管理交通运输和预防电网灾难性破坏等都具有很强的理论意义和应用价值。在对现有关键节点识别算法的研究分析基础上,受K-shell分解方法和重力模型的启发,本文提出了一种基于邻域中心性和重力模型的改进算法NCGM。NCGM算法不仅考虑了节点与处于核心位置节点之间的连接程度,还考虑了节点与其他节点之间的最短路径长度。为了评估所提出的NCGM算法,本文在7个常用数据集上使用易感–感染–恢复(SIR)传播动力学模型进行了实验仿真,将所提出的NCGM算法和5个对比算法的传播范围和肯德尔相关系数进行了比较分析。实验结果表明,所提出的NCGM算法能够更准确地识别不同类型网络中的关键节点。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.展开更多
文摘为解决许多关键节点识别算法在评估网络节点重要性时,忽视节点与其邻居节点间的相互关系,导致对网络鲁棒性和脆弱性的评估结果不准确的问题,提出一种改良的局部加权密度度量方式CPR-WCCN,旨在以较低的计算成本准确识别复杂网络中的关键节点.首先,借助节点间的最短路径长度和数量,定义节点间的通信概率序列.其次,通过结合通信概率和相对熵(Communication Probability and Relative Entropy,CPR),将传统的二元邻接矩阵转化为网络归一化相关矩阵.再次,结合加权聚类系数和邻居节点的影响(Weighted Clustering Coefficients and Neighbor Influence,WCCN),得到改进的考虑邻居影响的局部加权密度.最后,为验证CPRWCCN算法的效果,在故意攻击和随机攻击下进行模拟实验,利用传播模型在4种实际网络上对CPR-WCCN与其他5种算法进行对比分析.实验结果表明:当网络遭受故意攻击,导致前15个关键节点失效时,网络的连通性、效率、最大连接子图以及自然连通性等关键指标较随机攻击出现了更显著的下降;相较于其他5种算法,CPR-WCCN算法表现出最优的整体性能,能够准确且高效地识别出网络中的关键节点.
文摘基于引力模型的关键节点识别方法是常见的一类识别方法,但该类方法存在以下两方面不足,一是衡量节点“质量”时考虑的因素单一,二是所需的运行时间代价较高。通过优化这两方面不足,本文提出了一种改进的引力模型识别方法。首先,综合考虑节点的度、H指数中心性和聚类系数以衡量节点“质量”,并利用信息熵对节点“质量”进行区分。然后,重新考虑节点的影响范围以减少所提方法的运行时间代价。最后,将本文提出的方法与六种基准方法在八个数据集上进行比较。实验结果表明,本文提出的方法在单调性、鲁棒性和准确性方面均表现出明显优势。与基于引力模型的识别方法相比,本文提出方法的运行时间可以降低18.97%~87.65%。The key node identification method based on gravity model is a common type of identification method, but this type of method has the following two shortcomings: the first is the single factor considered when measuring “mass” of the node;the second is the high cost of required running time. Therefore, this paper proposes an improved gravity model identification method by optimizing these two shortcomings. Initially, “mass” of the node is measured by comprehensively considering the degree, the H-index centrality and the clustering coefficient, and the information entropy is used to distinguish “mass” of the node. Then, the influence range of the node is being reconsidered to reduce the runtime cost of the proposed method. Finally, the method proposed in this paper is compared with six benchmark methods on eight datasets. Experimental results show that the proposed method has obvious advantages in monotonicity, robustness and accuracy. The running time of the proposed method in this paper can be reduced by 18.97% - 87.65% compared with the identification method based on the gravity model.
文摘识别复杂网络中的关键节点对促进信息传播、阻断谣言传播、管理交通运输和预防电网灾难性破坏等都具有很强的理论意义和应用价值。在对现有关键节点识别算法的研究分析基础上,受K-shell分解方法和重力模型的启发,本文提出了一种基于邻域中心性和重力模型的改进算法NCGM。NCGM算法不仅考虑了节点与处于核心位置节点之间的连接程度,还考虑了节点与其他节点之间的最短路径长度。为了评估所提出的NCGM算法,本文在7个常用数据集上使用易感–感染–恢复(SIR)传播动力学模型进行了实验仿真,将所提出的NCGM算法和5个对比算法的传播范围和肯德尔相关系数进行了比较分析。实验结果表明,所提出的NCGM算法能够更准确地识别不同类型网络中的关键节点。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.
