搜索

x

留言板

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

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

一种新的复杂网络影响力最大化发现方法

胡庆成 张勇 许信辉 邢春晓 陈池 陈信欢

引用本文:
Citation:

一种新的复杂网络影响力最大化发现方法

胡庆成, 张勇, 许信辉, 邢春晓, 陈池, 陈信欢

A new approach for influence maximization in complex networks

Hu Qing-Cheng, Zhang Yong, Xu Xin-Hui, Xing Chun-Xiao, Chen Chi, Chen Xin-Hua
PDF
导出引用
  • 复杂网络中影响力最大化建模与分析是社会网络分析的关键问题之一, 其研究在理论和现实应用中都有重大的意义. 在给定s值的前提下, 如何寻找发现s个最大影响范围的节点集, 这是个组合优化问题, Kempe等已经证明该问题是NP-hard问题. 目前已有的随机算法时间复杂度低, 但是结果最差; 其他贪心算法时间复杂度很高, 不能适用于大型社会网络中, 并且这些典型贪心算法必须以了解网络的全局信息为前提, 而获取整个庞大复杂且不断发展变化的社会网络结构是很难以做到的. 我们提出了一种新的影响力最大化算法模型RMDN, 及改进的模型算法RMDN++, 模型只需要知道随机选择的节点以及其邻居节点信息, 从而巧妙地回避了其他典型贪心算法中必须事先掌握整个网络全局信息的问题, 算法的时间复杂度仅为O(s log(n)); 然后, 我们利用IC模型和LT模型在4种不同的真实复杂网络数据集的实验显示, RMDN, RMDN++算法有着和现有典型算法相近的影响力传播效果, 且有时还略优, 同时在运行时间上则有显著的提高; 我们从理论上推导证明了方法的可行性. 本文所提出的模型算法适用性更广, 可操作性更强, 为这项具有挑战性研究提供了新的思路和方法.
    Influence maximization modeling and analyzing is a critical issue in social network analysis in a complex network environment, and it can be significantly beneficial to both theory and real life. Given a fixed number k, how to find the set size k which has the greatest influencing scope is a combinatory optimization problem that has been proved to be NP-hard by Kempe et al. (2003). State-of-the-art random algorithm, although it is computation efficient, yields the worst performance; on the contrary, the well-studied greedy algorithms can achieve approximately optimal performance but its computing complexity is prohibitive for large social network; meanwhile, these algorithms should first acquire the global information (topology) of the network which is impractical for the colossal and forever changing network. We propose a new algorithm for influence maximization computing-RMDN and its improved version RMDN++. RMDN uses the information of a randomly chosen node and its nearest neighboring nodes which can avoid the procedure of knowing knowledge of the whole network. This can greatly accelerate the computing process, but its computing complexity is limited to the order of O(klog(n)). We use three different real-life datasets to test the effectiveness and efficiency of RMDN in IC model and LT model respectively. Result shows that RMDN has a comparable performance as the greedy algorithms, but obtains orders of magnitude faster according to different network; in the meantime, we have systematically and theoretically studied and proved the feasibility of our method. The wider applicability and stronger operability of RMDN may also shed light on the profound problem of influence maximization in social network.
      通信作者: 胡庆成, hqc10@mails.tsinghua.edu.cn
    • 基金项目: 国家重点基础研究发展(973计划) (批准号: 02011CB3023302)和国家高技术研究发展计划(863 计划) (批准号: SS2015AA020102)资助的课题.
      Corresponding author: Hu Qing-Cheng, hqc10@mails.tsinghua.edu.cn
    • Funds: Project supported by the National Basic Research Program of China (Grant No. 2011CB3023302), and the National High Technology Research and Development Program of China (Grant No. SS2015AA020102).
    [1]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [2]

    Barabsi A L, Albert R 1999 Science 286 509

    [3]

    Barabsi A L, Albert R, Jeong H, Bianconi G 2000 Science 287 2115a

    [4]

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

    [5]

    Hu Q C, Yin Y S, Ma P F 2013 Acta Phys. Sin 62 140101(in Chinese) [胡庆成, 尹龑燊, 马鹏斐 2013 物理学报 62 140101]

    [6]

    Ren Z M, Shao F, Liu J G 2013 Acta Phys. Sin 62 128901(in Chinese) [任卓明, 邵凤, 刘建国 2013 物理学报 62 128901]

    [7]

    Aral S, Walker D 2012 Science 337 337

    [8]

    Liu J G, Ren Z M, Guo Q 2013 Physica A: Statistical Mechanics and its Applications 392 4154

    [9]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nature Physics 6 888

    [10]

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

    [11]

    Liu J G, Ren Z M, Guo Q, et al 2013 Acta Phys. Sin. 62 178901(in Chinese) [刘建国, 任卓明, 郭强 等 2013 物理学报 62 178901]

    [12]

    Domingos P, Richardson M 2001 Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining San Francisco, CA, USA, August 26-29, 2001 p57

    [13]

    Richardson M, Domingos P 2002 Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining Edmonton, Alberta, Canada, July 23-26, 2002 p61

    [14]

    DKempe, JKleinberg, ETardos 2003 Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining New Washington, DC, USA, August 24-27, 2003 p137

    [15]

    Leskovec J, Krause A, Guestrin C 2007 Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining San Jose, CA August 12-15, 2007 p420

    [16]

    Goyal A, Lu W, Lakshmanan L V S 2011 Proceedings of the 20th international conference companion on World wide web Johannesburg,South Africa Sep 14-16, 2011 p47

    [17]

    Zhou C, Zhang P, Guo J 2013 Data Mining (ICDM),2013 IEEE 13th International Conference on. IEEE Dallas, Texas, USA Dec 8-11, 2013 p907

    [18]

    Chen W, Wang Y, Yang S2009 Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining Paris, France June 28-July 1, 2009 p199

    [19]

    Kimura M, Saito K 2006 Knowledge-Based Intelligent Information and Engineering Systems Bournemouth U K, October 9-11, 2006 p937

    [20]

    Chen W, Wang C, Wang Y 2010 Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data miningWashingtonDC, USA, July 25-28, 2010 p1029

    [21]

    Wang Y, Cong G, Song G 2010 Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data miningWashington DC, USA, July 25-28, 2010 p1039

    [22]

    Galstyan A, Musoyan V, Cohen P 2009 Phys. Rev. E 79 056102

    [23]

    Li D, Xu Z M, Chakraborty N 2014 PloS one 9 e102199

    [24]

    Zhou S, Mondragn R J 2004 Commun. Lett. 8 180

    [25]

    Bonacich P 1972 Journal of Mathematical Sociology 2 113

    [26]

    Milgram S 2003 Phys. Rev. Lett. 90 058701

    [27]

    Backstrom L, Boldi P, Rosa M, Ugander J, Vigna S 2012 ACM Web Science 2012: Conference Proceedings Evanston, Illinois, USA, June 2224, 2012 p45

    [28]

    Six Degrees of Separation, Twitter Style fromSysomos Apr 30, 2010

    [29]

    Cohen R, Havlin S 2003 Phys. Rev. Lett. 90 058701

    [30]

    Newman M E J, Strogatz S H, Watts D J 2001 Phys. Rev. E 64 026118

    [31]

    Leskovec J, Mcauley J J 2012 Advances in neural information processing systems South Lake Tahoe, Nevada, United States, December 3-6, 2012 p539

    [32]

    Xie N 2006 Social network analysis of blogs M.Sc. Dissertation, University of Bristol

    [33]

    Li G, Chen S, Feng J 2014 Proceedings of the 2014 ACM SIGMOD international conference on Management of data New York, NY, USA, June 22-25, 2014 p87

    [34]

    Clauset A, Shalizi C R, Newman M E J 2009 SIAM Rev. 51 661

    [35]

    Barabsi A L, Albert R, Jeong H 1999 Physica A 272 173

    [36]

    Newman M E J 2005 Contemporary Physics 46 323

  • [1]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [2]

    Barabsi A L, Albert R 1999 Science 286 509

    [3]

    Barabsi A L, Albert R, Jeong H, Bianconi G 2000 Science 287 2115a

    [4]

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

    [5]

    Hu Q C, Yin Y S, Ma P F 2013 Acta Phys. Sin 62 140101(in Chinese) [胡庆成, 尹龑燊, 马鹏斐 2013 物理学报 62 140101]

    [6]

    Ren Z M, Shao F, Liu J G 2013 Acta Phys. Sin 62 128901(in Chinese) [任卓明, 邵凤, 刘建国 2013 物理学报 62 128901]

    [7]

    Aral S, Walker D 2012 Science 337 337

    [8]

    Liu J G, Ren Z M, Guo Q 2013 Physica A: Statistical Mechanics and its Applications 392 4154

    [9]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nature Physics 6 888

    [10]

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

    [11]

    Liu J G, Ren Z M, Guo Q, et al 2013 Acta Phys. Sin. 62 178901(in Chinese) [刘建国, 任卓明, 郭强 等 2013 物理学报 62 178901]

    [12]

    Domingos P, Richardson M 2001 Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining San Francisco, CA, USA, August 26-29, 2001 p57

    [13]

    Richardson M, Domingos P 2002 Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining Edmonton, Alberta, Canada, July 23-26, 2002 p61

    [14]

    DKempe, JKleinberg, ETardos 2003 Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining New Washington, DC, USA, August 24-27, 2003 p137

    [15]

    Leskovec J, Krause A, Guestrin C 2007 Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining San Jose, CA August 12-15, 2007 p420

    [16]

    Goyal A, Lu W, Lakshmanan L V S 2011 Proceedings of the 20th international conference companion on World wide web Johannesburg,South Africa Sep 14-16, 2011 p47

    [17]

    Zhou C, Zhang P, Guo J 2013 Data Mining (ICDM),2013 IEEE 13th International Conference on. IEEE Dallas, Texas, USA Dec 8-11, 2013 p907

    [18]

    Chen W, Wang Y, Yang S2009 Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining Paris, France June 28-July 1, 2009 p199

    [19]

    Kimura M, Saito K 2006 Knowledge-Based Intelligent Information and Engineering Systems Bournemouth U K, October 9-11, 2006 p937

    [20]

    Chen W, Wang C, Wang Y 2010 Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data miningWashingtonDC, USA, July 25-28, 2010 p1029

    [21]

    Wang Y, Cong G, Song G 2010 Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data miningWashington DC, USA, July 25-28, 2010 p1039

    [22]

    Galstyan A, Musoyan V, Cohen P 2009 Phys. Rev. E 79 056102

    [23]

    Li D, Xu Z M, Chakraborty N 2014 PloS one 9 e102199

    [24]

    Zhou S, Mondragn R J 2004 Commun. Lett. 8 180

    [25]

    Bonacich P 1972 Journal of Mathematical Sociology 2 113

    [26]

    Milgram S 2003 Phys. Rev. Lett. 90 058701

    [27]

    Backstrom L, Boldi P, Rosa M, Ugander J, Vigna S 2012 ACM Web Science 2012: Conference Proceedings Evanston, Illinois, USA, June 2224, 2012 p45

    [28]

    Six Degrees of Separation, Twitter Style fromSysomos Apr 30, 2010

    [29]

    Cohen R, Havlin S 2003 Phys. Rev. Lett. 90 058701

    [30]

    Newman M E J, Strogatz S H, Watts D J 2001 Phys. Rev. E 64 026118

    [31]

    Leskovec J, Mcauley J J 2012 Advances in neural information processing systems South Lake Tahoe, Nevada, United States, December 3-6, 2012 p539

    [32]

    Xie N 2006 Social network analysis of blogs M.Sc. Dissertation, University of Bristol

    [33]

    Li G, Chen S, Feng J 2014 Proceedings of the 2014 ACM SIGMOD international conference on Management of data New York, NY, USA, June 22-25, 2014 p87

    [34]

    Clauset A, Shalizi C R, Newman M E J 2009 SIAM Rev. 51 661

    [35]

    Barabsi A L, Albert R, Jeong H 1999 Physica A 272 173

    [36]

    Newman M E J 2005 Contemporary Physics 46 323

  • [1] 李鑫, 赵城利, 刘阳洋. 有限步传播范围期望指标判别节点传播影响力. 物理学报, 2020, 69(2): 028901. doi: 10.7498/aps.69.20191313
    [2] 杨李, 宋玉蓉, 李因伟. 考虑边聚类与扩散特性的信息传播网络结构优化算法. 物理学报, 2018, 67(19): 190502. doi: 10.7498/aps.67.20180395
    [3] 周建, 贾贞, 李科赞. 复杂网络谱粗粒化方法的改进算法. 物理学报, 2017, 66(6): 060502. doi: 10.7498/aps.66.060502
    [4] 苏臻, 高超, 李向华. 节点中心性对复杂网络传播模式的影响分析. 物理学报, 2017, 66(12): 120201. doi: 10.7498/aps.66.120201
    [5] 肖云鹏, 李松阳, 刘宴兵. 一种基于社交影响力和平均场理论的信息传播动力学模型. 物理学报, 2017, 66(3): 030501. doi: 10.7498/aps.66.030501
    [6] 阮逸润, 老松杨, 王竣德, 白亮, 侯绿林. 一种改进的基于信息传播率的复杂网络影响力评估算法. 物理学报, 2017, 66(20): 208901. doi: 10.7498/aps.66.208901
    [7] 李勇军, 尹超, 于会, 刘尊. 基于最大熵模型的微博传播网络中的链路预测. 物理学报, 2016, 65(2): 020501. doi: 10.7498/aps.65.020501
    [8] 王小娟, 宋梅, 郭世泽, 杨子龙. 基于有向渗流理论的关联微博转发网络信息传播研究. 物理学报, 2015, 64(4): 044502. doi: 10.7498/aps.64.044502
    [9] 闵磊, 刘智, 唐向阳, 陈矛, 刘三(女牙). 基于扩展度的复杂网络传播影响力评估算法. 物理学报, 2015, 64(8): 088901. doi: 10.7498/aps.64.088901
    [10] 王金龙, 刘方爱, 朱振方. 一种基于用户相对权重的在线社交网络信息传播模型. 物理学报, 2015, 64(5): 050501. doi: 10.7498/aps.64.050501
    [11] 刘树新, 季新生, 刘彩霞, 郭虹. 一种信息传播促进网络增长的网络演化模型. 物理学报, 2014, 63(15): 158902. doi: 10.7498/aps.63.158902
    [12] 胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓. 一种新的网络传播中最有影响力的节点发现方法 . 物理学报, 2013, 62(14): 140101. doi: 10.7498/aps.62.140101
    [13] 苑卫国, 刘云, 程军军, 熊菲. 微博双向关注网络节点中心性及传播 影响力的分析. 物理学报, 2013, 62(3): 038901. doi: 10.7498/aps.62.038901
    [14] 吕天阳, 谢文艳, 郑纬民, 朴秀峰. 加权复杂网络社团的评价指标及其发现算法分析. 物理学报, 2012, 61(21): 210511. doi: 10.7498/aps.61.210511
    [15] 王亚奇, 蒋国平. 基于元胞自动机考虑传播延迟的复杂网络病毒传播研究. 物理学报, 2011, 60(8): 080510. doi: 10.7498/aps.60.080510
    [16] 张彦超, 刘云, 张海峰, 程辉, 熊菲. 基于在线社交网络的信息传播模型. 物理学报, 2011, 60(5): 050501. doi: 10.7498/aps.60.050501
    [17] 王亚奇, 蒋国平. 复杂网络中考虑不完全免疫的病毒传播研究. 物理学报, 2010, 59(10): 6734-6743. doi: 10.7498/aps.59.6734
    [18] 王丹, 于灏, 井元伟, 姜囡, 张嗣瀛. 基于感知流量算法的复杂网络拥塞问题研究. 物理学报, 2009, 58(10): 6802-6808. doi: 10.7498/aps.58.6802
    [19] 李明杰, 吴晔, 刘维清, 肖井华. 手机短信息传播过程和短信息寿命研究. 物理学报, 2009, 58(8): 5251-5258. doi: 10.7498/aps.58.5251
    [20] 许 丹, 李 翔, 汪小帆. 复杂网络病毒传播的局域控制研究. 物理学报, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
计量
  • 文章访问数:  4992
  • PDF下载量:  629
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-12-08
  • 修回日期:  2015-06-10
  • 刊出日期:  2015-10-05

一种新的复杂网络影响力最大化发现方法

  • 1. 清华大学计算机系, 信息技术研究院, 清华信息科学与技术国家实验室, 北京 100084
  • 通信作者: 胡庆成, hqc10@mails.tsinghua.edu.cn
    基金项目: 国家重点基础研究发展(973计划) (批准号: 02011CB3023302)和国家高技术研究发展计划(863 计划) (批准号: SS2015AA020102)资助的课题.

摘要: 复杂网络中影响力最大化建模与分析是社会网络分析的关键问题之一, 其研究在理论和现实应用中都有重大的意义. 在给定s值的前提下, 如何寻找发现s个最大影响范围的节点集, 这是个组合优化问题, Kempe等已经证明该问题是NP-hard问题. 目前已有的随机算法时间复杂度低, 但是结果最差; 其他贪心算法时间复杂度很高, 不能适用于大型社会网络中, 并且这些典型贪心算法必须以了解网络的全局信息为前提, 而获取整个庞大复杂且不断发展变化的社会网络结构是很难以做到的. 我们提出了一种新的影响力最大化算法模型RMDN, 及改进的模型算法RMDN++, 模型只需要知道随机选择的节点以及其邻居节点信息, 从而巧妙地回避了其他典型贪心算法中必须事先掌握整个网络全局信息的问题, 算法的时间复杂度仅为O(s log(n)); 然后, 我们利用IC模型和LT模型在4种不同的真实复杂网络数据集的实验显示, RMDN, RMDN++算法有着和现有典型算法相近的影响力传播效果, 且有时还略优, 同时在运行时间上则有显著的提高; 我们从理论上推导证明了方法的可行性. 本文所提出的模型算法适用性更广, 可操作性更强, 为这项具有挑战性研究提供了新的思路和方法.

English Abstract

参考文献 (36)

目录

    /

    返回文章
    返回