计算机应用

作者：张宪立, 唐建新, 曹来成

单位：兰州理工大学 计算机与通信学院, 兰州 730050

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

基金：国家自然科学基金资助项目（61562059）。

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

来源：2020年第1期

《计算机应用》期刊编辑部

查看计算机应用杂志2020年第1期