曹玖新　 闵绘宇　 徐　顺 　刘　波

(东南大学计算机科学与工程学院,南京211189)(东南大学软件学院,苏州215123)



基于启发式和贪心策略的社交网络影响最大化算法

曹玖新 闵绘宇 徐顺 刘波

(东南大学计算机科学与工程学院,南京211189)(东南大学软件学院,苏州215123)

为解决传统影响力最大化算法在影响范围和运行时间上存在的不平衡问题,提出了一种综合启发式和贪心算法的社交网络影响力最大化算法(MHG)．该算法综合考虑了贪心算法和启发式算法的优势,将种子节点的选择分为2个阶段,即通过启发式算法选出候选种子节点集和使用贪心算法从候选种子节点集中筛选出种子节点集合．结果表明,与现有的启发式算法相比,MHG算法在影响范围上具有显著优势,且接近贪心算法,但其运行时间明显少于贪心算法,因而在效果和时间2个方面取得了较好的平衡．在真实数据集及不同传播模型下,MHG算法均表现出稳定的影响范围,体现了该算法在大规模社会网络处理中的可扩展性．

社交网络;影响最大化;贪心算法;启发式算法;传播模型

随着互联网技术的迅速发展,社交网络已成为人们交流沟通的重要平台,并在个体信息传播、思想交互等方面发挥着重要作用．朋友或其他信任源的推荐会使用户获得更高的满意度．文献[1]采用个体间的相互关系解决影响力最大化问题．该问题的关键是如何在大规模社交网络中挖掘出一个规模较小的种子节点集……