概述

CELF（Cost Effective Lazy Forward，具有成本效益的惰性前向选择）算法可以在一个有传播（污染物、信息、病毒等）行为的网络中选取一些种子节点作为传播源头，以达到影响力最大化（Influence Maximization, IM）的效果。

CELF算法由Jure Leskovec等人于2007年提出，它改进了传统基于IC模型的贪心（Greedy）算法，利用函数次模性，只在初始时计算所有节点的影响力，之后不再重复计算所有节点的影响力，因此具有更高的成本效益。

算法的相关资料如下：

• J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, N. Glance, Cost-effective Outbreak Detection in Networks (2007)
• D. Kempe, J. Kleinberg, E. Tardos, Maximizing the Spread of Influence through a Social Network (2003)

CELF算法的一个典型应用场景是预防流行病爆发，通过选择一小组人进行监测，从而达到在疾病爆发的早期就能发现的效果。

基本概念

传播函数—IC模型

本算法采用独立级联（Independent Cascade, IC）模型来模拟网络中的影响传播过程。IC模型是一种概率型传播模型，它从一批初始被激活的种子节点集合开始，在第k轮：

• 只有在第k-1轮被激活的节点在第k轮具备激活能力，它们以一定的概率各自尝试激活每个尚未被激活的出边邻居节点。
• 当图中剩余具备激活能力的节点数为0时，传播过程结束。

传播结束时，图中被激活的节点总数就可以衡量种子集合的影响力。为了排除模拟结果的随机性，我们模拟大量次数，然后对所有结果取平均值，这种方法称为蒙特卡罗模拟（Monte-Carlo Simulation）。

次模性

传播函数IC()具有次模性（Submodular，又称子模性），这是指对于一个节点v，它的边际效益（Marginal Gain）随着种子集合S的增大而递减：

其中种子集合|S_k+1|>|S_k|，S∪{v}表示将节点v加入种子集合。

CELF算法正是利用了传播函数的次模性对传统的贪心算法进行了改进，省去了大量的重复计算从而算地更快，但结果仍接近最优。

惰性前向选择

CELF算法在初始时与贪心算法一样，要计算每个节点的影响力，然后根据影响力大小进行降序排列。由于此时种子集合为空，每个节点的影响力可以被视为各自的初始边际效益。

在第一轮迭代中，将列表最顶部的节点移至种子集合。

下一轮迭代中，只重新计算最顶部节点的边际效益。排序后，如果该节点仍位于最顶部，就可将其移至种子集合；如果不是，重新计算最顶部节点的边际效益并进行排序。

与贪心算法不同，在每轮迭代中，CELF不计算所有剩余节点的边际效益，这就是在利用传播函数的次模性——所有节点在本轮的边际效益只会比上一轮小。因此，如果计算的节点仍处于最顶部，就可以直接将其放入种子集合，无需计算其他节点。

当种子集合达到规定大小时，算法停止。

语法

• 命令：algo(celf)
• 参数：

示例

示例图如下：

文件回写

algo(celf).params({
  seedSetSize: 3,
  monteCarloSimulations: 1000,
  propagationProbability: 0.5 
}).write({
  file:{
    filename: 'seeds'
  }
})

结果：文件seeds

I,4.687
D,1.261
X,1

直接返回

algo(celf).params({
  seedSetSize: 2,
  monteCarloSimulations: 1000,
  propagationProbability: 0.6 
}) as seeds
return seeds

结果：seeds

流式返回

algo(celf).params({
  seedSetSize: 3,
  monteCarloSimulations: 1000,
  propagationProbability: 0.6 
}).stream() as seeds
find().nodes({_uuid == seeds._uuid}) as nodes
return table(nodes._id, nodes.createdOn, seeds.spread)

结果：table(nodes._id, nodes.createdOn, seeds.spread)