基于友好度的影响力最大化算法

吴 旭，胡一清

(西安邮电大学 计算机学院, 陕西 西安 710121)



基于友好度的影响力最大化算法

吴 旭，胡一清

(西安邮电大学 计算机学院, 陕西 西安 710121)

提出一种基于友好度的影响力最大化算法。利用社交网络中用户行为信息计算友好度并构建友好关系网络，通过友好度调整节点的扩散概率，同时启发式地选取友好度积累值较高的节点作为启发节点以此提升算法的实现效率，最后采用CELF++算法计算影响力最大的节点集。实验结果表明，该算法与CELF++算法、TIM算法和DegreeDiscount算法相比，在获得较好的扩散效果的同时亦将执行时间有效的控制在一定范围内。

影响力最大化；友好关系；社交网络；社会计算

社会网络中的影响力最大化算法[1, 2]可以帮助发现现实生活中不易发现的社会现象或者社会问题。其目的是寻找若干个种子节点使影响力扩散最大化，得到影响力最大化的最优解决方案。

利用自然贪心算法计算影响力最大化的效果虽然明显好于基于节点度或中心性的启发式的影响力最大化算法，但其计算效率不高，特别是面对拥有海量用户节点和边社交网站，低效问题更加明显[3]。CELF(Cost-Effective Lazy Forward selection)算法[4]在自然贪心算法的基础上，利用影响力最大化的子模块特性提升了贪心算法的效率；CELF++算法[5]是对CELF算法的改进，利用堆特性进一步提升了算法效率。 NewGreedy算法[6]和CELF算法[4]融合得到的MixedGreedy算法，计算效率也有所提高，但是计算得出的种子节点个数与最佳的影响力最大化的节点集仍有差距；……