一种兴趣驱动的跨网络传播优化算法

李 雷 邓诗琦 赵 博 施化吉 施磊磊

1(江苏大学计算机科学与通信工程学院 江苏 镇江 212013) 2(中国传媒大学新闻传播学部新闻学院 北京 100024)

0 引 言

社交网络的开放性、便利性及内容的丰富性吸引了广大的用户人群，同时也为在线推荐系统和病毒式营销提供了良好的平台。近年来，基于社交网络的精准广告投放已经成为首要选择。其中，影响力最大化问题以“口碑营销”为基础对用户影响规则及影响力传播模式进行研究，具有重大的理论意义和实用价值。

文献[1]给出了影响力最大化问题的相关研究进展。Domingos等[2]首先将影响力最大化问题引入社会网络领域，并给出了该问题的详细定义与评价指标。Kempe等[3]在此基础上将影响力最大化形式化定义为在特定影响力传播模型中挖掘影响力大的k个节点的离散优化问题，并证明了影响力最大化问题是一个NP-hard问题，且用贪心算法可以得到精确度为(1-1/e)的近似最优解，但其时间复杂度高、效率低下。针对此问题，一些研究者对影响力最大化问题的贪心算法作出了一系列改进[4-6]，也有研究者提出用启发式算法[7-10]解决该问题。除了提升算法的运行效率外，很多研究以提升问题模型的实用性为目标进行开展，如通过考虑主题感知这一因素以提升影响力传播模型的准确性[11-12]；将挖掘全局影响力最大的节点具体化为挖掘某一特定地理位置内影响力最大的节点[13-14]；将成本因素引入影响力最大化问题[15-16]等。

上述研究都是基于单网络对影响力最大化问题进行了较为充分的研究，然而随着用户的跨网络参与行为逐渐增多，各社交网络间的交集也随之增加，学者开始从跨网络的角度探究影响力最大化问题。……