一种改进的社会网络影响力最大化算法

摘要

影响力最大化问题是如何在社会网络中选择k个种子节点，使得在特定传播模型下的影响范围达到最大。已有的经典算法虽然有较好的影响范围，但其时间复杂度过高，不适用于大型社交网络的影响力分析，也不能保证很好的影响效果。提出一种基于潜在影响力的集合覆盖贪心算法，每次计算所有未覆盖节点的未覆盖度数，选择未覆盖度数最大的节点作为下一个种子节点。如果未覆盖度数最大的节点数不止一个，则选择这些节点中潜在影响力最大的节点作为下一个种子节点。实验结果表明，改进的算法相对于已有算法在最终影响范围和时间复杂度上都有明显的提高。