搜索

文章查询

x

留言板

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

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

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

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

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

阮逸润, 老松杨, 王竣德, 白亮, 陈立栋
PDF
导出引用
导出核心图
  • 节点重要性度量对于研究复杂网络鲁棒性与脆弱性具有重要意义.大规模实际复杂网络的结构往往随着时间不断变化,在获取网络全局信息用于评估节点重要性方面具有局限性.通过量化节点局部网络拓扑的重合程度来定义节点间的相似性,提出了一种考虑节点度以及邻居节点拓扑重合度的节点重要性评估算法,算法只需要获取节点两跳内的邻居节点信息,通过计算邻居节点对之间的相似度,便可表征其在复杂网络中的结构重要性.基于六个经典的实际网络和一个人工的小世界网络,分别以静态与动态的方式对网络进行攻击,通过对极大连通系数与网络效率两种评估指标的实验结果对比,证明了所提算法优于基于局域信息的度指标、半局部度指标、基于节点度及其邻居度的WL指标以及基于节点位置的K-shell指标.
      通信作者: 阮逸润, ruanyirun@163.com
    • 基金项目: 国家自然科学基金(批准号: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] 任卓明, 邵凤, 刘建国, 郭强, 汪秉宏. 基于度与集聚系数的网络节点重要性度量方法研究. 物理学报, 2013, 62(12): 128901. doi: 10.7498/aps.62.128901
    [2] 孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 物理学报, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
    [3] 于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法. 物理学报, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
    [4] 刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. 物理学报, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
    [5] 黄丽亚, 汤平川, 霍宥良, 郑义, 成谢锋. 基于加权K-阶传播数的节点重要性. 物理学报, 2019, 68(12): 128901. doi: 10.7498/aps.68.20190087
    [6] 陈世明, 吕辉, 徐青刚, 许云飞, 赖强. 基于度的正/负相关相依网络模型及其鲁棒性研究. 物理学报, 2015, 64(4): 048902. doi: 10.7498/aps.64.048902
    [7] 王雨, 郭进利. 基于多重影响力矩阵的有向加权网络节点重要性评估方法. 物理学报, 2017, 66(5): 050201. doi: 10.7498/aps.66.050201
    [8] 侯绿林, 老松杨, 肖延东, 白亮. 复杂网络可控性研究现状综述. 物理学报, 2015, 64(18): 188901. doi: 10.7498/aps.64.188901
    [9] 陈世明, 邹小群, 吕辉, 徐青刚. 面向级联失效的相依网络鲁棒性研究. 物理学报, 2014, 63(2): 028902. doi: 10.7498/aps.63.028902
    [10] 曾高荣, 裘正定. 数字水印的鲁棒性评测模型. 物理学报, 2010, 59(8): 5870-5879. doi: 10.7498/aps.59.5870
    [11] 周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. 物理学报, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
    [12] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [13] 徐明, 许传云, 曹克非. 度相关性对无向网络可控性的影响. 物理学报, 2017, 66(2): 028901. doi: 10.7498/aps.66.028901
    [14] 段东立, 武小悦. 基于可调负载重分配的无标度网络连锁效应分析. 物理学报, 2014, 63(3): 030501. doi: 10.7498/aps.63.030501
    [15] 缪志强, 王耀南. 基于径向小波神经网络的混沌系统鲁棒自适应反演控制. 物理学报, 2012, 61(3): 030503. doi: 10.7498/aps.61.030503
    [16] 高湘昀, 安海忠, 方伟. 基于复杂网络的时间序列双变量相关性波动研究. 物理学报, 2012, 61(9): 098902. doi: 10.7498/aps.61.098902
    [17] 谭索怡, 祁明泽, 吴俊, 吕欣. 复杂网络链路可预测性: 基于特征谱视角. 物理学报, 2020, 69(8): 1-10. doi: 10.7498/aps.69.20191817
    [18] 段东立, 战仁军. 基于相继故障信息的网络节点重要度演化机理分析. 物理学报, 2014, 63(6): 068902. doi: 10.7498/aps.63.068902
    [19] 郭进利. 新节点的边对网络无标度性影响. 物理学报, 2008, 57(2): 756-761. doi: 10.7498/aps.57.756
    [20] 温淑焕, 袁俊英. 基于无源性的不确定机器人的力控制. 物理学报, 2010, 59(3): 1615-1619. doi: 10.7498/aps.59.1615
  • 引用本文:
    Citation:
计量
  • 文章访问数:  676
  • PDF下载量:  527
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-09-20
  • 修回日期:  2016-10-14
  • 刊出日期:  2017-02-05

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

  • 1. 国防科学技术大学, 信息系统工程重点实验室, 长沙 410073
  • 通信作者: 阮逸润, ruanyirun@163.com
    基金项目: 

    国家自然科学基金(批准号:61571453)资助的课题.

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

English Abstract

参考文献 (45)

目录

    /

    返回文章
    返回