搜索

x

留言板

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

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

一种新的网络传播中最有影响力的节点发现方法

胡庆成 尹龑燊 马鹏斐 高旸 张勇 邢春晓

引用本文:
Citation:

一种新的网络传播中最有影响力的节点发现方法

胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓

A new approach to identify influential spreaders in complex networks

Hu Qing-Cheng, Yin Yan-Shen, Ma Peng-Fei, Gao Yang, Zhang Yong, Xing Chun-Xiao
PDF
导出引用
  • 在复杂网络的传播模型研究中, 如何发现最具影响力的传播节点在理论和现实应用中都有重大的意义. 目前的研究一般使用节点的度数、紧密度、介数和K-shell等中心化指标来评价影响力, 这种方法虽然简单, 但是由于它们仅利用了节点自身的内部属性, 因而在评价影响力时精确度并不高, 普遍性适用性较弱.为了解决这个问题, 本文提出了KSC (K-shell and community centrality)指标模型. 此模型不但考虑了节点的内部属性, 而且还综合考虑了节点的外部属性, 例如节点所属的社区等. 然后利用SIR (susceptible-infected-recovered)模型对传播过程进行仿真, 实验证明所提出的方法可以更好地发现最具有影响力的节点, 且可适用于各种复杂网络. 本文为这项具有挑战性研究提供了新的思想和方法.
    In the research of the propagation model of complex network, it is of theoretical and practical significance to detect the most influential nodes. Global metrics such as degree centrality, closeness centrality, betweenness centrality and K-shell centrality can be used to identify the influential spreaders. Each of these approaches is simple but has a low accuracy. We propose K-shell and community centrality (KSC) model. This model considers not only the internal properties of nodes but also the external properties, such as the community which these nodes belong to. The susceptible-infected-recovered model is used to evaluate the performance of KSC model. The experimental result shows that our method is better to detect the most influential nodes. This paper comes up with a new idea and method for the study in this field.
    • 基金项目: 国家重点基础研究发展计划(批准号: 2011CB302302)和国家高技术研究发展计划(批准号: 2012AA09A408)资助的课题.
    • Funds: Project supported by National Basic Research Program of China (Grant No. 2011CB302302) and the National High Technology Research and Development Program of China (Grant No. 2012AA09A408).
    [1]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [2]

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

    [3]

    Barabási A L, Albert R, Jeong H, Bianconi G 2000 Science 287 2115a

    [4]

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

    [5]

    Kempe D, Kleinberg J, Tardos E 2003 Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining New Washington, DC, USA, August 24-27, 2003 p137

    [6]

    Gomez-Rodriguez M, Leskovec J, Krause A 2010 Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining Washington, DC, USA, July 25-28, 2010 p1019

    [7]

    Budak C, Agrawal D, El Abbadi A 2011 Proceedings of the 20th International Conference on World Wide Web Hyderabad, India, March 28-April 1, 2011 p665

    [8]

    Mislove A, Marcon M, Gummadi K P, Druschel P, Bhattacharjee B 2007 Proceedings of the ACM SIGCOMM 2007 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications Kyoto, Japan, August 27-31, 2007 p29

    [9]

    Yuan W G, Liu Y, Cheng J J 2013 Acta Phys. Sin. 62 038901 (in Chinese) [苑卫国, 刘云, 程军军 2013 物理学报 62 038901]

    [10]

    Weng J, Lim E P, Jiang J, He Q 2010 Proceedings of the Third International Conference on Web Search and Web Data Mining, WSDM 2010 New York, NY, USA, February 4-6, 2010 p261

    [11]

    Xu D, Li X, Wang X F 2007 Acta Phys. Sin. 56 1313 (in Chinese) [许丹, 李翔, 汪小帆 2007 物理学报 56 1313]

    [12]

    Naveed N, Gottron T, Kunegis J, Alhadi A C 2011 Proceedings of the 20th ACM International Conference on Information and Knowledge Management Koblenz, Germany, June 14-17, 2011 p1

    [13]

    Gu Y R, Xia L L 2012 Acta Phys. Sin. 61 238701 (in Chinese) [顾亦然, 夏玲玲 2012 物理学报 61 238701]

    [14]

    Swamynathan G, Wilson C, Boe B, Almeroth K, Zhao B Y 2008 Proceedings of the First Workshop on Online Social Networks ACM New York, USA, August 18, 2008 p1

    [15]

    Mislove A, Marcon M, Krishna P G, Druschel P, Bhattacharjee B 2007 Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement (IMC'07) ACM New York, USA, October 24-26, 2007 p29

    [16]

    Albert R, Jeong H, Barabasi A L 2000 Nature 406 378

    [17]

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

    [18]

    Freeman L C 1977 Sociometry 40 35

    [19]

    Brin S, Page L 1998 Comput. Netw. ISDN Syst. 30 107

    [20]

    Opsahl T, Agneessens F, Skvoretz J 2010 Soc. Networks 32 245

    [21]

    Sabidussi G 1966 Psychometrika 31 581

    [22]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Tech. Rep. Phys. Soc. 1001 5285

    [23]

    Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E 2007 Proc. Natl. Acad. Sci. USA 104 p1150

    [24]

    Girvan M, Newman M E J 2002 Proc. Natl. Acad. Sci. USA 99 7821

    [25]

    Fortunato S 2010 Phys. Rep. 486 75

    [26]

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

    [27]

    Freeman L C 1979 Social Networks 1 215

    [28]

    Sabidussi G 1966 Psychometrika 31 581

    [29]

    Lin K 1970 Bell Syst. Tech. J. 49 291

    [30]

    Newman M E J 2004 Phys. J. B 38 321

    [31]

    Newman M E J 2004 Phys. Rev. E 69 066133

    [32]

    Guimera R, Amaral L A N 2005 Nature 433 7028

    [33]

    Burt R 2004 Am. J. Soc. 110 349

    [34]

    Granovetter M 1973 Am. J. Soc. 78 1360

    [35]

    Roy M Anderson, Robert M May 1992 Infectious Diseases of Humans: Dynamics and Control. (New York: Oxford University Press) p66

    [36]

    Diekmann O, Heesterbeek J A P 2001 Mathematical Epidemiology of Infectious Diseases: Model Building, Analysis and Interpretation (New York: Wiley Series in Mathematical & Computational Biology)

    [37]

    Hethcote H W 2000 Soc. Industr. Appl. Math. 42 599

    [38]

    Bernoulli D, Blower S 2004 Rev. Med. Virol. 14 275

    [39]

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

    [40]

    Xie N 2006 M. S. Dissertation (Bristo: University of Bristol)

    [41]

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

    [42]

    Spring N, Mahajan R, Wetherall D, Anderson T 2004 Acm. Sigcomm. Comp. Commu. Rev. 32 3

    [43]

    Guimerá R, Danon L, Díaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103

  • [1]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [2]

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

    [3]

    Barabási A L, Albert R, Jeong H, Bianconi G 2000 Science 287 2115a

    [4]

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

    [5]

    Kempe D, Kleinberg J, Tardos E 2003 Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining New Washington, DC, USA, August 24-27, 2003 p137

    [6]

    Gomez-Rodriguez M, Leskovec J, Krause A 2010 Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining Washington, DC, USA, July 25-28, 2010 p1019

    [7]

    Budak C, Agrawal D, El Abbadi A 2011 Proceedings of the 20th International Conference on World Wide Web Hyderabad, India, March 28-April 1, 2011 p665

    [8]

    Mislove A, Marcon M, Gummadi K P, Druschel P, Bhattacharjee B 2007 Proceedings of the ACM SIGCOMM 2007 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications Kyoto, Japan, August 27-31, 2007 p29

    [9]

    Yuan W G, Liu Y, Cheng J J 2013 Acta Phys. Sin. 62 038901 (in Chinese) [苑卫国, 刘云, 程军军 2013 物理学报 62 038901]

    [10]

    Weng J, Lim E P, Jiang J, He Q 2010 Proceedings of the Third International Conference on Web Search and Web Data Mining, WSDM 2010 New York, NY, USA, February 4-6, 2010 p261

    [11]

    Xu D, Li X, Wang X F 2007 Acta Phys. Sin. 56 1313 (in Chinese) [许丹, 李翔, 汪小帆 2007 物理学报 56 1313]

    [12]

    Naveed N, Gottron T, Kunegis J, Alhadi A C 2011 Proceedings of the 20th ACM International Conference on Information and Knowledge Management Koblenz, Germany, June 14-17, 2011 p1

    [13]

    Gu Y R, Xia L L 2012 Acta Phys. Sin. 61 238701 (in Chinese) [顾亦然, 夏玲玲 2012 物理学报 61 238701]

    [14]

    Swamynathan G, Wilson C, Boe B, Almeroth K, Zhao B Y 2008 Proceedings of the First Workshop on Online Social Networks ACM New York, USA, August 18, 2008 p1

    [15]

    Mislove A, Marcon M, Krishna P G, Druschel P, Bhattacharjee B 2007 Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement (IMC'07) ACM New York, USA, October 24-26, 2007 p29

    [16]

    Albert R, Jeong H, Barabasi A L 2000 Nature 406 378

    [17]

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

    [18]

    Freeman L C 1977 Sociometry 40 35

    [19]

    Brin S, Page L 1998 Comput. Netw. ISDN Syst. 30 107

    [20]

    Opsahl T, Agneessens F, Skvoretz J 2010 Soc. Networks 32 245

    [21]

    Sabidussi G 1966 Psychometrika 31 581

    [22]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Tech. Rep. Phys. Soc. 1001 5285

    [23]

    Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E 2007 Proc. Natl. Acad. Sci. USA 104 p1150

    [24]

    Girvan M, Newman M E J 2002 Proc. Natl. Acad. Sci. USA 99 7821

    [25]

    Fortunato S 2010 Phys. Rep. 486 75

    [26]

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

    [27]

    Freeman L C 1979 Social Networks 1 215

    [28]

    Sabidussi G 1966 Psychometrika 31 581

    [29]

    Lin K 1970 Bell Syst. Tech. J. 49 291

    [30]

    Newman M E J 2004 Phys. J. B 38 321

    [31]

    Newman M E J 2004 Phys. Rev. E 69 066133

    [32]

    Guimera R, Amaral L A N 2005 Nature 433 7028

    [33]

    Burt R 2004 Am. J. Soc. 110 349

    [34]

    Granovetter M 1973 Am. J. Soc. 78 1360

    [35]

    Roy M Anderson, Robert M May 1992 Infectious Diseases of Humans: Dynamics and Control. (New York: Oxford University Press) p66

    [36]

    Diekmann O, Heesterbeek J A P 2001 Mathematical Epidemiology of Infectious Diseases: Model Building, Analysis and Interpretation (New York: Wiley Series in Mathematical & Computational Biology)

    [37]

    Hethcote H W 2000 Soc. Industr. Appl. Math. 42 599

    [38]

    Bernoulli D, Blower S 2004 Rev. Med. Virol. 14 275

    [39]

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

    [40]

    Xie N 2006 M. S. Dissertation (Bristo: University of Bristol)

    [41]

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

    [42]

    Spring N, Mahajan R, Wetherall D, Anderson T 2004 Acm. Sigcomm. Comp. Commu. Rev. 32 3

    [43]

    Guimerá R, Danon L, Díaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103

  • [1] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 0(0): 0-0. doi: 10.7498/aps.71.20220565
    [2] 杨青林, 王立夫, 李欢, 余牧舟. 基于相对距离的复杂网络谱粗粒化方法. 物理学报, 2019, 68(10): 100501. doi: 10.7498/aps.68.20181848
    [3] 孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 物理学报, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
    [4] 苏臻, 高超, 李向华. 节点中心性对复杂网络传播模式的影响分析. 物理学报, 2017, 66(12): 120201. doi: 10.7498/aps.66.120201
    [5] 周建, 贾贞, 李科赞. 复杂网络谱粗粒化方法的改进算法. 物理学报, 2017, 66(6): 060502. doi: 10.7498/aps.66.060502
    [6] 阮逸润, 老松杨, 王竣德, 白亮, 侯绿林. 一种改进的基于信息传播率的复杂网络影响力评估算法. 物理学报, 2017, 66(20): 208901. doi: 10.7498/aps.66.208901
    [7] 韩忠明, 陈炎, 李梦琪, 刘雯, 杨伟杰. 一种有效的基于三角结构的复杂网络节点影响力度量模型. 物理学报, 2016, 65(16): 168901. doi: 10.7498/aps.65.168901
    [8] 闵磊, 刘智, 唐向阳, 陈矛, 刘三(女牙). 基于扩展度的复杂网络传播影响力评估算法. 物理学报, 2015, 64(8): 088901. doi: 10.7498/aps.64.088901
    [9] 韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰. 面向结构洞的复杂网络关键节点排序. 物理学报, 2015, 64(5): 058902. doi: 10.7498/aps.64.058902
    [10] 胡庆成, 张勇, 许信辉, 邢春晓, 陈池, 陈信欢. 一种新的复杂网络影响力最大化发现方法. 物理学报, 2015, 64(19): 190101. doi: 10.7498/aps.64.190101
    [11] 苏晓萍, 宋玉蓉. 利用邻域“结构洞”寻找社会网络中最具影响力节点. 物理学报, 2015, 64(2): 020101. doi: 10.7498/aps.64.020101
    [12] 刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. 物理学报, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
    [13] 任卓明, 刘建国, 邵凤, 胡兆龙, 郭强. 复杂网络中最小K-核节点的传播能力分析. 物理学报, 2013, 62(10): 108902. doi: 10.7498/aps.62.108902
    [14] 于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法. 物理学报, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
    [15] 刘金良. 具有随机节点结构的复杂网络同步研究. 物理学报, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [16] 周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. 物理学报, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
    [17] 吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. 物理学报, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [18] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [19] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [20] 李 季, 汪秉宏, 蒋品群, 周 涛, 王文旭. 节点数加速增长的复杂网络生长模型. 物理学报, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
计量
  • 文章访问数:  5756
  • PDF下载量:  2226
  • 被引次数: 0
出版历程
  • 收稿日期:  2013-01-25
  • 修回日期:  2013-03-25
  • 刊出日期:  2013-07-05

一种新的网络传播中最有影响力的节点发现方法

  • 1. 清华大学计算机系, 信息技术研究院, 清华信息科学与技术国家实验室, 北京 100084
    基金项目: 国家重点基础研究发展计划(批准号: 2011CB302302)和国家高技术研究发展计划(批准号: 2012AA09A408)资助的课题.

摘要: 在复杂网络的传播模型研究中, 如何发现最具影响力的传播节点在理论和现实应用中都有重大的意义. 目前的研究一般使用节点的度数、紧密度、介数和K-shell等中心化指标来评价影响力, 这种方法虽然简单, 但是由于它们仅利用了节点自身的内部属性, 因而在评价影响力时精确度并不高, 普遍性适用性较弱.为了解决这个问题, 本文提出了KSC (K-shell and community centrality)指标模型. 此模型不但考虑了节点的内部属性, 而且还综合考虑了节点的外部属性, 例如节点所属的社区等. 然后利用SIR (susceptible-infected-recovered)模型对传播过程进行仿真, 实验证明所提出的方法可以更好地发现最具有影响力的节点, 且可适用于各种复杂网络. 本文为这项具有挑战性研究提供了新的思想和方法.

English Abstract

参考文献 (43)

目录

    /

    返回文章
    返回