基于种子候选的贪心策略影响力最大化算法

作者：李美玲; 钱付兰^*; 徐涛; 赵姝; 张燕平

来源：模式识别与人工智能, 2020, 33(11): 1033-1042.

DOI：10.16451/j.cnki.issn1003-6059.202011008

• 社会网络
• 贪心算法
• 蒙特卡洛模拟
• 影响力最大化
• 局部概率解

爬山贪心算法的时间复杂度较高,不易扩展至大规模社会网络.为了解决此问题,文中从理论上分析节点集影响力评估可转化为局部概率解计算,能够提高算法运行效率.将局部概率解函数拓展到贪心算法中,提出基于种子候选的贪心影响力最大化算法和基于种子候选的偷懒贪心影响力最大化算法.在4个真实数据集上实验表明,文中算法与具有成本效益的惰性前向选择算法(CELF)性能一致,但在运行时间上快于CELF.

• 单位
  安徽大学