CELF(Cost-Effective Lazy Forward selection)具有成本效益的惰性前向选择算法

CELF(Cost-Effective Lazy Forward selection)算法解析   

  引言：在社交网络影响力最大化问题的求解过程中，我们往往需要去选择一些目标种子结点作为信息初始传播的源头。贪婪算法在传播效果上的解决可以达到影响的最大化，但是在时间复杂度上面显得确十分糟糕。为此CELF算法应势而生，CELF算法利用了函数次模性的特点，在第一轮选择种子结点时，计算网络中所有节点的边际收益，但将在之后的过程中，不再做网络节点边际收益的重复计算，这相对于传统的贪婪算法，将在时间上得到非常明显的改善。本文是对论文《Cost-effective Outbreak Detection in Networks》的补充，如果你是看了这篇论文之后，依然不明白CELF算法，那么本文可能会给予你一点点启示。

一.函数的次模性（submodular)

  对于函数次模性的理解，举个例子，当我们在饿了的时候，吃一碗饭得到的满足感，是比饱腹的时候得到的更多，函数次模性数学解释如下：

图1 函数的次模性
  图中的 R ( ) R() R()函数，我们可以看作是一个收益函数，因为在原文中的解释相对稍微复杂，我就用另一个例子来说明。图1中的A和B看作是选好的种子集， R ( ) R() R()可以看作是A,B种子集在网络中影响到的非种子结点的数量！次模性的意思就是，当种子集A比B小的时候，新的种子结点S加入到种子集A和B中, R ( A ∪ R(A\cup R(A∪{s} ) − R ( A ) )-R(A) )−R(A)获得边际收益更大！

二.CELF 算法伪码解读

图2 CELF算法伪码
  CELF算法的说明：因为算法最主要的是“篮筐处”，我对“篮筐”里面的伪码，做出如下逐行解释：（如果你已经熟悉伪码可以不用看）

  第一行：输入网络结构 g ( V , E ) g(V,E) g(V,E)，网络结构 V V V是点的集合， E E E是边的集合；R是收益函数；c是成本函数；B是预算；type就是网络节点成本的类型，原文中有两种类型，UC统一成本（常数），CB非统一成本（会变化的）。

  第二行：最开始种子结点集A为空集；对于每一个V中的结点s,初始化它的边际收益 δ s \delta_{s} δs​为无穷大。

  第三行：循环条件为，当把种子结点S加入到种子集A中的时候，成本函数的值c小于等于预算B，然后可以继续循环。循环为后置循环，意思是先循环再判断是否满足循环条件。

  第四行：进入循环体内，对于每一个非种子结点s，我们给它打上flase标签。

  第五行：永久循环，除非第八行运行条件成立退出。

  第六、七行：根据种子结点的成本类型为UC或者CB并进行以边际收益 δ s \delta_{s} δs​为选则依据的结点选择（选择边际收益最大的）。

  第八行: 如果找出来的最大边际收益 δ s \delta_{s} δs​结点的标签为ture，则加入种子集A，并结束循环，进行下一轮选择。

  第九行：如果找出来的最大边际收益结点的标签为flase，则重新计算边际收益，并改标签为ture。

次模性在CELF中的体现解析   在第二轮选择种子结点的时候，并没有全部计算所有结点的边际收益（可能计算了部分）

  因为：

图3 论文截图处“蓝色框部分”给出了解释

  因为第一轮边际收益计算后，排序在顶端的点依然在顶端，只有可能当他们的边际收益很接近的时候，可能在第K（k>1）轮需要多计算几次。另外，如果结点之间的边际收益相隔大，那么之后的计算完全没必要感觉，直接依靠第一轮的边际收益排序来选择就好了！

  这就是相比于贪婪算法时间节省的地方，第一轮时间复杂度是一样的，后面的选择轮数就不需要再去遍历估计那些没有被选为种子结点的结点的边际收益，此处正是次模性的体现（领会）
   该解析如果还是看得不明白，可以参考另一位作者写的，虽然简陋，希望能一起结合论文看，能让你明白！
https://blog.csdn.net/s1102379635/article/details/8524447