基于局部概率解的免疫遗传影响力最大化算法

摘要

影响力最大化问题是在复杂社会网络中选择一小部分用户在特定传播模型下最大化影响扩散。基于贪心的蒙特卡洛模拟方法在理论上保证近乎最优的解决方案,但算法运行效率很低。虽然已经开发出许多没有理论保证的启发式方法,但都大大降低了解决方案的质量。为解决该问题,提出局部概率解策略计算节点集的影响力,其性能近似于蒙特卡洛模拟,并且提出基于免疫遗传的影响力最大化算法。在4个真实数据集上的实验表明所提算法在解决影响力最大化问题上的高效性。在影响力传播范围上,和当前表现最好的CELF算法有极其相近的性能,且运行效率比CELF算法快大约5个数量级。