电子学报 ›› 2019, Vol. 47 ›› Issue (1): 161-168.DOI: 10.3969/j.issn.0372-2112.2019.01.021

• 学术论文 • 上一篇    下一篇

基于树核度的社交网络影响最大化问题

朱恩强1,2, 吴艳蕾2, 许宇光2, 牛云云2   

  1. 1. 广州大学计算科技研究院, 广东广州 510006;
    2. 北京大学信息科学技术学院, 北京 100871
  • 收稿日期:2015-04-22 修回日期:2016-07-17 出版日期:2019-01-25
    • 作者简介:
    • 朱恩强 男,1983年6月出生,辽宁人.2015年获北京大学信息科学技术学院理学博士学位,现为北京大学信息学院博士后,主要从事图论与组合优化、社交网络信息传播及安全、DNA序列编码理论的研究.E-mail:zhuenqiang@pku.edu.cn
    • 基金资助:
    • 国家973重点基础研究发展计划 (No.2013CB329600,No.2013CB329602,No.2013CB329606); 国家自然科学基金 (No.61572046,No.61572492,No.61472433)

Tree-Coritivity-Based Influence Maximization in Social Networks

ZHU En-qiang1,2, WU Yan-lei2, XU Yu-guang2, NIU Yun-yun2   

  1. 1. Institute of Computing Science and Technology, Guangzhou University, Guangzhou, Guangdong 510006, China;
    2. School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
  • Received:2015-04-22 Revised:2016-07-17 Online:2019-01-25 Published:2019-01-25
    • Supported by:
    • National Program on Key Basic Research Project of China  (973 Program) (No.2013CB329600, No.2013CB329602, No.2013CB329606); National Natural Science Foundation of China (No.61572046, No.61572492, No.61472433)

摘要: 社交网络中的影响最大化问题是指对于给定的k值,寻找k个在特定传播模型下能够使得传播范围达到最大的节点.此问题在常用的几种传播模型中都是NP-难的.目前虽然已经有很多近似求解的算法,但如何在较低的算法时间复杂度下,保证较大的传播范围仍然是求解该问题的一个挑战.为此,本文提出了一种新颖的基于图的树核度理论的方法来求解社交网络影响最大化问题,并相应地给出了一个多项式时间的算法.所提算法综合考虑了网络的结构特征和传播特征.另外,我们将该算法与传统的随机、度以及贪心算法进行了比较.实验结果表明,所提算法可以较快地找到能够使得传播范围较大的节点集合.

关键词: 树核度, 树核, 社会网络, 算法, 影响最大化, 传播模型

Abstract: Influence maximization problem in social networks deals with finding a small subset of nodes,which could maximize the spread of influence.It has been proved that this problem is NP-hard under the commonly used diffusion models.Although many algorithms have been proposed to solve this problem approximately,it is still a challenge to guarantee the spread of influence within a low time complexity.For this,we propose a novel method based on tree-coritivity theory and give a polynomial-time algorithm,for finding the initial active nodes required in the influence maximization problem.Our algorithm considers both the structure and the propagation characteristics of a network. Moreover,by experiment,we compare this algorithm with other conventional node-selection methods such as Random,Degree and Greedy.The results demonstrate that the proposed algorithm can find the node set that can widely spread the information efficiently.

Key words: tree-coritivity, tree-core, social network, algorithm, influence maximization, diffusion models

中图分类号: