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

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

Greedy Strategy Influence Maximization Algorithm Based on Seed Candidates

The hill-climbing greedy algorithm is not easily extended to large-scale social networks due to its high time complexity.In this paper,it is theoretically analyzed that the node set influence evaluation can be transformed into local probability solution,and thus the algorithm efficiency is significantly improved.The local probability solution function is extend to the greedy algorithm.Based on seed candidates,the greedy influence maximization algorithm and the lazy forward influence maximization algorithm are proposed,respectively. Experiments on four real datasets show that the performance of the proposed algorithms is as high as that of cost-effective lazy forward selection,and the proposed algorithms are superior in running time.