李阅志，祝园园，钟　鸣

(1.软件工程国家重点实验室(武汉大学)，武汉 430072;　2.武汉大学 计算机学院，武汉 430072)(*通信作者电子邮箱yyzhu@whu.edu.cn)

0　引言

随着Facebook和微信微博等社交网络的流行，越来越多的用户喜欢在社交网络中分享自己的观点和其他信息，使得网络影响力传播的研究成为社交网络分析的热点[1]。 影响力最大化问题作为病毒式营销和广告投放等社交网络推荐研究领域的一个重要问题，引起了广泛的关注和研究热情。

影响最大化问题最早由Domingos等[2]定义为如何寻找t个初始节点，使得信息的最终传播范围最广。 Kempe等[3]将影响最大化定义为一个离散优化问题，证实了这个问题在独立级联模型下是NP难问题，提出了对后续研究影响极大的两种传播模型：独立级联(Independent Cascade，IC)模型和线性阈值(Linear Threshhold，LT)模型，并基于子模性质(sub-modularity)提出了一个基本的贪心算法Greedy。 为了降低Greedy算法的时间复杂度，后来的研究者又提出了若干改进算法，如CELF(Cost-Effective Lazy Forward)算法[4]、DegreeDiscount算法[5]、核覆盖算法(Core Covering Algorithm, CCA)[6]、PMIA(Prefix excluding Maximum Influence Arborescence)算法[7]、IRIE(Influence Rank Influence Estimation)算法[8]等。 其中PMIA算法和IRIE算法被认为是现有影响力最大化算法中影响范围和时间效率排名靠前的算法。这些算法基本都使用了子模性质，虽然时间效率有了很大的提升，但是影响范围效果仍然比不上Greedy算法[3]。

Kempe等[3]已经证明具有子模性的影响范围函数使用Greedy算法求解，能取得最优解的63%[9]。该结论表明当前取得最大影响范围的Greedy算法和最优解仍有差距。 为了缩小现有影响最大化算法和最优解的差距，本文提出一种采用k-核过滤的算法，可以应用于现有的大多数基于子模性质的影响最大化算法，扩大它们的影响范围，降低它们的时间复杂度。……