基于社交网络的影响力最大化算法

影响力最大化问题研究在给定传播模型下如何选取社交网络中的一组种子用户，使信息通过这些用户实现最大范围的传播。现有算法主要存在2个问题：一是由于影响范围有限、时间复杂度高，难以适用于大规模社交网络；二是仅局限于特定传播模型，只能解决单一类型社交网络下的影响力最大化问题，当使用在不同类型社交网络上时效果较差。对此，基于2个经典影响力传播模型，结合反向影响采样技术，提出一种高效的影响力最大化（MTIM）算法。为验证MTIM算法的高效性，将其与IMM、TIM和PMC等贪心算法，以及One Hop和DegreeDiscount等启发式算法在4个真实社交网络上进行对比实验，结果表明MTIM算法能够提供■近似保证，显著扩大影响范围，并有效提高运行效率。