基于自规避随机游走的节点排序算法

段杰明; 尚明生; 蔡世民; 张玉霞

doi:10.7498/aps.64.200501

摘要

评估复杂网络系统的节点重要性有助于提升其系统抗毁性和结构稳定性. 目前, 定量节点重要性的排序算法通常基于网络结构的中心性指标如度数、介数、紧密度、特征向量等. 然而, 这些算法需要以知晓网络结构的全局信息为前提, 很难在大规模网络中实际应用. 基于自规避随机游走的思想, 提出一种结合网络结构局域信息和标签扩散的节点排序算法. 该算法综合考虑了节点的直接邻居数量及与其他节点之间的拓扑关系, 能够表征其在复杂网络系统中的结构影响力和重要性. 基于三个典型的实际网络, 通过对极大连通系数、网络谱距离数、节点连边数和脆弱系数等评估指标的实验对比, 结果表明提出的算法显著优于现有的依据局域信息的节点排序算法.

关键词:

Abstract

Evaluation of node importance is helpful to improve the invulnerability and robustness of complex networked systems. At present, the classic ranking methods of quantitatively analyzing node importance are based on the centrality measurements of network topology, such as degree, betweenness, closeness, eigenvector, etc. Therefore, they often restrict the unknown topological information and are not convenient to use in large-scale real networked systems. In this paper, according to the idea of self-avoiding random walking, we propose a novel and simplified ranking method integrated with label propagation and local topological information, in which the number of labels that node collects from propagating process quantitatively denotes the ranking order. Moreover, the proposed method is able to characterize the structural influence and importance of node in complex networked system because it comprehensively considers both the direct neighbors of node and the topological relation of node to other ones. Through performing the experiments on three benchmark networks, we obtain interesting results derived from four common evaluating indices, i. e., the coefficient of giant component, the spectral distance, the links of node, and the fragility, which indicate that the proposed method is much more efficient and effective for ranking influential nodes than the acquaintance algorithm.

Keywords:

作者及机构信息

1.
电子科技大学计算机科学与工程学院, 成都 611731;

2.
电子科技大学大数据研究中心, 成都 611731;

3.
华南理工大学物理与光电学院, 广州 510640

基金项目: 国家自然科学基金(批准号: 61370150, 61433014, 71490720)和中央高校基本科研业务费(批准号: 2014ZM0079)资助的课题.

Authors and contacts

1.
School of Computer Scinece and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China;

2.
Big Data Research Center, University of Electronic Science and Technology of China, Chengdu 611731, China;

3.
Physics and Photoelectricity School, South China University of Technology, Guangzhou 510640, China

Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 61370150, 61433014, 71490720) and the Fundamental Research Funds for the Central Universities, China (Grant No. 2014ZM0079).

参考文献

[1]	Kinney R, Crucitti P, Albert R, Latora V 2005 Eur. Phys. J. B 46 101
[2]	Strogatz S H 2001 Nature 410 268
[3]	Watts D J, Strogatz S H 1998 Nature 393 440
[4]	Barabasi A L, Albert R 1999 Science 286 509
[5]	L L, Medo M, Yeung C H, Zhang Y C, Zhang Z K, Zhou T 2012 Phys. Rep. 519 1
[6]	Albert R, Barabási A L 2002 Rev. Mod. Phys. 74 47
[7]	Liang Z W, Li J P, Yang F, Petropulu A 2014 Chin. Phys. B 23 098902
[8]	Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901 (in Chinese) [刘建国, 任卓明, 郭强, 汪秉宏 2013 62 178901]
[9]	Newman M 2010 Networks: An Introduction (Oxford: Oxford University Press)
[10]	Freeman L 1977 Sociometry 40 35
[11]	Sabidussi G 1966 Psychometrika 31 581
[12]	Stephenson K, Zelen M 1989 Soc. Networks 11 1
[13]	Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888
[14]	Ghoshal G, Barabási A L 2010 Nat. Commun. 2 394
[15]	Zhao J, Yu L, Li J R, Zhou P 2015 Chin. Phys. B 24 058904
[16]	Chen D, L L, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777
[17]	Zhang H F, Li K Z, Fu X C, Wang B H 2009 Chin. Phys. Lett. 26 068901
[18]	Cheng X Q, Ren F X, Shen H W, Zhang Z K, Zhou T 2010 J. Stat. Mech. 20 595
[19]	Zhao Y X, Huang B, Tang M, Zhang H F, Chen D B 2014 EPL 108 68005
[20]	Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 9602
[21]	Hu Q, Gao Y, Ma P, Yin Y, Zhang Y, Xing C 2013 Web-Age Information (Berlin: Springer Berlin Heidelberg) pp99-104
[22]	Ren X L, L L Y 2014 Chin. Sci. Bull. 59 1175 (in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]
[23]	Cohen R, Havlin S, Ben-Avraham D 2003 Phys. Rev. Lett. 91 247901
[24]	Cohen R, Erez K, Ben-Avraham D, Havlin S 2001 Phys. Rev. Lett. 86 3682
[25]	Salathé M, Jones J H 2010 PLoS Comput. Biol. 4 e1000736
[26]	Albert R, Jeong H, Barabasi A L 2000 Nature 406 378
[27]	Muff S, Rao F, Caflisch A 2005 Phys. Rev. E 72 056107
[28]	Dorogovtsev S N, Mendes J F 2001 Phys. Rev. Lett. 87 219801
[29]	Holme P, Kim B J, Yoon C N, Han S K 2002 Phys. Rev. E 65 056109
[30]	Costa L F, Rodrigues F A, Travieso G, Villas Boas P R 2007 Adv. Phys. 56 167
[31]	Latora V, Marchiori M 2001 Phys. Rev. Lett. 87 198701
[32]	Latora V, Marchiori M 2003 Eur. Phys. J. B 32 249
[33]	Moreno Y, Nekovee M, Vespignani A 2004 Phys. Rev. E 69 055101
[34]	Newman M E 2002 Phys. Rev. Lett. 89 208701

施引文献

[1]	Kinney R, Crucitti P, Albert R, Latora V 2005 Eur. Phys. J. B 46 101
[2]	Strogatz S H 2001 Nature 410 268
[3]	Watts D J, Strogatz S H 1998 Nature 393 440
[4]	Barabasi A L, Albert R 1999 Science 286 509
[5]	L L, Medo M, Yeung C H, Zhang Y C, Zhang Z K, Zhou T 2012 Phys. Rep. 519 1
[6]	Albert R, Barabási A L 2002 Rev. Mod. Phys. 74 47
[7]	Liang Z W, Li J P, Yang F, Petropulu A 2014 Chin. Phys. B 23 098902
[8]	Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901 (in Chinese) [刘建国, 任卓明, 郭强, 汪秉宏 2013 62 178901]
[9]	Newman M 2010 Networks: An Introduction (Oxford: Oxford University Press)
[10]	Freeman L 1977 Sociometry 40 35
[11]	Sabidussi G 1966 Psychometrika 31 581
[12]	Stephenson K, Zelen M 1989 Soc. Networks 11 1
[13]	Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888
[14]	Ghoshal G, Barabási A L 2010 Nat. Commun. 2 394
[15]	Zhao J, Yu L, Li J R, Zhou P 2015 Chin. Phys. B 24 058904
[16]	Chen D, L L, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777
[17]	Zhang H F, Li K Z, Fu X C, Wang B H 2009 Chin. Phys. Lett. 26 068901
[18]	Cheng X Q, Ren F X, Shen H W, Zhang Z K, Zhou T 2010 J. Stat. Mech. 20 595
[19]	Zhao Y X, Huang B, Tang M, Zhang H F, Chen D B 2014 EPL 108 68005
[20]	Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 9602
[21]	Hu Q, Gao Y, Ma P, Yin Y, Zhang Y, Xing C 2013 Web-Age Information (Berlin: Springer Berlin Heidelberg) pp99-104
[22]	Ren X L, L L Y 2014 Chin. Sci. Bull. 59 1175 (in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]
[23]	Cohen R, Havlin S, Ben-Avraham D 2003 Phys. Rev. Lett. 91 247901
[24]	Cohen R, Erez K, Ben-Avraham D, Havlin S 2001 Phys. Rev. Lett. 86 3682
[25]	Salathé M, Jones J H 2010 PLoS Comput. Biol. 4 e1000736
[26]	Albert R, Jeong H, Barabasi A L 2000 Nature 406 378
[27]	Muff S, Rao F, Caflisch A 2005 Phys. Rev. E 72 056107
[28]	Dorogovtsev S N, Mendes J F 2001 Phys. Rev. Lett. 87 219801
[29]	Holme P, Kim B J, Yoon C N, Han S K 2002 Phys. Rev. E 65 056109
[30]	Costa L F, Rodrigues F A, Travieso G, Villas Boas P R 2007 Adv. Phys. 56 167
[31]	Latora V, Marchiori M 2001 Phys. Rev. Lett. 87 198701
[32]	Latora V, Marchiori M 2003 Eur. Phys. J. B 32 249
[33]	Moreno Y, Nekovee M, Vespignani A 2004 Phys. Rev. E 69 055101
[34]	Newman M E 2002 Phys. Rev. Lett. 89 208701

