Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (3): 834-838.DOI: 10.11772/j.issn.1001-9081.2018081695

Previous Articles     Next Articles

Influence maximization algorithm on internal decay based on community structure in social network

SUN Zili, PENG Jian, TONG Bo   

  1. College of Computer Science, Sichuan University, Chengdu Sichuan 610065, China
  • Received:2018-08-15 Revised:2018-08-30 Online:2019-03-10 Published:2019-03-11

社会网络中基于社群衰减的影响力最大化算法

孙子力, 彭舰, 仝博   

  1. 四川大学 计算机学院, 成都 610065
  • 通讯作者: 彭舰
  • 作者简介:孙子力(1991-),男,山东烟台人,硕士研究生,主要研究方向:大数据与云计算;彭舰(1970-),男,四川成都人,教授,博士,CCF高级会员,主要研究方向:大数据与云计算、无线传感器网络、移动计算;仝博(1989-),男,天津人,博士研究生,主要研究方向:大数据与云计算。

Abstract:

The existing network spread model ignores the information attenuation in the process of information spread, and the traditional influence maximization algorithm cannot effectively use the community structure to improve the influence spread range. To solve these problems, an algorithm of Influence Maximization on Internal Decay (IMID) based on community structure was proposed. Firstly, the community structure of a whole social network was divided and the influence range of nodes in the community was evaluated. Then, with spread probability of association points between the communities considered, the attenuation degree of information spread between nodes was calculated. Experimental and analysis results show that the proposed algorithm not only reduces the time complexity, but also obtains the influence transmission range near that of greedy algorithm, with influence coverage over 90%. Therefore, with several nodes selected as the initial nodes between the core seed node set and connected communities, information will be widely spread in the network at the minimum cost.

Key words: information spread, influence maximization, social network, community division

摘要:

针对现有网络传播模型忽略了信息传播过程中的信息衰减,传统影响力最大化算法无法有效利用社群结构提高影响力传播范围的问题,提出一种基于社群结构的影响力最大化算法——社群衰减的影响力最大化(IMID)算法。首先对整个社会网络进行社群结构划分,评估社群中节点影响力范围,并考虑社群之间关联点之间的关联概率,在信息传播过程中增加节点之间信息传播衰减度计算。通过实验与分析,该算法不仅降低了时间复杂度,还获得了接近贪心算法的影响力传播范围,影响覆盖率达到90%以上。因此,在核心种子节点集和连接社群之间纽带节点选取若干节点作为初始节点,会让信息以最小的代价在网络中获得广泛传播。

关键词: 信息传播, 影响力最大化, 社会网络, 社群划分

CLC Number: