概述

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不计算所有剩余节点的边际效益，这就是在利用传播函数的次模性——所有节点在本轮的边际效益只会比上一轮小。因此，如果计算的节点仍处于最顶部，就可以直接将其放入种子集合，无需计算其他节点。

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

示例图集

创建示例图集：

// 在空图集中逐行运行以下语句
create().node_schema("account").edge_schema("follow")
create().node_property(@account, "createdOn", datetime)
insert().into(@account).nodes([{_id:"A", createdOn: "2016-12-3"}, {_id:"B", createdOn:"2022-1-30" }, {_id:"C", createdOn: "2019-11-8"}, {_id:"D", createdOn: "2019-1-16"}, {_id:"E", createdOn: "2016-3-4"}, {_id:"F", createdOn: "2019-11-10"}, {_id:"G", createdOn: "2019-7-26"}, {_id:"H", createdOn: "2016-7-11"}, {_id:"I", createdOn: "2018-12-13"},{_id:"J", createdOn: "2018-3-21"}])
insert().into(@follow).edges([{_from:"A", _to:"B"}, {_from:"A", _to:"G"}, {_from:"B", _to:"F"}, {_from:"C", _to:"J"}, {_from:"D", _to:"J"}, {_from:"E", _to:"A"}, {_from:"F", _to:"C"}, {_from:"F", _to:"G"}, {_from:"G", _to:"H"}, {_from:"H", _to:"C"}, {_from:"H", _to:"E"}, {_from:"H", _to:"J"}, {_from:"I", _to:"B"}, {_from:"C", _to:"B"}])

创建HDC图集

将当前图集全部加载到HDC服务器hdc-server-1上，并命名为 hdc_celf：

CALL hdc.graph.create("hdc-server-1", "hdc_celf", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_celf", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

参数

算法名：celf

文件回写

CALL algo.celf.write("hdc_celf", {
  params: {
    return_id_uuid: "id",
    seedSetSize: 3,
    monteCarloSimulations: 1000,
    propagationProbability: 0.5
  },
  return_params: {
    file: {
      filename: "seeds"
    }
  }
})

algo(celf).params({
  projection: "hdc_celf",
  return_id_uuid: "id",
  seedSetSize: 3,
  monteCarloSimulations: 1000,
  propagationProbability: 0.5
}).write({
  file: {
    filename: "seeds"
  }
})

结果：

_id,spread
H,3.612
I,1.673
A,1.353

完整返回

CALL algo.celf("hdc_celf", {
  params: {
    return_id_uuid: "id",    
    seedSetSize: 2,
    monteCarloSimulations: 1000,
    propagationProbability: 0.6
  },
  return_params: {}
}) YIELD seeds
RETURN seeds

exec{
  algo(celf).params({
    return_id_uuid: "id",    
    seedSetSize: 2,
    monteCarloSimulations: 1000,
    propagationProbability: 0.6
  }) as seeds
  return seeds
} on hdc_celf

结果：

流式返回

CALL algo.celf("hdc_celf", {
  params: {
    return_id_uuid: "id",
    seedSetSize: 3,
    monteCarloSimulations: 1000,
    propagationProbability: 0.6
  },
  return_params: {
  	stream: {}
  }
}) YIELD seeds
MATCH (nodes WHERE nodes._id = seeds._id)
RETURN nodes._id, nodes.createdOn, seeds.spread

exec{
  algo(celf).params({
    return_id_uuid: "id",
    seedSetSize: 3,
    monteCarloSimulations: 1000,
    propagationProbability: 0.6 
  }).stream() as seeds
  find().nodes({_id == seeds._id}) as nodes
  return nodes._id, nodes.createdOn, seeds.spread
} on hdc_celf

结果：