基于拓扑势的影响力最大化算法

作者：王秀芳; 牛炜南^*; 孙承爱; 仇丽青

来源：计算机工程与设计, 2020, 41(03): 735-741.

DOI：10.16208/j.issn1000-7024.2020.03.022

• 社交网络
• 影响力最大化
• 拓扑势
• CELF算法
• 加权度

针对影响力最大化问题中贪心算法时间效率低的局限性,提出基于拓扑势的影响力最大化算法。基于拓扑势理论,确定节点是"山峰""山谷"和"斜坡"节点;启发式地选取加权度最大的k个"山峰"和"山谷"节点构成候选种子集;采用CELF (cost-effective forward)算法确定最优种子集,提高影响范围。实验结果表明,基于拓扑势的算法在Amazon数据集上比贪心算法的运行时间快了98%,在时间复杂度方面比其它传统算法更具优势。

• 单位
  山东科技大学