计算机应用 ›› 2020, Vol. 40 ›› Issue (1): 96-102.DOI: 10.11772/j.issn.1001-9081.2019061066

• 数据科学与技术 • 上一篇    下一篇

基于反向PageRank的影响力最大化算法

张宪立, 唐建新, 曹来成   

  1. 兰州理工大学 计算机与通信学院, 兰州 730050
  • 收稿日期:2019-06-24 修回日期:2019-09-02 出版日期:2020-01-10 发布日期:2019-09-29
  • 通讯作者: 张宪立
  • 作者简介:张宪立(1979-),男,甘肃陇南人,讲师,主要研究方向:社会网络分析、影响力最大化;唐建新(1985-),男,河南商丘人,讲师,博士,主要研究方向:传播动力学、智能计算;曹来成(1965-),男,甘肃平凉人,教授,博士,主要研究方向:网络空间安全、大数据智能分析与安全。
  • 基金资助:
    国家自然科学基金资助项目(61562059)。

Influence maximization algorithm based on reverse PageRank

ZHANG Xianli, TANG Jianxin, CAO Laicheng   

  1. School of Computer and Communication, Lanzhou University of Technology, Lanzhou Gansu 730050, China
  • Received:2019-06-24 Revised:2019-09-02 Online:2020-01-10 Published:2019-09-29
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61562059).

摘要: 针对社会网络上的影响力最大化算法在大规模网络上难以同时满足传播范围、时间效率和空间效率要求的问题,提出一种混合PageRank和度中心性的启发式算法(MPRD)。首先,基于PageRank,引入一种反向PageRank思想来评估节点影响力;然后,结合局部指标度中心性,设计一种混合的指标来评估节点的最终影响力;最后,通过相似性方法去掉影响力重合严重的节点,选出种子节点集。在6个数据集和两种传播模型上进行实验,实验结果表明,所提的MPRD在传播范围上优于现有的启发式算法,在时间效率上比贪心算法快四、五个数量级,在空间效率上优于基于反向抽样的IMM算法。所提的MPRD在处理大规模网络上的影响力最大化问题时能够取得传播范围、时间效率和空间效率的平衡。

关键词: 影响力最大化, PageRank, 度中心性, 启发式算法, 贪心算法

Abstract: Concerning the problem that the existing influence maximization algorithms on social networks are difficult to meet the requirements of propagation range, time cost and memory usage on large scale networks simultaneously, a heuristic algorithm of Mixed PageRank and Degree (MPRD) was proposed. Firstly, the idea of reverse PageRank was introduced for evaluating the influence of nodes based on PageRank. Secondly, a mixed index based on reverse PageRank and degree centrality was designed for evaluating final influence of nodes. Finally, the seed node set was selected by using the similarity method to filter out the node with serious overlapping influence. The experiments were conducted on six datasets and two propagation models. The experimental results show that the proposed MPRD is superior to the existing heuristic algorithms in term of propagation range, and is four or five orders of magnitude faster than greedy algorithm, and needs lower memory compared to Influence Maximization based on Martingale (IMM) algorithm based on reverse sampling. The proposed MPRD can achieve the balance of propagation range, time cost and memory usage in solving the problem of influence maximization on large scale networks.

Key words: influence maximization, PageRank, degree centrality, heuristic algorithm, greedy algorithm

中图分类号: