搜索

文章查询

x

留言板

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

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

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

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

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

胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓
PDF
导出引用
导出核心图
  • 在复杂网络的传播模型研究中, 如何发现最具影响力的传播节点在理论和现实应用中都有重大的意义. 目前的研究一般使用节点的度数、紧密度、介数和K-shell等中心化指标来评价影响力, 这种方法虽然简单, 但是由于它们仅利用了节点自身的内部属性, 因而在评价影响力时精确度并不高, 普遍性适用性较弱.为了解决这个问题, 本文提出了KSC (K-shell and community centrality)指标模型. 此模型不但考虑了节点的内部属性, 而且还综合考虑了节点的外部属性, 例如节点所属的社区等. 然后利用SIR (susceptible-infected-recovered)模型对传播过程进行仿真, 实验证明所提出的方法可以更好地发现最具有影响力的节点, 且可适用于各种复杂网络. 本文为这项具有挑战性研究提供了新的思想和方法.
    • 基金项目: 国家重点基础研究发展计划(批准号: 2011CB302302)和国家高技术研究发展计划(批准号: 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] 苏晓萍, 宋玉蓉. 利用邻域“结构洞”寻找社会网络中最具影响力节点. 物理学报, 2015, 64(2): 020101. doi: 10.7498/aps.64.020101
    [2] 胡庆成, 张勇, 许信辉, 邢春晓, 陈池, 陈信欢. 一种新的复杂网络影响力最大化发现方法. 物理学报, 2015, 64(19): 190101. doi: 10.7498/aps.64.190101
    [3] 阮逸润, 老松杨, 王竣德, 白亮, 侯绿林. 一种改进的基于信息传播率的复杂网络影响力评估算法. 物理学报, 2017, 66(20): 208901. doi: 10.7498/aps.66.208901
    [4] 汪秉宏, 周 涛, 王文旭, 李 季, 蒋品群. 节点数加速增长的复杂网络生长模型. 物理学报, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
    [5] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [6] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [7] 吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. 物理学报, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [8] 周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. 物理学报, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
    [9] 刘金良. 具有随机节点结构的复杂网络同步研究. 物理学报, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [10] 韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰. 面向结构洞的复杂网络关键节点排序. 物理学报, 2015, 64(5): 058902. doi: 10.7498/aps.64.058902
  • 引用本文:
    Citation:
计量
  • 文章访问数:  1728
  • PDF下载量:  2153
  • 被引次数: 0
出版历程
  • 收稿日期:  2013-01-25
  • 修回日期:  2013-03-25
  • 刊出日期:  2013-07-20

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

  • 1. 清华大学计算机系, 信息技术研究院, 清华信息科学与技术国家实验室, 北京 100084
    基金项目: 

    国家重点基础研究发展计划(批准号: 2011CB302302)和国家高技术研究发展计划(批准号: 2012AA09A408)资助的课题.

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

English Abstract

参考文献 (43)

目录

    /

    返回文章
    返回