概述
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
的增大而递减:
![](https://img.ultipa.cn/img/2023-03-14-11-41-37-submodular.jpg)
其中种子集合|Sk+1|>|Sk|,S∪{v}
表示将节点v
加入种子集合。
CELF算法正是利用了传播函数的次模性对传统的贪心算法进行了改进,省去了大量的重复计算从而算地更快,但结果仍接近最优。
惰性前向选择
CELF算法在初始时与贪心算法一样,要计算每个节点的影响力,然后根据影响力大小进行降序排列。由于此时种子集合为空,每个节点的影响力可以被视为各自的初始边际效益。
在第一轮迭代中,将列表最顶部的节点移至种子集合。
下一轮迭代中,只重新计算最顶部节点的边际效益。排序后,如果该节点仍位于最顶部,就可将其移至种子集合;如果不是,重新计算最顶部节点的边际效益并进行排序。
与贪心算法不同,在每轮迭代中,CELF不计算所有剩余节点的边际效益,这就是在利用传播函数的次模性——所有节点在本轮的边际效益只会比上一轮小。因此,如果计算的节点仍处于最顶部,就可以直接将其放入种子集合,无需计算其他节点。
当种子集合达到规定大小时,算法停止。
语法
- 命令:
algo(celf)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
seedSetSize | int | >0 | 1 |
是 | 种子节点的个数 |
monteCarloSimulations | int | >0 | 1000 |
是 | 蒙特卡罗模拟次数 |
propagationProbability | float | (0,1) | 0.1 |
是 | 本轮有激活能力的节点成功激活每个出边邻居的概率 |
示例
示例图如下:
![](https://img.ultipa.cn/draw/draw_b0e238a2cd6f47179fce311b9d6213a6.jpg?v='1680580762084')
文件回写
配置项 | 回写内容 | 描述 |
---|---|---|
filename | _id ,spread |
点及其加入种子集合时的边际效益 |
algo(celf).params({
seedSetSize: 3,
monteCarloSimulations: 1000,
propagationProbability: 0.5
}).write({
file:{
filename: 'seeds'
}
})
结果:文件seeds
I,4.687
D,1.261
X,1
直接返回
别名序号 | 类型 | 描述 |
列名 |
---|---|---|---|
0 | []perNode | 点及其加入种子集合时的边际效益 | _uuid , spread |
algo(celf).params({
seedSetSize: 2,
monteCarloSimulations: 1000,
propagationProbability: 0.6
}) as seeds
return seeds
结果:seeds
_uuid | spread |
---|---|
9 | 5.345 |
4 | 1.262 |
流式返回
别名序号 | 类型 | 描述 |
列名 |
---|---|---|---|
0 | []perNode | 点及其加入种子集合时的边际效益 | _uuid , spread |
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)
nodes._id | nodes.createdOn | seeds.spread |
---|---|---|
I | 2018-12-13 00:00:00 | 5.345 |
D | 2019-01-16 00:00:00 | 1.262 |
X | 2022-06-13 00:00:00 | 1 |