搜索

x

留言板

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

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

基于度与集聚系数的网络节点重要性度量方法研究

任卓明 邵凤 刘建国 郭强 汪秉宏

引用本文:
Citation:

基于度与集聚系数的网络节点重要性度量方法研究

任卓明, 邵凤, 刘建国, 郭强, 汪秉宏

Node importance measurement based on the degree and clustering coefficient information

Ren Zhuo-Ming, Shao Feng, Liu Jian-Guo, Guo Qiang, Wang Bing-Hong
PDF
导出引用
  • 网络中节点重要性度量对于研究网络的鲁棒性具有十分重要的意义. 研究者们普遍运用度或集聚系数来度量节点的重要程度, 然而度指标只考虑节点自身邻居个数而忽略了其邻居之间的信息, 集聚系数只考虑节点邻居之间的紧密程度而忽略了其邻居的规模. 本文综合考虑节点的邻居个数, 以及其邻居之间的连接紧密程度, 提出了一种基于邻居信息与集聚系数的节点重要性评价方法. 对美国航空网络和美国西部电力网进行的选择性攻击实验表明, 采用该方法的效果较k-shell指标可以分别提高24%和112%. 本文的节点重要性度量方法只需要考虑网络局部信息, 因此非常适合于对大规模网络的节点重要性进行有效分析.
    The node importance measurement plays an important role in analyzing the robustness of the network. Most researchers use the degree or clustering coefficient to measure the node importance. However, the degree can only take into account the neighbor size, regardless of the clustering property of the neighbors. The clustering coefficient could only measure the closeness among the neighbors and neglect the activity of the target node. In this paper, we present a new method to measure the node importance by combining neighbor and clustering coefficient information. The robustness results measured by the network efficiency through removing the important nodes for the US Air network, the power grid of the western United States and Barabasi-Albert networks show that the new method can more accurately evaluate the node importance than the degree, neighbor information and k-shell indices.
    • 基金项目: 国家自然科学基金(批准号: 11275186, 71071098, 71171136, 91024026)、上海市青年科技启明星计划(A类)(批准号: 11QA1404500)、上海市教委科研创新项目(批准号: 11ZZ135, 11YZ110)、教育部科学技术研究重大项目(批准号: 211057)、上海市一流学科(系统科学)建设项目(批准号: XTKX2012)和上海市研究生创新基金(批准号: 5411115004)资助的课题.
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 11275186, 71071098, 71171136, 91024026), the Shanghai Rising-Star Program, China (Grant No. 11QA1404500), the Innovation Program of Shanghai Municipal Education Commission, China (Grant Nos. 11ZZ135, 11YZ110), the Key Project of Chinese Ministry of Education (Grant No. 211057), the Shanghai Leading Academic Discipline Project (Systems Science) (Grant No. XTKX2012), and the Innovation Fund For Graduate Student of Shanghai, China (Grant No. 54-11-115-004).
    [1]

    Newman M E J 2003 SIAM Rev. 45 167

    [2]

    Barabasi A L 2009 Science 325 412

    [3]

    Zhou T, Bai W J, Wang B H, Liu Z J, Yan G 2005 Physics 34 31 (in Chinese) [周涛, 柏文洁, 汪秉宏, 刘之景, 严钢2005 物理 34 31]

    [4]

    Liu J G, Wang Z T, Dang Y Z 2005 Mod. Phys. Lett. B 19 785

    [5]

    Zhou X, Zhang F M, Zhou W P, Zhou W, Yang F 2012 Acta Phys. Sin. 61 190201 (in Chinese) [周漩, 张凤鸣, 周卫平, 邹伟, 杨帆 2012 物理学报 61 190201]

    [6]

    Tan Y J, Wu J, Deng H Z, Zhu D Z 2006 Syst. Eng. 24 1 (in Chinese) [谭跃进, 吴俊, 邓宏钟, 朱大智 2006系统工程 24 1]

    [7]

    Liu H K, Zhou T 2007 Acta Phys. Sin. 56 106 (in Chinese) [刘宏鲲, 周涛 2007物理学报 56 106]

    [8]

    Jeong H, Mason S, Barabasi A L 2001 Nature 411 41

    [9]

    Dunne J A, Williams R J, Martinez N D 2002 Ecol. Lett. 5 558

    [10]

    Newman M E J, Forrest S, Balthrop A 2002 J. Phys. Rev. E 66 035101

    [11]

    Magoni D 2003 IEEE J. Sel. Area. Commun. 21 949

    [12]

    Samant K, Bhattacharyya S 2004 Proceedings of the 37th Annual Hawaii International Conference on System Sciences Washington, USA, January 5-8, 2004 p289

    [13]

    Freeman L C 1977 Sociometry 40 35

    [14]

    Holme P, Kim B J, Yoon C N, Han S K 2002 Phys. Rev. E 65 056109

    [15]

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

    [16]

    Bryan K, Leise T 2006 SIAM Rev. 48 569

    [17]

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

    [18]

    Barabasi A L, Albert R 1999 Science 286 509

    [19]

    Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031

    [20]

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

    [21]

    Centola D 2010 Science 329 1194

    [22]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [23]

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

    [24]

    Codd E F 1970 Commun. ACM 13 377

    [25]

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

    [26]

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

    [27]

    Li P X, Ren Y Q, Xi Y M, 2004 Syst. Eng. 22 13 (in Chinese) [李鹏翔, 任玉晴, 席酉民 系统工程 2004 22 13]

    [28]

    He N, Li D, Gan W Y, Zhu X 2007 Comput. Sci. 34 1 (in Chinese) [赫南, 李德, 淦文燕, 朱熙 2007计算机科学 34 1]

    [29]

    Batagelj V, Mrvar A 1998 Connections 21 47

    [30]

    Strogatz S H 1998 Nature 393 440

    [31]

    Klemm K, Serrano M, Eguiluz V, Miguel M 2012 Sci. Rep. 2 292

    [32]

    Borge-Holthoefer J, Moreno Y 2012 Phys. Rev. E 85 026116

  • [1]

    Newman M E J 2003 SIAM Rev. 45 167

    [2]

    Barabasi A L 2009 Science 325 412

    [3]

    Zhou T, Bai W J, Wang B H, Liu Z J, Yan G 2005 Physics 34 31 (in Chinese) [周涛, 柏文洁, 汪秉宏, 刘之景, 严钢2005 物理 34 31]

    [4]

    Liu J G, Wang Z T, Dang Y Z 2005 Mod. Phys. Lett. B 19 785

    [5]

    Zhou X, Zhang F M, Zhou W P, Zhou W, Yang F 2012 Acta Phys. Sin. 61 190201 (in Chinese) [周漩, 张凤鸣, 周卫平, 邹伟, 杨帆 2012 物理学报 61 190201]

    [6]

    Tan Y J, Wu J, Deng H Z, Zhu D Z 2006 Syst. Eng. 24 1 (in Chinese) [谭跃进, 吴俊, 邓宏钟, 朱大智 2006系统工程 24 1]

    [7]

    Liu H K, Zhou T 2007 Acta Phys. Sin. 56 106 (in Chinese) [刘宏鲲, 周涛 2007物理学报 56 106]

    [8]

    Jeong H, Mason S, Barabasi A L 2001 Nature 411 41

    [9]

    Dunne J A, Williams R J, Martinez N D 2002 Ecol. Lett. 5 558

    [10]

    Newman M E J, Forrest S, Balthrop A 2002 J. Phys. Rev. E 66 035101

    [11]

    Magoni D 2003 IEEE J. Sel. Area. Commun. 21 949

    [12]

    Samant K, Bhattacharyya S 2004 Proceedings of the 37th Annual Hawaii International Conference on System Sciences Washington, USA, January 5-8, 2004 p289

    [13]

    Freeman L C 1977 Sociometry 40 35

    [14]

    Holme P, Kim B J, Yoon C N, Han S K 2002 Phys. Rev. E 65 056109

    [15]

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

    [16]

    Bryan K, Leise T 2006 SIAM Rev. 48 569

    [17]

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

    [18]

    Barabasi A L, Albert R 1999 Science 286 509

    [19]

    Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031

    [20]

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

    [21]

    Centola D 2010 Science 329 1194

    [22]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [23]

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

    [24]

    Codd E F 1970 Commun. ACM 13 377

    [25]

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

    [26]

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

    [27]

    Li P X, Ren Y Q, Xi Y M, 2004 Syst. Eng. 22 13 (in Chinese) [李鹏翔, 任玉晴, 席酉民 系统工程 2004 22 13]

    [28]

    He N, Li D, Gan W Y, Zhu X 2007 Comput. Sci. 34 1 (in Chinese) [赫南, 李德, 淦文燕, 朱熙 2007计算机科学 34 1]

    [29]

    Batagelj V, Mrvar A 1998 Connections 21 47

    [30]

    Strogatz S H 1998 Nature 393 440

    [31]

    Klemm K, Serrano M, Eguiluz V, Miguel M 2012 Sci. Rep. 2 292

    [32]

    Borge-Holthoefer J, Moreno Y 2012 Phys. Rev. E 85 026116

  • [1] 杨武华, 王彩琳, 张如亮, 张超, 苏乐. 高压IGBT雪崩鲁棒性的研究. 物理学报, 2023, 72(7): 078501. doi: 10.7498/aps.72.20222248
    [2] 潘倩倩, 刘润然, 贾春晓. 具有弱依赖组的复杂网络上的级联失效. 物理学报, 2022, 71(11): 110505. doi: 10.7498/aps.70.20210850
    [3] 赵豪, 冯晋霞, 孙婧可, 李渊骥, 张宽收. 连续变量Einstein-Podolsky-Rosen纠缠态光场在光纤信道中分发时纠缠的鲁棒性. 物理学报, 2022, 71(9): 094202. doi: 10.7498/aps.71.20212380
    [4] 杨松青, 蒋沅, 童天驰, 严玉为, 淦各升. 基于Tsallis熵的复杂网络节点重要性评估方法. 物理学报, 2021, 70(21): 216401. doi: 10.7498/aps.70.20210979
    [5] 薛晓丹, 王美丽, 邵雨竹, 王俊松. 基于抑制性突触可塑性的神经元放电率自稳态机制. 物理学报, 2019, 68(7): 078701. doi: 10.7498/aps.68.20182234
    [6] 黄丽亚, 汤平川, 霍宥良, 郑义, 成谢锋. 基于加权K-阶传播数的节点重要性. 物理学报, 2019, 68(12): 128901. doi: 10.7498/aps.68.20190087
    [7] 孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 物理学报, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
    [8] 王雨, 郭进利. 基于多重影响力矩阵的有向加权网络节点重要性评估方法. 物理学报, 2017, 66(5): 050201. doi: 10.7498/aps.66.050201
    [9] 阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 物理学报, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
    [10] 高彦丽, 陈世明. 一种全局同质化相依网络耦合模式. 物理学报, 2016, 65(14): 148901. doi: 10.7498/aps.65.148901
    [11] 宋玉萍, 倪静. 网络集聚性对节点中心性指标的准确性影响. 物理学报, 2016, 65(2): 028901. doi: 10.7498/aps.65.028901
    [12] 彭兴钊, 姚宏, 杜军, 王哲, 丁超. 负荷作用下相依网络中的级联故障. 物理学报, 2015, 64(4): 048901. doi: 10.7498/aps.64.048901
    [13] 侯绿林, 老松杨, 肖延东, 白亮. 复杂网络可控性研究现状综述. 物理学报, 2015, 64(18): 188901. doi: 10.7498/aps.64.188901
    [14] 陈世明, 吕辉, 徐青刚, 许云飞, 赖强. 基于度的正/负相关相依网络模型及其鲁棒性研究. 物理学报, 2015, 64(4): 048902. doi: 10.7498/aps.64.048902
    [15] 陈世明, 邹小群, 吕辉, 徐青刚. 面向级联失效的相依网络鲁棒性研究. 物理学报, 2014, 63(2): 028902. doi: 10.7498/aps.63.028902
    [16] 刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. 物理学报, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
    [17] 于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法. 物理学报, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
    [18] 缪志强, 王耀南. 基于径向小波神经网络的混沌系统鲁棒自适应反演控制. 物理学报, 2012, 61(3): 030503. doi: 10.7498/aps.61.030503
    [19] 温淑焕, 袁俊英. 基于无源性的不确定机器人的力控制. 物理学报, 2010, 59(3): 1615-1619. doi: 10.7498/aps.59.1615
    [20] 曾高荣, 裘正定. 数字水印的鲁棒性评测模型. 物理学报, 2010, 59(8): 5870-5879. doi: 10.7498/aps.59.5870
计量
  • 文章访问数:  9268
  • PDF下载量:  2007
  • 被引次数: 0
出版历程
  • 收稿日期:  2013-01-16
  • 修回日期:  2013-02-06
  • 刊出日期:  2013-06-05

/

返回文章
返回