搜索

x

留言板

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

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

一种有效的基于三角结构的复杂网络节点影响力度量模型

韩忠明 陈炎 李梦琪 刘雯 杨伟杰

引用本文:
Citation:

一种有效的基于三角结构的复杂网络节点影响力度量模型

韩忠明, 陈炎, 李梦琪, 刘雯, 杨伟杰

An efficient node influence metric based on triangle in complex networks

Han Zhong-Ming, Chen Yan, Li Meng-Qi, Liu Wen, Yang Wei-Jie
PDF
导出引用
  • 度量复杂网络中的节点影响力对理解网络的结构和功能起着至关重要的作用. 度、介数、紧密度等经典指标能够一定程度上度量节点影响力,k-shell和H-index等指标也可以应用于评价节点影响力. 然而这些模型都存在着各自的局限性. 本文基于节点与邻居节点之间的三角结构提出了一种有效的节点影响力度量指标模型(local triangle centrality,LTC),该模型不仅考虑节点间的三角结构,同时考虑了周边邻居节点的规模. 我们在多个真实复杂网络上进行了大量实验,通过SIR模型进行节点影响力仿真实验,证明LTC指标相比于其他指标能够更加准确地度量节点的传播影响力. 节点删除后网络鲁棒性的实验结果也表明LTC指标具有更好效果.
    Influential nodes in large-scale complex networks are very important for accelerating information propagation, understanding hierarchical community structure and controlling rumors spreading. Classic centralities such as degree, betweenness and closeness, can be used to measure the node influence. Other systemic metrics, such as k-shell and H-index, take network structure into account to identify influential nodes. However, these methods suffer some drawbacks. For example, betweenness is an effective index to identify influential nodes. However, computing betweenness is a high time complexity task and some nodes with high degree are not highly influential nodes. Presented in this paper is a simple and effective node influence measure index model based on a triangular structure between a node and its neighbor nodes (local triangle centrality (LTC)). The model considers not only the triangle structure between nodes, but also the degree of the surrounding neighbor nodes. However, in complex networks the numbers of triangles for a pair of nodes are extremely unbalanced, a sigmoid function is introduced to bound the number of triangles for each pair of nodes between 0 and 1. The LTC model is very flexible and can be used to measure the node influence on weighted complex networks. We detailedly compare the influential nodes produced by different approaches in Karata network. Results show that LTC can effectively identify the influential nodes. Comprehensive experiments are conducted based on six real complex networks with different network scales. We select highly influential nodes produced by five benchmark approaches and LTC model to run spreading processes by the SIR model, thus we can evaluate the efficacies of different approaches. The experimental results of the SIR model show that LTC metric can more accurately identify highly influential nodes in most real complex networks than other indicators. We also conduct network robustness experiment on four selected networks by computing the ratio of nodes in giant component to remaining nodes after removing highly influential nodes. The experimental results also show that LTC model outperforms other methods.
      通信作者: 韩忠明, hanzm@th.btbu.edu.cn
    • 基金项目: 国家自然科学基金(批准号:61170112)、教育部人文社会科学研究基金项目(批准号:13YJC860006)和北京市教委科学研究面上项目(批准号:KM201410011005)资助的课题.
      Corresponding author: Han Zhong-Ming, hanzm@th.btbu.edu.cn
    • Funds: Project supported by the National Natural Science Foundation of China (Grant No. 61170112), the Research Fund Project of the Ministry of Education of Humanities and Social Science, China (Grant No. 13YJC860006), and the Scientific Research Common Program of Beijing Municipal Commission of Education, China (Grant No. KM201410011005).
    [1]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [2]

    Barabsi A L, Albert R 1999 Science 286 509

    [3]

    Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113

    [4]

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

    [5]

    Motter A E, Lai Y C 2002 Phys. Rev. E 66 065102

    [6]

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

    [7]

    Pei S, Makse H A 2013 J. Stat. Mech. Theory Exp. 2013 P12002

    [8]

    Pastor-Satorras R, Vespignani A 2002 Phys. Rev. E 65 036104

    [9]

    Morone F, Makse H A 2015 Nature 524 65

    [10]

    Bonacich P 1972 J. Math. Sociol. 2 113

    [11]

    Chen D, L L, Shang M S, Zhou T 2012 Physica A: Stat. Mech. Appl. 391 1777

    [12]

    Min L, Liu Z, Tang X Y, Chen M, Liu S Y 2015 Acta Phys. Sin. 64 088901 (in Chinese) [闵磊, 刘智, 唐向阳, 陈矛, 刘三(女牙) 2015 物理学报 64 088901]

    [13]

    Fowler J H, Christakis N A 2008 BMJ 337 a2338

    [14]

    Newman M E J 2005 Social Networks 27 39

    [15]

    Sabidussi G 1966 Psychometrika 31 581

    [16]

    Palla G, Barabsi A L, Vicsek T 2007 Nature 446 664

    [17]

    Chen D B, Gao H, L L Y, Zhou T 2012 PloS One 8 e77455

    [18]

    Zhao Z Y, Yu H, Zhu Z L, Wang X F 2014 Chin. J. Comput. 37 753 (in Chinese) [赵之滢, 于海, 朱志良, 汪小帆 2014 计算机学报 37 753]

    [19]

    Su X P, Song Y R 2015 Acta Phys. Sin. 64 020101 (in Chinese) [苏晓萍, 宋玉蓉 2015 物理学报 64 020101]

    [20]

    Han Z M, Wu Y, Tan X S, Duan D G, Yang W J 2015 Acta Phys. Sin. 64 058902 (in Chinese) [韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰 2015 物理学报 64 058902]

    [21]

    Zhang J X, Chen D B, Dong Q, Zhao D B 2016 arXiv 1602 00070

    [22]

    Berkhin P 2005 Internet Mathematics 2 73

    [23]

    Kleinberg J M 1999 JACM 46 604

    [24]

    Li Q, Zhou T, L L Y, Chen D B 2014 Physica A: Stat. Mech. Appl. 404 47

    [25]

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

    [26]

    Pei S, Muchnik L, Andrade J J S, Zheng Z M, Hernn A M 2014 Sci. Rep. 4 5547

    [27]

    Liu J G, Ren Z M, Guo Q 2013 Physica A: Stat. Mech. Appl. 392 4154

    [28]

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

    [29]

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

    [30]

    Hethcote, Herbert W 2000 SIAM Rev. 42 599

    [31]

    Pastor S R, Castellano C, Van M P, Vespignani A 2015 Rev. Mod. Phys. 87 925

    [32]

    Shu P, Wang W, Tang M, Do Y 2015 Chaos 25 063104

    [33]

    Iyer S, Killingback T, Sundaram B, Wang Z 2013 PloS One 8 e59613

  • [1]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [2]

    Barabsi A L, Albert R 1999 Science 286 509

    [3]

    Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113

    [4]

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

    [5]

    Motter A E, Lai Y C 2002 Phys. Rev. E 66 065102

    [6]

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

    [7]

    Pei S, Makse H A 2013 J. Stat. Mech. Theory Exp. 2013 P12002

    [8]

    Pastor-Satorras R, Vespignani A 2002 Phys. Rev. E 65 036104

    [9]

    Morone F, Makse H A 2015 Nature 524 65

    [10]

    Bonacich P 1972 J. Math. Sociol. 2 113

    [11]

    Chen D, L L, Shang M S, Zhou T 2012 Physica A: Stat. Mech. Appl. 391 1777

    [12]

    Min L, Liu Z, Tang X Y, Chen M, Liu S Y 2015 Acta Phys. Sin. 64 088901 (in Chinese) [闵磊, 刘智, 唐向阳, 陈矛, 刘三(女牙) 2015 物理学报 64 088901]

    [13]

    Fowler J H, Christakis N A 2008 BMJ 337 a2338

    [14]

    Newman M E J 2005 Social Networks 27 39

    [15]

    Sabidussi G 1966 Psychometrika 31 581

    [16]

    Palla G, Barabsi A L, Vicsek T 2007 Nature 446 664

    [17]

    Chen D B, Gao H, L L Y, Zhou T 2012 PloS One 8 e77455

    [18]

    Zhao Z Y, Yu H, Zhu Z L, Wang X F 2014 Chin. J. Comput. 37 753 (in Chinese) [赵之滢, 于海, 朱志良, 汪小帆 2014 计算机学报 37 753]

    [19]

    Su X P, Song Y R 2015 Acta Phys. Sin. 64 020101 (in Chinese) [苏晓萍, 宋玉蓉 2015 物理学报 64 020101]

    [20]

    Han Z M, Wu Y, Tan X S, Duan D G, Yang W J 2015 Acta Phys. Sin. 64 058902 (in Chinese) [韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰 2015 物理学报 64 058902]

    [21]

    Zhang J X, Chen D B, Dong Q, Zhao D B 2016 arXiv 1602 00070

    [22]

    Berkhin P 2005 Internet Mathematics 2 73

    [23]

    Kleinberg J M 1999 JACM 46 604

    [24]

    Li Q, Zhou T, L L Y, Chen D B 2014 Physica A: Stat. Mech. Appl. 404 47

    [25]

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

    [26]

    Pei S, Muchnik L, Andrade J J S, Zheng Z M, Hernn A M 2014 Sci. Rep. 4 5547

    [27]

    Liu J G, Ren Z M, Guo Q 2013 Physica A: Stat. Mech. Appl. 392 4154

    [28]

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

    [29]

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

    [30]

    Hethcote, Herbert W 2000 SIAM Rev. 42 599

    [31]

    Pastor S R, Castellano C, Van M P, Vespignani A 2015 Rev. Mod. Phys. 87 925

    [32]

    Shu P, Wang W, Tang M, Do Y 2015 Chaos 25 063104

    [33]

    Iyer S, Killingback T, Sundaram B, Wang Z 2013 PloS One 8 e59613

  • [1] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
    [2] 任卓明. 动态复杂网络中节点影响力的研究进展. 物理学报, 2020, 69(4): 048901. doi: 10.7498/aps.69.20190830
    [3] 康玲, 项冰冰, 翟素兰, 鲍中奎, 张海峰. 基于区域密度曲线识别网络上的多影响力节点. 物理学报, 2018, 67(19): 198901. doi: 10.7498/aps.67.20181000
    [4] 孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 物理学报, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
    [5] 阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 物理学报, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
    [6] 苏臻, 高超, 李向华. 节点中心性对复杂网络传播模式的影响分析. 物理学报, 2017, 66(12): 120201. doi: 10.7498/aps.66.120201
    [7] 苏晓萍, 宋玉蓉. 利用邻域“结构洞”寻找社会网络中最具影响力节点. 物理学报, 2015, 64(2): 020101. doi: 10.7498/aps.64.020101
    [8] 韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰. 面向结构洞的复杂网络关键节点排序. 物理学报, 2015, 64(5): 058902. doi: 10.7498/aps.64.058902
    [9] 胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓. 一种新的网络传播中最有影响力的节点发现方法 . 物理学报, 2013, 62(14): 140101. doi: 10.7498/aps.62.140101
    [10] 刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. 物理学报, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
    [11] 任卓明, 刘建国, 邵凤, 胡兆龙, 郭强. 复杂网络中最小K-核节点的传播能力分析. 物理学报, 2013, 62(10): 108902. doi: 10.7498/aps.62.108902
    [12] 于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法. 物理学报, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
    [13] 苑卫国, 刘云, 程军军, 熊菲. 微博双向关注网络节点中心性及传播 影响力的分析. 物理学报, 2013, 62(3): 038901. doi: 10.7498/aps.62.038901
    [14] 刘金良. 具有随机节点结构的复杂网络同步研究. 物理学报, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [15] 周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. 物理学报, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
    [16] 吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. 物理学报, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [17] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [18] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [19] 郭进利. 新节点的边对网络无标度性影响. 物理学报, 2008, 57(2): 756-761. doi: 10.7498/aps.57.756
    [20] 李 季, 汪秉宏, 蒋品群, 周 涛, 王文旭. 节点数加速增长的复杂网络生长模型. 物理学报, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
计量
  • 文章访问数:  4574
  • PDF下载量:  647
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-05-10
  • 修回日期:  2016-06-15
  • 刊出日期:  2016-08-05

一种有效的基于三角结构的复杂网络节点影响力度量模型

  • 1. 北京工商大学计算机与信息工程学院, 北京 100048;
  • 2. 食品安全大数据技术北京市重点实验室, 北京 100048
  • 通信作者: 韩忠明, hanzm@th.btbu.edu.cn
    基金项目: 国家自然科学基金(批准号:61170112)、教育部人文社会科学研究基金项目(批准号:13YJC860006)和北京市教委科学研究面上项目(批准号:KM201410011005)资助的课题.

摘要: 度量复杂网络中的节点影响力对理解网络的结构和功能起着至关重要的作用. 度、介数、紧密度等经典指标能够一定程度上度量节点影响力,k-shell和H-index等指标也可以应用于评价节点影响力. 然而这些模型都存在着各自的局限性. 本文基于节点与邻居节点之间的三角结构提出了一种有效的节点影响力度量指标模型(local triangle centrality,LTC),该模型不仅考虑节点间的三角结构,同时考虑了周边邻居节点的规模. 我们在多个真实复杂网络上进行了大量实验,通过SIR模型进行节点影响力仿真实验,证明LTC指标相比于其他指标能够更加准确地度量节点的传播影响力. 节点删除后网络鲁棒性的实验结果也表明LTC指标具有更好效果.

English Abstract

参考文献 (33)

目录

    /

    返回文章
    返回