搜索

x

留言板

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

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

基于扩展度的复杂网络传播影响力评估算法

闵磊 刘智 唐向阳 陈矛 刘三(女牙)

引用本文:
Citation:

基于扩展度的复杂网络传播影响力评估算法

闵磊, 刘智, 唐向阳, 陈矛, 刘三(女牙)

Evaluating influential spreaders in complex networks by extension of degree

Min Lei, Liu Zhi, Tang Xiang-Yang, Chen Mao, Liu San-Ya
PDF
导出引用
  • 对网络中节点的传播影响力进行评估具有十分重要的意义, 有助于促进有益或抑制有害信息的传播. 目前, 多种中心性指标可用于对节点的传播影响力进行评估, 然而它们一般只有当传播率处于特定范围时才能取得理想的结果. 例如, 度值中心性指标在传播率较小时较为合适, 而半局部中心性和接近中心性指标则适用于稍大一些的传播率. 为了解决各种评估指标对传播率敏感的问题, 提出了一种基于扩展度的传播影响力评估算法. 算法利用邻居节点度值叠加的方式对节点度的覆盖范围进行了扩展, 使不同的扩展层次对应于不同的传播率, 并通过抽样测试确定了适合于特定传播率的层次数. 真实和模拟数据集上的实验结果表明, 通过扩展度算法得到的扩展度指标能在不同传播率下对节点的传播影响力进行有效评估, 其准确性能够达到或优于利用其他中心性指标进行评估的结果.
    Evaluating influential spreaders in networks is of great significance for promoting the dissemination of beneficial information or inhibiting the spreading of harmful information. Currently, there are some central indices that can be used to evaluate spreading influence of {nodes}. However, most of them ignore the spreading probability and take into consideration only the network topology or the location of source node, so the excellent results can be achieved only when the spreading probability is in a specified range. For example, the degree centrality is appropriate for a minor spreading probability, but to ensure the accuracy, semi-local and closeness centralities are more suitable for a slightly larger one. To solve the sensitivity problem of spreading probability, a novel algorithm is proposed based on the extension of degree. In this algorithm, the coverage area of degree is recursively extended by the overlapping of degree of neighbors, which makes different extension levels correspond to different spreading probabilities. For a certain spreading probability, the proper level index is calculated by finding the most correlate ranking sequences of sampling {nodes}, which is obtained by matching the results of different spreading levels and SIR simulation. In this paper, the relationship between extension level and spreading probability is explained by the theory of fitting the weight and infected possibility of {nodes}, and the feasibility of the sampling method is verified by the computational experiments. The experimental results on both real and computer-generated datasets show that the proposed algorithm can effectively evaluate the spreading influences of {nodes} under different spreading probabilities, and the performance is close or even superior to that evaluated by using other central indices.
    • 基金项目: 国家科技支撑计划(批准号: 2013BAH72B01)、教育部新世纪优秀人才支持计划 (批准号: NCET-11-0654)和教育部-中国移动科研基金(2012)研发项目(批准号: MCM20121061)资助的课题.
    • Funds: Project supported by the National Key Technology Research and Development Program of the Ministry of Science and Technology of China (Grant No. 2013BAH72B01), the Program for New Century Excellent Talents in University of Ministry of Education of China (Grant No. NCET-11-0654), and the Scientific Research Foundation of Ministry of Education of China and China Mobile Limited (Grant No. MCM20121061).
    [1]

    Zhang W, Bai S Y, Jin R 2014 Int. J. Mod. Phys. B 28 1450136

    [2]

    Newman M E J 2003 SIAM Rev. 45 167

    [3]

    Albert R, Barabasi A L 2002 Rev. Mod. Phys. 74 47

    [4]

    Wu Y, Hu Y, He X H, Deng K 2014 Chin. Phys. B 23 060101

    [5]

    Balthrop J, Forrest S, Newman M E J, Williamson M M 2004 Science 304 527

    [6]

    Li K Z, Xu Z P, Zhu G H, Ding Y 2014 Chin. Phys. B 23 118904

    [7]

    Freeman L C 1978-1979 Soc. Networks 1 215

    [8]

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

    [9]

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

    [10]

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

    [11]

    Bae J, Kim S 2014 Physica A 395 549

    [12]

    Gao S, Ma J, Chen Z M, Wang G H, Xing C M 2014 Physica A 403 130

    [13]

    Du Y X, Gao C, Hu Y, Mahadevan S, Deng Y 2014 Physica A 399 57

    [14]

    Ren Z M, Liu J G, Shao F, Hu Z L, Guo Q 2013 Acta Phys. Sin. 62 108902 (in Chinese) [任卓明, 刘建国, 邵凤, 胡兆龙, 郭强 2013 物理学报 62 108902]

    [15]

    Ren X L, L L Y 2014 Chin. Sci. Bul. 59 1175 (in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]

    [16]

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

    [17]

    Liu Y, Tang M, Zhou T, Do Y 2014 arXiv:1409.5187v1 [physics. soc-ph]

    [18]

    Wang W, Tang M, Yang H, Do Y, Lai Y C, Lee G W 2014 Sci. Rep. 4 5097

    [19]

    Wang W, Tang M, Zhang H F, Gao H, Do Y, Liu Z H 2014 Phys. Rev. E 90 042803

    [20]

    Newman M E J 2002 Phys. Rev. E 66 016128

    [21]

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

    [22]

    Kendall M G 1938 Biometrika 30 81

    [23]

    Hu Q C, Yin Y S, Ma P F, Gao Y, Zhang Y, Xing C X 2013 Acta Phys. Sin. 62 140101 (in Chinese) [胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓 2013 物理学报 62 140101]

    [24]

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

    [25]

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

    [26]

    Palla G, Derenyi I, Farkas I, Vicsek T 2005 Nature 435 814

    [27]

    Guimera R, Danon L, Diaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103

    [28]

    Boguna M, Pastor-Satorras R, Diaz-Guilera A, Arenas A 2004 Phys. Rev. E 70 056122

    [29]

    Castellano C, Pastor-Satorras R 2010 Phys. Rev. Lett. 105 218701

    [30]

    Lancichinetti A, Fortunato S, Radicchi F 2008 Phys. Rev. E 78 046110

  • [1]

    Zhang W, Bai S Y, Jin R 2014 Int. J. Mod. Phys. B 28 1450136

    [2]

    Newman M E J 2003 SIAM Rev. 45 167

    [3]

    Albert R, Barabasi A L 2002 Rev. Mod. Phys. 74 47

    [4]

    Wu Y, Hu Y, He X H, Deng K 2014 Chin. Phys. B 23 060101

    [5]

    Balthrop J, Forrest S, Newman M E J, Williamson M M 2004 Science 304 527

    [6]

    Li K Z, Xu Z P, Zhu G H, Ding Y 2014 Chin. Phys. B 23 118904

    [7]

    Freeman L C 1978-1979 Soc. Networks 1 215

    [8]

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

    [9]

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

    [10]

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

    [11]

    Bae J, Kim S 2014 Physica A 395 549

    [12]

    Gao S, Ma J, Chen Z M, Wang G H, Xing C M 2014 Physica A 403 130

    [13]

    Du Y X, Gao C, Hu Y, Mahadevan S, Deng Y 2014 Physica A 399 57

    [14]

    Ren Z M, Liu J G, Shao F, Hu Z L, Guo Q 2013 Acta Phys. Sin. 62 108902 (in Chinese) [任卓明, 刘建国, 邵凤, 胡兆龙, 郭强 2013 物理学报 62 108902]

    [15]

    Ren X L, L L Y 2014 Chin. Sci. Bul. 59 1175 (in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]

    [16]

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

    [17]

    Liu Y, Tang M, Zhou T, Do Y 2014 arXiv:1409.5187v1 [physics. soc-ph]

    [18]

    Wang W, Tang M, Yang H, Do Y, Lai Y C, Lee G W 2014 Sci. Rep. 4 5097

    [19]

    Wang W, Tang M, Zhang H F, Gao H, Do Y, Liu Z H 2014 Phys. Rev. E 90 042803

    [20]

    Newman M E J 2002 Phys. Rev. E 66 016128

    [21]

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

    [22]

    Kendall M G 1938 Biometrika 30 81

    [23]

    Hu Q C, Yin Y S, Ma P F, Gao Y, Zhang Y, Xing C X 2013 Acta Phys. Sin. 62 140101 (in Chinese) [胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓 2013 物理学报 62 140101]

    [24]

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

    [25]

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

    [26]

    Palla G, Derenyi I, Farkas I, Vicsek T 2005 Nature 435 814

    [27]

    Guimera R, Danon L, Diaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103

    [28]

    Boguna M, Pastor-Satorras R, Diaz-Guilera A, Arenas A 2004 Phys. Rev. E 70 056122

    [29]

    Castellano C, Pastor-Satorras R 2010 Phys. Rev. Lett. 105 218701

    [30]

    Lancichinetti A, Fortunato S, Radicchi F 2008 Phys. Rev. E 78 046110

  • [1] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 0(0): 0-0. doi: 10.7498/aps.71.20220565
    [2] 阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 物理学报, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
    [3] 苏臻, 高超, 李向华. 节点中心性对复杂网络传播模式的影响分析. 物理学报, 2017, 66(12): 120201. doi: 10.7498/aps.66.120201
    [4] 罗仕龙, 龚凯, 唐朝生, 周靖. 加权网络中基于冗余边过滤的k-核分解排序算法. 物理学报, 2017, 66(18): 188902. doi: 10.7498/aps.66.188902
    [5] 徐明, 许传云, 曹克非. 度相关性对无向网络可控性的影响. 物理学报, 2017, 66(2): 028901. doi: 10.7498/aps.66.028901
    [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(19): 190101. doi: 10.7498/aps.64.190101
    [9] 欧阳博, 金心宇, 夏永祥, 蒋路茸, 吴端坡. 疾病传播与级联失效相互作用的研究:度不相关网络中疾病扩散条件的分析. 物理学报, 2014, 63(21): 218902. doi: 10.7498/aps.63.218902
    [10] 任卓明, 刘建国, 邵凤, 胡兆龙, 郭强. 复杂网络中最小K-核节点的传播能力分析. 物理学报, 2013, 62(10): 108902. doi: 10.7498/aps.62.108902
    [11] 苑卫国, 刘云, 程军军, 熊菲. 微博双向关注网络节点中心性及传播 影响力的分析. 物理学报, 2013, 62(3): 038901. doi: 10.7498/aps.62.038901
    [12] 李泽荃, 张瑞新, 杨曌, 赵红泽, 于健浩. 复杂网络中心性对灾害蔓延的影响. 物理学报, 2012, 61(23): 238902. doi: 10.7498/aps.61.238902
    [13] 张聪, 沈惠璋, 李峰, 杨何群. 复杂网络中社团结构发现的多分辨率密度模块度. 物理学报, 2012, 61(14): 148902. doi: 10.7498/aps.61.148902
    [14] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [15] 李树彬, 吴建军, 高自友, 林勇, 傅白白. 基于复杂网络的交通拥堵与传播动力学分析. 物理学报, 2011, 60(5): 050701. doi: 10.7498/aps.60.050701
    [16] 王亚奇, 蒋国平. 基于元胞自动机考虑传播延迟的复杂网络病毒传播研究. 物理学报, 2011, 60(8): 080510. doi: 10.7498/aps.60.080510
    [17] 王亚奇, 蒋国平. 复杂网络中考虑不完全免疫的病毒传播研究. 物理学报, 2010, 59(10): 6734-6743. doi: 10.7498/aps.59.6734
    [18] 闫小勇, 王明生. 增长速度对合作网络参与者节点度分布的影响. 物理学报, 2010, 59(2): 851-858. doi: 10.7498/aps.59.851
    [19] 宋玉蓉, 蒋国平. 基于一维元胞自动机的复杂网络恶意软件传播研究. 物理学报, 2009, 58(9): 5911-5918. doi: 10.7498/aps.58.5911
    [20] 许 丹, 李 翔, 汪小帆. 复杂网络病毒传播的局域控制研究. 物理学报, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
计量
  • 文章访问数:  4460
  • PDF下载量:  624
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-09-04
  • 修回日期:  2014-11-17
  • 刊出日期:  2015-04-05

基于扩展度的复杂网络传播影响力评估算法

  • 1. 华中师范大学, 国家数字化学习工程技术研究中心, 武汉 430079
    基金项目: 国家科技支撑计划(批准号: 2013BAH72B01)、教育部新世纪优秀人才支持计划 (批准号: NCET-11-0654)和教育部-中国移动科研基金(2012)研发项目(批准号: MCM20121061)资助的课题.

摘要: 对网络中节点的传播影响力进行评估具有十分重要的意义, 有助于促进有益或抑制有害信息的传播. 目前, 多种中心性指标可用于对节点的传播影响力进行评估, 然而它们一般只有当传播率处于特定范围时才能取得理想的结果. 例如, 度值中心性指标在传播率较小时较为合适, 而半局部中心性和接近中心性指标则适用于稍大一些的传播率. 为了解决各种评估指标对传播率敏感的问题, 提出了一种基于扩展度的传播影响力评估算法. 算法利用邻居节点度值叠加的方式对节点度的覆盖范围进行了扩展, 使不同的扩展层次对应于不同的传播率, 并通过抽样测试确定了适合于特定传播率的层次数. 真实和模拟数据集上的实验结果表明, 通过扩展度算法得到的扩展度指标能在不同传播率下对节点的传播影响力进行有效评估, 其准确性能够达到或优于利用其他中心性指标进行评估的结果.

English Abstract

参考文献 (30)

目录

    /

    返回文章
    返回