[1]	汪亭亭, 梁宗文, 张若曦. 基于信息熵与迭代因子的复杂网络节点重要性评价方法. , 2023, 72(4): 048901. doi: 10.7498/aps.72.20221878
[2]	阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. , 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
[3]	王烨花, 何美娟. 高斯色噪声激励下非对称双稳耦合网络系统的随机共振. , 2022, 71(19): 190501. doi: 10.7498/aps.71.20220909
[4]	刘慧, 王炳珺, 陆君安, 李增扬. 复杂网络牵制控制优化选点算法及节点组重要性排序. , 2021, 70(5): 056401. doi: 10.7498/aps.70.20200872
[5]	韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰. 面向结构洞的复杂网络关键节点排序. , 2015, 64(5): 058902. doi: 10.7498/aps.64.058902
[6]	段东立, 战仁军. 基于相继故障信息的网络节点重要度演化机理分析. , 2014, 63(6): 068902. doi: 10.7498/aps.63.068902
[7]	孙中奎, 鲁捧菊, 徐伟. 非对称双稳耦合网络系统的尺度随机共振研究. , 2014, 63(22): 220503. doi: 10.7498/aps.63.220503
[8]	范宏. 动态银行网络系统中系统性风险定量计算方法研究. , 2014, 63(3): 038902. doi: 10.7498/aps.63.038902
[9]	周漩, 杨帆, 张凤鸣, 周卫平, 邹伟. 复杂网络系统拓扑连接优化控制方法. , 2013, 62(15): 150201. doi: 10.7498/aps.62.150201
[10]	刘金良. 具有随机节点结构的复杂网络同步研究. , 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
[11]	刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. , 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
[12]	周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. , 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
[13]	吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. , 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
[14]	周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. , 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
[15]	郭永峰, 谭建国. 一类非线性神经网络系统的超阈值随机共振现象. , 2012, 61(17): 170502. doi: 10.7498/aps.61.170502
[16]	钭斐玲, 胡延庆, 黎勇, 樊瑛, 狄增如. 空间网络上的随机游走. , 2012, 61(17): 178901. doi: 10.7498/aps.61.178901
[17]	钱江海, 韩定定, 马余刚. 开放式复杂航空网络系统的动力学演化. , 2011, 60(9): 098901. doi: 10.7498/aps.60.098901
[18]	吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. , 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
[19]	高洋, 李丽香, 彭海朋, 杨义先, 张小红. 多重边复杂网络系统的稳定性分析. , 2008, 57(3): 1444-1452. doi: 10.7498/aps.57.1444
[20]	李季, 汪秉宏, 蒋品群, 周涛, 王文旭. 节点数加速增长的复杂网络生长模型. , 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051

计量

文章访问数: 6917
PDF下载量: 377
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

搜索

留言板