基于上界的影响力计算方法

基于上界的影响力计算方法是指通过对种子节点集的影响范围上界进行估计，结合影响范围的子模特性，实现网络中最有影响力的种子节点集的快速发现功能 。1

研究背景影响最大化问题源自病毒营销，它通过选择若干个高影响力用户，利用口碑效应实现营销效果最大化。影响最大化问题可定义为一个离散优化问题：给定随机传播模型，从社交网络G=(V,E)中，寻找k个节点作为传播级联的初始活跃节点，使得最终的影响力传播范围最大化，其中V是社交网络中用户的集合，E是用户之间的关系集合，边上的权重值反映了用户间的影响力大小。这里常用的随机传播模型为独立级联模型（IC模型）和线性阈值模型（LT模型）。

影响最大化问题在IC模型和LT模型上都是NP难问题，但影响范围函数具有单调特性和子模特性。一个集合函数是单调的，如果对所有的都成立。称一个集合函数具有子模特性，如果对任意的以及都有成立，即的边际效益是递减的。

基于上述两个特性，Kempe等人2提出了面向影响最大化问题的贪婪算法（Greedy算法），该算法依次从候选节点中选择边际效益最大的节点加入到种子节点集合中，直到选满k个点为止。贪婪算法使用蒙特卡洛模拟（MC模拟）来估计用户集合的影响范围。贪婪算法需要次迭代才能获得最终结果，其中k为种子节点集的大小，N为整个网络的大小，当N较大时，算法效率并不理想。

为解决这个问题，Leskovec等人利用影响范围函数的子模特性，提出一种CEFL算法，可以大幅削减MC模拟的调用次数，使执行效率为Greedy算法的700倍。在此基础上，Goyal等人提出了CELF算法的扩展版本——CELF++算法，该算法能将CELF算法的执行效率进一步提高35%-55%。

虽然CELF算法（包括CELF++算法）能有效提高影响最大化问题的求解效率，但它们在大规模网络上的执行效率仍然不理想。特别是在初始阶段，CELF算法需要对社交网络中每个节点的影响力边际效益建立初始上界，需要执行N次MC模拟，当N取值较大时，算法执行会非常慢。

基于影响范围上界的影响最大化方法为克服上述问题，基于影响范围上界的影响最大化方法旨在建立每个节点的影响范围初始理论上界，弥补Greedy算法在先验信息方面的缺失，来进一步减少Greedy算法中MC模拟的调用次数，实现大规模网络上影响最大化问题的高效求解。UBLF算法的主要步骤如下：

1. 将带有传播概率的扩散网络信息转换成传播概率矩阵PP，这里PP是一个N×N的方阵；

2. 以PP为处理对象，利用上界计算理论公式（详见文献1），计算每个节点作为初始扩散点的传播范围上界；这里可利用迭代法处理大规模矩阵的求逆运算，这样的一个优点在于它能同时求得所有节点的影响范围上界；

3. 依次选取上界较大的节点进行蒙特卡洛模拟，用真实值进行序列对比；若某节点v的真实值比其它点的上界值还要大，那么节点就入选整个网络的关键节点集，如此直到选满k个节点为止。

实验结果表明基于上界的影响力计算方法可大幅削减MC模拟的调用次数，在保证影响最大化问题求解精度不变的前提下，将其求解效率在CELF算法的基础上进一步提高2到10倍，且该算法对扩散模型的参数变化表现出较强的稳健性（实验结果详见文献1）。

本词条内容贡献者为:

吴晨涛 - 副研究员 - 上海交通大学