作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2018, Vol. 44 ›› Issue (5): 188-193,200. doi: 10.19678/j.issn.1000-3428.0046702

• 人工智能及识别技术 • 上一篇    下一篇

基于合并影响概率的社交网络影响最大化算法

周飞,高茂庭   

  1. 上海海事大学 信息工程学院,上海 201306
  • 收稿日期:2017-04-10 出版日期:2018-05-15 发布日期:2018-05-15
  • 作者简介:周飞(1993—),男,硕士研究生,主研方向为数据挖掘、数据分析;高茂庭,教授、博士。
  • 基金资助:
    国家自然科学基金(61202022)。

Influence Maximization Algorithm for Social Network Based on Combined Impact Probability

ZHOU Fei,GAO Maoting   

  1. College of Information Engineering,Shanghai Maritime University,Shanghai 201306,China
  • Received:2017-04-10 Online:2018-05-15 Published:2018-05-15

摘要: 针对大型社交网络影响最大化算法时间复杂度较高,并且节点影响覆盖率较低的问题,提出一种新的影响力最大化算法。采用PageRank算法选择影响力较高的节点作为备用种子,通过统计备用种子对潜在可激活节点的激活轮次和激活次数来计算其合并影响概率,并采用遗传算法从中选择合并影响概率最大的k个结果作为种子节点。仿真结果表明,与DegreeDiscount、PageRank等算法相比,该算法能获得较好的节点选取效果。

关键词: 社交网络, 影响最大化, 合并影响概率, 遗传算法, 独立级联模型

Abstract: In order to solve the problem of high time complexity and low impact coverage of nodes in influence maximization algorithm,a new influence maximization algorithm is proposed.The PageRank algorithm is used to select the nodes with higher influence as the standby seeds.Then,the combined impact probability of the standby nodes is calculated by counting the number of active rotations and activations of the nodes which can be activated,and k nodes with the largest probability of the combined impact are selected as the seed nodes by the Genetic Algorithm(GA).Simulation results show that compared with DegreeDiscount,PageRank and other algorithms,the algorithm can obtain better nodes selection effect.

Key words: social network, influence maximization, combined impact probability, Genetic Algorithm(GA), Independent Cascade Model(ICM)

中图分类号: