搜索

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

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

基于领域相似度的复杂网络节点重要度评估算法

阮逸润 老松杨 王竣德 白亮 陈立栋

引用本文:
Citation:

基于领域相似度的复杂网络节点重要度评估算法

阮逸润, 老松杨, 王竣德, 白亮, 陈立栋

Node importance measurement based on neighborhood similarity in complex network

Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Chen Li-Dong
PDF
导出引用
  • 节点重要性度量对于研究复杂网络鲁棒性与脆弱性具有重要意义.大规模实际复杂网络的结构往往随着时间不断变化,在获取网络全局信息用于评估节点重要性方面具有局限性.通过量化节点局部网络拓扑的重合程度来定义节点间的相似性,提出了一种考虑节点度以及邻居节点拓扑重合度的节点重要性评估算法,算法只需要获取节点两跳内的邻居节点信息,通过计算邻居节点对之间的相似度,便可表征其在复杂网络中的结构重要性.基于六个经典的实际网络和一个人工的小世界网络,分别以静态与动态的方式对网络进行攻击,通过对极大连通系数与网络效率两种评估指标的实验结果对比,证明了所提算法优于基于局域信息的度指标、半局部度指标、基于节点度及其邻居度的WL指标以及基于节点位置的K-shell指标.
    Ranking node importance is of great significance for studying the robustness and vulnerability of complex network. Over the recent years, various centrality indices such as degree, semilocal, K-shell, betweenness and closeness centrality have been employed to measure node importance in the network. Among them, some well-known global measures such as betweenness centrality and closeness centrality can achieve generally higher accuracy in ranking nodes, while their computation complexity is relatively high, and also the global information is not readily available in a large-scaled network. In this paper, we propose a new local metric which only needs to obtain the neighborhood information within two hops of the node to rank node importance. Firstly, we calculate the similarity of node neighbors by quantifying the overlap of their topological structures with Jaccard index; secondly, the similarity between pairs of neighbor nodes is calculated synthetically, and the redundancy of the local link of nodes is obtained. Finally, by reducing the influence of densely local links on ranking node importance, a new local index named LLS that considers both neighborhood similarity and node degree is proposed. To check the effectiveness of the proposed method of ranking node importance, we carry out it on six real world networks and one artificial small-world network by static attacks and dynamic attacks. In the static attack mode, the ranking value of each node is the same as that in the original network. In the dynamic attack mode, once the nodes are removed, the centrality of each node needs recalculating. The relative size of the giant component and the network efficiency are used for network connectivity assessment during the attack. A faster decrease in the size of the giant component and a faster decay of network efficiency indicate a more effective attack strategy. By comparing the decline rates of these two indices to evaluate the connectedness of all networks, we find that the proposed method is more efficient than traditional local metrics such as degree centrality, semilocal centrality, K-shell decomposition method, no matter whether it is in the static or dynamic manner. And for a certain ranking method, the results of the dynamic attack are always better than those of the static attack. This work can shed some light on how the local densely connections affect the node centrality in maintaining network robustness.
      通信作者: 阮逸润, ruanyirun@163.com
    • 基金项目: 国家自然科学基金(批准号:61571453)资助的课题.
      Corresponding author: Ruan Yi-Run, ruanyirun@163.com
    • Funds: Project supported by the National Natural Science Foundation of China (Grant No. 61571453).
    [1]

    Barabási A L, Albert R 1999 Science 286 509

    [2]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [3]

    Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200

    [4]

    Rogers T 2015 Europhys. Lett. 109 28005

    [5]

    Kinney R, Crucitti P, Albert R, Latora V 2005 Eur. Phys. J. B 46 101

    [6]

    Wang G Z, Cao Y J, Bao Z J, Han Z X 2009 Acta Phys. Sin. 58 3597 (in Chinese)[王光增, 曹一家, 包哲静, 韩祯祥2009物理学报58 3597]

    [7]

    Albert R, Jeong H, Barabási A L 1999 Nature 401 130

    [8]

    Sabidussi G 1966 Psychometrika 31 581

    [9]

    Freeman L C 1977 Sociometry 40 35

    [10]

    Newman M E J 2006 Phys. Rev. E 74 036104

    [11]

    Brin S and Page L 1998 Comput. Networks. Isdn. 30 107

    [12]

    Radicchi F, Fortunato S, Markines B, Vespignani A 2009 Phys. Rev. E 80 056103

    [13]

    L L Y, Zhang Y C, Yeung C H, Zhou T 2011 PloS One 6 e21202

    [14]

    L L Y, Zhang Q M, Stanley H E 2016 Nat. Commun. 7 10168

    [15]

    Chen D B, Lu L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777

    [16]

    Wang J W, Rong L L, Guo T Z 2010 J. Dalian Univ. Technol. 50 822 (in Chinese)[王建伟, 荣莉莉, 郭天柱2010大连理工大学学报50 822]

    [17]

    Ren Z M, Shao F, Liu J G, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 128901 (in Chinese)[任卓明, 邵凤, 刘建国, 郭强, 汪秉宏2013物理学报62 128901]

    [18]

    Ugander J, Backstrom L, Marlow C, Kleinberg J 2012 Proc. Natl. Acad. Sci. 109 5962

    [19]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888

    [20]

    Ren X L, L L Y 2014 Sci. Bull. 59 1175 (in Chinese)[任晓龙, 吕琳媛2014科学通报59 1175]

    [21]

    Chen D B, Xiao R, Zeng A, Zhang Y C 2014 Europhys. Lett. 104 68006

    [22]

    Ruan Y R, Lao S Y, Xiao Y D, Wang J D, Bai L 2016 Chin. Phys. Lett. 33 028901

    [23]

    Burt R S 2009 Structure Holes:the Social Structure of Competition (London:Harvard University Press) p53

    [24]

    Li P, Zhang J, Xu X K, Small M 2012 Chin. Phys. Lett. 29 048903

    [25]

    Liu J G, Lin J H, Guo Q, Zhou T 2016 Sci. Rep. 6 21380

    [26]

    L L Y, Chen D B, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1

    [27]

    Liu Y Y, Slotine J J, Barabási A L 2011 Nature 473 167

    [28]

    Orouskhani Y, Jalili M, Yu X H 2016 Sci. Rep. 6 24252

    [29]

    Zhou M Y, Zhuo Z, Liao H, Fu Z Q, Cai S M 2015 Sci. Rep. 5 17459

    [30]

    Liu Y Y, Slotine J J, Barabasi A L 2012 PloS One 7 e44459

    [31]

    Jia T, Pósfai M 2014 Sci. Rep. 4 5379

    [32]

    Jaccad P 1901 Bull. Torrey Bot. Club 37 547

    [33]

    Castellano C and Pastor-Satorras R 2010 Phys. Rev. Lett. 105 218701

    [34]

    Dereich S, Mörters P 2013 Ann. Prob. 41 329

    [35]

    Vragovic I, Louis E, Diaz-Guilera A 2005 Phys. Rev. E 71 036122

    [36]

    Latora V, Marchiori M 2007 New J. Phys. 9 188

    [37]

    Blagus N,Šubelj L, Bajec M 2012 Physica A 391 2794

    [38]

    Batagelj V, Mrvar A 1998 Connections 21 47

    [39]

    Isella L, Stehlé J, Barrat A, Cattuto C, Pinton J F 2011 J. Theor. Biol. 271 166

    [40]

    Guimera R, Danon L, Diaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103

    [41]

    Von Mering C, Krause R, Snel B, Cornell M, Oliver S G, Fields S, Bork P 2002 Nature 417 399

    [42]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [43]

    Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 9602

    [44]

    Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 13172

    [45]

    Buldyrev S V, Parshani R, Paul G, Stanley H E, Havlin S 2010 Nature 464 1025

  • [1]

    Barabási A L, Albert R 1999 Science 286 509

    [2]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [3]

    Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200

    [4]

    Rogers T 2015 Europhys. Lett. 109 28005

    [5]

    Kinney R, Crucitti P, Albert R, Latora V 2005 Eur. Phys. J. B 46 101

    [6]

    Wang G Z, Cao Y J, Bao Z J, Han Z X 2009 Acta Phys. Sin. 58 3597 (in Chinese)[王光增, 曹一家, 包哲静, 韩祯祥2009物理学报58 3597]

    [7]

    Albert R, Jeong H, Barabási A L 1999 Nature 401 130

    [8]

    Sabidussi G 1966 Psychometrika 31 581

    [9]

    Freeman L C 1977 Sociometry 40 35

    [10]

    Newman M E J 2006 Phys. Rev. E 74 036104

    [11]

    Brin S and Page L 1998 Comput. Networks. Isdn. 30 107

    [12]

    Radicchi F, Fortunato S, Markines B, Vespignani A 2009 Phys. Rev. E 80 056103

    [13]

    L L Y, Zhang Y C, Yeung C H, Zhou T 2011 PloS One 6 e21202

    [14]

    L L Y, Zhang Q M, Stanley H E 2016 Nat. Commun. 7 10168

    [15]

    Chen D B, Lu L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777

    [16]

    Wang J W, Rong L L, Guo T Z 2010 J. Dalian Univ. Technol. 50 822 (in Chinese)[王建伟, 荣莉莉, 郭天柱2010大连理工大学学报50 822]

    [17]

    Ren Z M, Shao F, Liu J G, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 128901 (in Chinese)[任卓明, 邵凤, 刘建国, 郭强, 汪秉宏2013物理学报62 128901]

    [18]

    Ugander J, Backstrom L, Marlow C, Kleinberg J 2012 Proc. Natl. Acad. Sci. 109 5962

    [19]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888

    [20]

    Ren X L, L L Y 2014 Sci. Bull. 59 1175 (in Chinese)[任晓龙, 吕琳媛2014科学通报59 1175]

    [21]

    Chen D B, Xiao R, Zeng A, Zhang Y C 2014 Europhys. Lett. 104 68006

    [22]

    Ruan Y R, Lao S Y, Xiao Y D, Wang J D, Bai L 2016 Chin. Phys. Lett. 33 028901

    [23]

    Burt R S 2009 Structure Holes:the Social Structure of Competition (London:Harvard University Press) p53

    [24]

    Li P, Zhang J, Xu X K, Small M 2012 Chin. Phys. Lett. 29 048903

    [25]

    Liu J G, Lin J H, Guo Q, Zhou T 2016 Sci. Rep. 6 21380

    [26]

    L L Y, Chen D B, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1

    [27]

    Liu Y Y, Slotine J J, Barabási A L 2011 Nature 473 167

    [28]

    Orouskhani Y, Jalili M, Yu X H 2016 Sci. Rep. 6 24252

    [29]

    Zhou M Y, Zhuo Z, Liao H, Fu Z Q, Cai S M 2015 Sci. Rep. 5 17459

    [30]

    Liu Y Y, Slotine J J, Barabasi A L 2012 PloS One 7 e44459

    [31]

    Jia T, Pósfai M 2014 Sci. Rep. 4 5379

    [32]

    Jaccad P 1901 Bull. Torrey Bot. Club 37 547

    [33]

    Castellano C and Pastor-Satorras R 2010 Phys. Rev. Lett. 105 218701

    [34]

    Dereich S, Mörters P 2013 Ann. Prob. 41 329

    [35]

    Vragovic I, Louis E, Diaz-Guilera A 2005 Phys. Rev. E 71 036122

    [36]

    Latora V, Marchiori M 2007 New J. Phys. 9 188

    [37]

    Blagus N,Šubelj L, Bajec M 2012 Physica A 391 2794

    [38]

    Batagelj V, Mrvar A 1998 Connections 21 47

    [39]

    Isella L, Stehlé J, Barrat A, Cattuto C, Pinton J F 2011 J. Theor. Biol. 271 166

    [40]

    Guimera R, Danon L, Diaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103

    [41]

    Von Mering C, Krause R, Snel B, Cornell M, Oliver S G, Fields S, Bork P 2002 Nature 417 399

    [42]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [43]

    Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 9602

    [44]

    Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 13172

    [45]

    Buldyrev S V, Parshani R, Paul G, Stanley H E, Havlin S 2010 Nature 464 1025

  • [1] 赵豪, 冯晋霞, 孙婧可, 李渊骥, 张宽收. 连续变量Einstein-Podolsky-Rosen纠缠态光场在光纤信道中分发时纠缠的鲁棒性. 物理学报, 2022, 71(9): 094202. doi: 10.7498/aps.71.20212380
    [2] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
    [3] 杨松青, 蒋沅, 童天驰, 严玉为, 淦各升. 基于Tsallis熵的复杂网络节点重要性评估方法. 物理学报, 2021, 70(21): 216401. doi: 10.7498/aps.70.20210979
    [4] 谭索怡, 祁明泽, 吴俊, 吕欣. 复杂网络链路可预测性: 基于特征谱视角. 物理学报, 2020, 69(8): 088901. doi: 10.7498/aps.69.20191817
    [5] 黄丽亚, 汤平川, 霍宥良, 郑义, 成谢锋. 基于加权K-阶传播数的节点重要性. 物理学报, 2019, 68(12): 128901. doi: 10.7498/aps.68.20190087
    [6] 孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 物理学报, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
    [7] 徐明, 许传云, 曹克非. 度相关性对无向网络可控性的影响. 物理学报, 2017, 66(2): 028901. doi: 10.7498/aps.66.028901
    [8] 王雨, 郭进利. 基于多重影响力矩阵的有向加权网络节点重要性评估方法. 物理学报, 2017, 66(5): 050201. doi: 10.7498/aps.66.050201
    [9] 侯绿林, 老松杨, 肖延东, 白亮. 复杂网络可控性研究现状综述. 物理学报, 2015, 64(18): 188901. doi: 10.7498/aps.64.188901
    [10] 陈世明, 吕辉, 徐青刚, 许云飞, 赖强. 基于度的正/负相关相依网络模型及其鲁棒性研究. 物理学报, 2015, 64(4): 048902. doi: 10.7498/aps.64.048902
    [11] 段东立, 武小悦. 基于可调负载重分配的无标度网络连锁效应分析. 物理学报, 2014, 63(3): 030501. doi: 10.7498/aps.63.030501
    [12] 陈世明, 邹小群, 吕辉, 徐青刚. 面向级联失效的相依网络鲁棒性研究. 物理学报, 2014, 63(2): 028902. doi: 10.7498/aps.63.028902
    [13] 刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. 物理学报, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
    [14] 于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法. 物理学报, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
    [15] 任卓明, 邵凤, 刘建国, 郭强, 汪秉宏. 基于度与集聚系数的网络节点重要性度量方法研究. 物理学报, 2013, 62(12): 128901. doi: 10.7498/aps.62.128901
    [16] 高湘昀, 安海忠, 方伟. 基于复杂网络的时间序列双变量相关性波动研究. 物理学报, 2012, 61(9): 098902. doi: 10.7498/aps.61.098902
    [17] 缪志强, 王耀南. 基于径向小波神经网络的混沌系统鲁棒自适应反演控制. 物理学报, 2012, 61(3): 030503. doi: 10.7498/aps.61.030503
    [18] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [19] 周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. 物理学报, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
    [20] 曾高荣, 裘正定. 数字水印的鲁棒性评测模型. 物理学报, 2010, 59(8): 5870-5879. doi: 10.7498/aps.59.5870
计量
  • 文章访问数:  5912
  • PDF下载量:  721
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-09-20
  • 修回日期:  2016-10-14
  • 刊出日期:  2017-02-05

基于领域相似度的复杂网络节点重要度评估算法

  • 1. 国防科学技术大学, 信息系统工程重点实验室, 长沙 410073
  • 通信作者: 阮逸润, ruanyirun@163.com
    基金项目: 国家自然科学基金(批准号:61571453)资助的课题.

摘要: 节点重要性度量对于研究复杂网络鲁棒性与脆弱性具有重要意义.大规模实际复杂网络的结构往往随着时间不断变化,在获取网络全局信息用于评估节点重要性方面具有局限性.通过量化节点局部网络拓扑的重合程度来定义节点间的相似性,提出了一种考虑节点度以及邻居节点拓扑重合度的节点重要性评估算法,算法只需要获取节点两跳内的邻居节点信息,通过计算邻居节点对之间的相似度,便可表征其在复杂网络中的结构重要性.基于六个经典的实际网络和一个人工的小世界网络,分别以静态与动态的方式对网络进行攻击,通过对极大连通系数与网络效率两种评估指标的实验结果对比,证明了所提算法优于基于局域信息的度指标、半局部度指标、基于节点度及其邻居度的WL指标以及基于节点位置的K-shell指标.

English Abstract

参考文献 (45)

目录

    /

    返回文章
    返回