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

doi:10.3778/j.issn.1002-8331.2103-0204

摘要/Abstract

摘要： 重要节点排序是复杂网络研究的重要问题。用网络的鲁棒性和脆弱性指标评价基于引力模型的重要节点排序算法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

孟昱煜, 王霄, 闫光辉, 罗浩, 杨波, 张磊, 王琼. 基于弹簧模型的重要节点排序算法[J]. 计算机工程与应用, 2022, 58(7): 77-86.

MENG Yuyu, WANG Xiao, YAN Guanghui, LUO Hao, YANG Bo, ZHANG Lei, WANG Qiong. Ranking Algorithms of Vital Nodes Based on Spring Model[J]. Computer Engineering and Applications, 2022, 58(7): 77-86.

参考文献

[1] 张昕，郭阳.复杂网络中的一种介度熵抗毁性度量方法[J].计算机工程与应用，2020，56（12）：111-117.
ZHANG X，GUO Y.Betweenness-degree entropy invulnerability measurement method in complex networks[J].Computer Engineering and Applications，2020，56（12）：111-117.
[2] 刘凤增，肖兵，金宏斌，等.基于有限节点集的网络毁伤最大化问题研究[J].控制与决策，2020，35（4）：172-177.
LIU F Z，XIAO B，JIN H B，et al.Network damage maximization based on finite node set[J].Control and Decision，2020，35（4）：172-177.
[3] WILLIAMS R J，MARTINEZ N D.Simple rules yield complex food webs[J].Nature，2000，404：180-183.
[4] JEONG H，TOMBOR B，ALBERT R，et al.The large-scale organization of metabolic networks[J].Nature，2000，407：651-654.
[5] ALBERT R，JEONG H，BARABASI A.Diameter of the World-Wide Web[J].Nature，1999，401：130-131.
[6] REDNER S.How popular is your paper? An empirical study of the citation distribution[J].European Physical Journal B Condensed Matter & Complex Systems，1998，4（2）：131-134.
[7] 王安，顾益军.基于社区划分的节点重要性评估方法[J].计算机工程与应用，2020，56（8）：42-48.
WANG A，GU Y J.Nodes importance ranking method based on community detection[J].Computer Engineering and Applications，2020，56（8）：42-48.
[8] 任晓龙，吕琳媛.网络重要节点排序方法综述[J].科学通报，2014，59（13）：1175-1197.
REN X L，LYU L Y.Review of ranking nodes in complex networks[J].Chinese Science Bulletin，2014，59（13）：1175-1197.
[9] WENG J，LIM E P，JIANG J，et al.Twitterrank：Finding topic-sensitive influential twitterers[M].[S.l.]：ACM Press，2010：261-270.
[10] VITALI S，GLATTFELDER J B，BATTISTON S.The network of global corporate control[J].Business & Politics，2011，15（3）：357-379.
[11] 范如国，王奕博，罗明，等.基于SEIR的新型肺炎传播模型及拐点预测分析[J].电子科技大学学报，2020，49（1）：1-6.
FAN R G，WANG Y B，LUO M，et al.SEIR-based novel pneumonia transmission model and infection point prediction analysis[J].Journal of University of Electronic Science and Technology of China，2020，49（1）：1-6.
[12] 谢仲伦，杨楠，黄保续，等.SARS控制策略仿真研究：防控措施效果比较[J].系统仿真学报，2004，16（12）：2667-2672.
XIE Z L，YANG N，HUANG B X，et al.Simulation research of SARS control strategy in China：Prevention and control measure’s effect comparison[J].Journal of System Simulation，2004，16（12）：2667-2672.
[13] 陈诗，任卓明，刘闯，等.时序网络中关键节点的识别方法研究进展[J].电子科技大学学报，2020，49（2）：291-314.
CHEN S，REN Z M，LIU C，et al.Identification methods of vital nodes on temporal networks[J].Journal of University of Electronic Science and Technology of China，2020，49（2）：291-314.
[14] 顾亦然，朱梓嫣.基于LeaderRank和节点相似度的复杂网络重要节点排序算法[J].电子科技大学学报，2017，46（2）：441-448.
GU Y R，ZHU Z Y.Node ranking in complex networks based on LeaderRank and nodes similarity[J].Journal of University of Electronic Science and Technology of China，2017，46（2）：441-448.
[15] FREEMAN L C.Centrality in social networks conceptual clarification[J].Social Networks，1978，1（3）：215-239.
[16] HIRSCH J E.An index to quantify an individual’s scientific research output[J].Proceedings of the National Academy of Sciences of the United States of America，2005，102：16569-16572.
[17] KITSAK M，GALLOS L K，HAVLIN S，et al.Identification of influential spreaders in complex networks[J].Nature Physics，2010，6（11）：888-893.
[18] LYU L Y，ZHOU T，ZHANG Q M，et al.The H-index of a network node and its relation to degree and coreness[J].Nature Communications，2016，7：10168.
[19] BONACICH P.Factoring and weighting approaches to status scores and clique identification[J].Journal of Mathematical Sociology，1972，2（1）：113-120.
[20] BRIN S，PAGE L.The anatomy of a large-scale hypertextual Web search engine[J].Computer Networks & Isdn Systems，1998，30：107-117.
[21] LI Z，REN T，MA X Q，et al.Identifying influential spreaders by gravity model[J].Scientific Reports，2019，9（1）：8387.
[22] KENDALL M.A new measure of rank correlation[J].Biometrika，1938，30（1/2）：81-93.
[23] HETHCOTE H W.The mathematics of infectious diseases[J].SIAM Review，2009，42：599-653.
[24] 刘惠，柴志杰，杜军朝，等.基于组合虚拟力的传感器网络三维空间重部署算法研究[J].自动化学报，2011，37（6）：713-723.
LIU H，CHAI Z J，DU J C，et al.Sensor redeployment algorithm based on combined virtual forces in three dimensional space[J].Acta Automatica Sinica，2011，37（6）：713-723.
[25] JOHNSON D B.Efficient algorithms for shortest paths in sparse networks[J].Journal of the ACM，1977，24（1）：1-13.
[26] GOH K，CUSICK M E，VALLE D，et al.The human disease network[J].PNAS，2007，104：8685-8690.
[27] KUMAR A，SNYDER M.Protein complexes take the bait[J].Nature，2002，415：123-124.
[28] WATTS D J，STROGATZ S H.Collective dynamics of “small-world” networks[J].Nature，1998，393：440-442.
[29] ROCHA L E C，LILJEROS F，HOLME P.Simulated epidemics in an empirical spatiotemporal network of 50，185 sexual contacts[J].PLoS Computational Biology，2011，7（3）：e1001109.