计算机工程与应用 ›› 2022, Vol. 58 ›› Issue (7): 77-86.DOI: 10.3778/j.issn.1002-8331.2103-0204

• 理论与研发 • 上一篇    下一篇

基于弹簧模型的重要节点排序算法

孟昱煜,王霄,闫光辉,罗浩,杨波,张磊,王琼   

  1. 1.兰州交通大学 电子与信息工程学院,兰州 730070 
    2.国网甘肃省电力公司信息通信公司,兰州 730070
  • 出版日期:2022-04-01 发布日期:2022-04-01

Ranking Algorithms of Vital Nodes Based on Spring Model

MENG Yuyu, WANG Xiao, YAN Guanghui, LUO Hao, YANG Bo, ZHANG Lei, WANG Qiong   

  1. 1.School of Electronics and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China
    2.State Grid Gansu Information & Telecommunication Company, Lanzhou 730070, China
  • Online:2022-04-01 Published:2022-04-01

摘要: 重要节点排序是复杂网络研究的重要问题。用网络的鲁棒性和脆弱性指标评价基于引力模型的重要节点排序算法GM(gravity model)和其局部算法LGM(local gravity model)时,当度大的节点从网络中移除后,其引力较大的近邻节点的后续移除通常并不能在很大程度上影响网络的结构与功能,说明算法在重要节点排序精度方面仍然存在提升之处。基于此,在弹簧模型的启发下,进一步考虑网络节点近邻和路径信息,并结合网络直径,提出了重要节点排序算法SM(spring model)和其局部算法LSM(local spring model)。基于合成网络和真实网络数据集针对网络的鲁棒性和脆弱性与经典算法进行对比实验,结果表明SM算法和LSM算法对于网络中重要节点排序具有更高的准确性。特别地,在Power网络上的SIR传播实验进一步证明了SM算法相较于其他算法,具有更高的合理性和有效性。

关键词: 重要节点, 复杂网络, 弹簧模型, SM算法, LSM算法

Abstract: Node ranking of vital nodes is an important problem in complex networks. When using the robustness and vulnerability of the network to evaluate the node ranking algorithms gravity model (GM) and local gravity model (LGM) based on the gravity model, once the nodes with large degrees have been removed from the network, the removal of neighbors with large gravitational values usually cannot largely affect the structure and function of the network, which shows that the algorithms still have some improvement in the ranking accuracy of vital nodes. Because of that, inspired by the spring model, further considering neighbors’ information and path information in the network, combined with the network diameter, spring model(SM) and local spring model(LSM), the node ranking algorithm and its local algorithm, are proposed. The results show that the SM algorithm and the LSM algorithm have higher accuracy for the ranking of vital nodes than other classical algorithms in synthetic networks and real networks. Especially, the SIR epidemic experiments on the Power network are conducted to furtherly verify the higher rationality and effectiveness of the SM algorithm than other algorithms.

Key words: vital nodes, complex networks, spring model, spring model(SM) algorithm, local spring model(LSM) algorithm