CELF

术语表

有向: 有向特征。该算法在有向图上定义良好。
有向: 有向特征。该算法忽略图的方向。
有向: 有向特征。该算法不能在有向图上运行。
无向: 无向特征。该算法在无向图上定义良好。
无向: 无向特征。该算法忽略图的无向性。
异构节点: 异构节点完全支持。该算法有能力区分不同类型的节点。
异构节点: 异构节点允许。该算法平等对待所有选定的节点，无论其标签如何。
异构关系: 异构关系完全支持。该算法有能力区分不同类型的关系。
异构关系: 异构关系允许。该算法平等对待所有选定的关系，无论其类型如何。
加权关系: 加权特征。该算法支持将关系属性用作权重，通过 relationshipWeightProperty 配置参数指定。
加权关系: 加权特征。该算法将每个关系视为同等重要，忽略任何关系权重值。
节点属性: 节点属性特征。该算法使用节点属性。

简介

影响力最大化问题旨在寻找一组 k 个节点，以使网络中预期的影响力传播最大化。这组初始的 k 个节点被称为 种子集 (seed set)。

Neo4j GDS 库支持在独立级联 (Independent Cascade) 传播模型下，对最优种子集进行近似计算。在此传播模型中，我们最初假设种子集中的节点受到影响，其过程如下：一个受影响的节点以概率 p 影响其每个邻居。传播范围即为最终受影响的节点总数。

Neo4j GDS 库支持 CELF 算法，该算法由 Leskovec 等人在 2007 年的《网络中具有成本效益的爆发检测》(Cost-effective Outbreak Detection in Networks) 一文中提出，用于计算具有较大预期传播范围的种子集。

CELF 算法基于该问题的贪心 (Greedy) 算法。它通过 k 个步骤迭代构建返回的种子集 S，在每一步中，将能带来最大预期传播增益的节点添加到 S 中。

对于不在 S 中的节点 u，其预期传播增益通过运行 mc 次不同的蒙特卡洛 (Monte Carlo) 传播过程模拟来进行估计，并计算在每次模拟中，若将 u 添加到 S 中，会有多少节点受到影响。

CELF 算法在贪心算法的基础上引入了 惰性转发 (lazy forwarding) 机制，该机制剔除了大量无需检查的节点，从而大幅减少了所需的模拟次数。这使得 CELF 在大型网络上比贪心算法快得多。

语法

不同模式下的 CELF 语法

在命名图上以流模式 (stream mode) 运行 CELF。

CALL gds.influenceMaximization.celf.stream(
  graphName: String,
  configuration: Map
)
YIELD
  nodeId: Integer,
  spread: Float

表 1. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 2. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
seedSetSize (种子集大小)	整数	`不适用`	否	在网络中使预期传播最大化的节点数量。
monteCarloSimulations (蒙特卡洛模拟次数)	整数	`100`	是	蒙特卡洛模拟的次数。
propagationProbability (传播概率)	浮点数	`0.1`	是	节点被其活跃邻居节点激活的概率。
randomSeed	整数	`不适用`	是	用于控制算法随机性的种子值。
1. 在 GDS 会话中，默认值为可用处理器的数量。

表 3. 结果
名称	类型	描述
nodeId	整数	节点 ID。
spread (传播范围)	浮点数	选择该节点所带来的传播增益。

在命名图上以统计模式 (stats mode) 运行 CELF。

CALL gds.influenceMaximization.celf.stats(
  graphName: String,
  configuration: Map
)
YIELD
  computeMillis: Integer,
  totalSpread: Float,
  nodeCount: Integer,
  configuration: Map

表 4. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 5. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[2]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
seedSetSize (种子集大小)	整数	`不适用`	否	在网络中使预期传播最大化的节点数量。
monteCarloSimulations (蒙特卡洛模拟次数)	整数	`100`	是	蒙特卡洛模拟的次数。
propagationProbability (传播概率)	浮点数	`0.1`	是	节点被其活跃邻居节点激活的概率。
randomSeed	整数	`不适用`	是	用于控制算法随机性的种子值。
2. 在 GDS 会话中，默认值为可用处理器的数量。

表 6. 结果
名称	类型	描述
computeMillis	整数	运行算法的毫秒数。
totalSpread (总传播范围)	浮点数	种子集中各节点传播范围的总和。
nodeCount	整数	图中的节点数。
配置	Map	用于运行算法的配置。

在命名图上以变异模式 (mutate mode) 运行 CELF。

CALL gds.influenceMaximization.celf.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  mutateMillis: Integer,
  nodePropertiesWritten: Integer,
  computeMillis: Integer,
  totalSpread: Float,
  nodeCount: Integer,
  configuration: Map

表 7. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 8. 配置
名称	类型	默认	可选	描述
mutateProperty	字符串	`不适用`	否	GDS 图中写入传播范围的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
seedSetSize (种子集大小)	整数	`不适用`	否	在网络中使预期传播最大化的节点数量。
monteCarloSimulations (蒙特卡洛模拟次数)	整数	`100`	是	蒙特卡洛模拟的次数。
propagationProbability (传播概率)	浮点数	`0.1`	是	节点被其活跃邻居节点激活的概率。
randomSeed	整数	`不适用`	是	用于控制算法随机性的种子值。

表 9. 结果
名称	类型	描述
mutateMillis	整数	向投影图添加属性的毫秒数。
nodePropertiesWritten	整数	添加到投影图中的属性数量。
computeMillis	整数	运行算法的毫秒数。
totalSpread (总传播范围)	浮点数	种子集中各节点传播范围的总和。
nodeCount	整数	图中的节点数。
配置	Map	用于运行算法的配置。

在命名图上以写入模式 (write mode) 运行 CELF。

CALL gds.influenceMaximization.celf.write(
  graphName: String,
  configuration: Map
)
YIELD
  writeMillis: Integer,
  nodePropertiesWritten: Integer,
  computeMillis: Integer,
  totalSpread: Float,
  nodeCount: Integer,
  configuration: Map

表 10. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 11. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[3]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeProperty	字符串	`不适用`	否	Neo4j 数据库中写入传播范围的节点属性。
seedSetSize (种子集大小)	整数	`不适用`	否	在网络中使预期传播最大化的节点数量。
monteCarloSimulations (蒙特卡洛模拟次数)	整数	`100`	是	蒙特卡洛模拟的次数。
propagationProbability (传播概率)	浮点数	`0.1`	是	节点被其活跃邻居节点激活的概率。
randomSeed	整数	`不适用`	是	用于控制算法随机性的种子值。
3. 在 GDS 会话中，默认值为可用处理器的数量。

表 12. 结果
名称	类型	描述
writeMillis	整数	向投影图添加属性的毫秒数。
nodePropertiesWritten	整数	添加到 Neo4j 数据库的属性数量。
computeMillis	整数	运行算法的毫秒数。
totalSpread (总传播范围)	浮点数	种子集中各节点传播范围的总和。
nodeCount	整数	图中的节点数。
配置	Map	用于运行算法的配置。

示例

以下所有示例应在空数据库中运行。

这些示例将 Cypher 投影作为规范。原生投影将在未来版本中弃用。

在本节中，我们将展示在具体图上运行 CELF 算法的示例。旨在说明结果的样子，并为如何在实际环境中使用该算法提供指导。我们将使用一个小型的社交网络图，其中少数节点按特定模式连接。示例图如下所示：

以下 Cypher 语句将在 Neo4j 数据库中创建示例图：

CREATE
  (a:Person {name: 'Jimmy'}),
  (b:Person {name: 'Jack'}),
  (c:Person {name: 'Alice'}),
  (d:Person {name: 'Ceri'}),
  (e:Person {name: 'Mohammed'}),
  (f:Person {name: 'Michael'}),
  (g:Person {name: 'Ethan'}),
  (h:Person {name: 'Lara'}),
  (i:Person {name: 'Amir'}),
  (j:Person {name: 'Willie'}),

  (b)-[:FRIEND_OF]->(c),
  (c)-[:FRIEND_OF]->(a),
  (c)-[:FRIEND_OF]->(g),
  (c)-[:FRIEND_OF]->(h),
  (c)-[:FRIEND_OF]->(i),
  (c)-[:FRIEND_OF]->(j),
  (d)-[:FRIEND_OF]->(g),
  (f)-[:FRIEND_OF]->(e),
  (f)-[:FRIEND_OF]->(g),
  (g)-[:FRIEND_OF]->(a),
  (g)-[:FRIEND_OF]->(b),
  (g)-[:FRIEND_OF]->(h),
  (g)-[:FRIEND_OF]->(e),
  (h)-[:FRIEND_OF]->(i);

以下语句将投影图并将其存储在图目录中。

MATCH (source:Person)
OPTIONAL MATCH (source)-[r:FRIEND_OF]->(target:Person)
RETURN gds.graph.project(
  'myGraph',
  source,
  target
)

在接下来的示例中，我们将演示如何在图上使用 CELF 算法。

内存估算

首先，我们将使用 estimate 过程估算运行算法的成本。这可以在任何执行模式下完成。在这个例子中我们将使用 write 模式。估算算法有助于了解在您的图上运行该算法将产生的内存影响。当您随后在其中一种执行模式下真正运行算法时，系统将执行一次估算。如果估算显示执行超出其内存限制的可能性非常高，则禁止执行。要阅读更多关于此的内容，请参阅自动估算和执行阻塞。

有关 estimate 的更多详细信息，请参阅内存估算。

以下内容将估算运行算法所需的内存

CALL gds.influenceMaximization.celf.write.estimate('myGraph', {
  writeProperty: 'spread',
  seedSetSize: 3
})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 13. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
10	14	2608	2608	"2608 字节"

统计

在 stats 执行模式下，算法返回一行包含算法结果摘要的数据。此执行模式不会产生任何副作用。对于通过检查 computeMillis 返回项来评估算法性能非常有用。在下面的示例中，我们将省略返回的时间信息。过程的完整签名可以在语法部分中找到。

有关 stats 模式的更多详细信息，请参阅统计。

以下代码将以统计模式运行该算法

CALL gds.influenceMaximization.celf.stats('myGraph', {seedSetSize: 3})
YIELD totalSpread

表 14. 结果
totalSpread (总传播范围)
3.76

使用 stats 模式有助于检查不同的配置选项如何影响 totalSpread，并选择能产生最优传播结果的配置。

流

在 stream 执行模式下，算法返回属于种子集的节点的传播范围。这使我们可以直接检查结果，或在 Cypher 中进行后续处理，而不会产生任何副作用。

有关 stream 模式的更多详细信息，请参阅流式读取。

以下内容将运行算法并流式传输结果

CALL gds.influenceMaximization.celf.stream('myGraph', {seedSetSize: 3})
YIELD nodeId, spread
RETURN gds.util.asNode(nodeId).name AS name, spread
ORDER BY spread DESC, name ASC

表 15. 结果
名称 (name)	spread (传播范围)
"Alice"	1.46
"Ethan"	1.2
“Michael”	1.1

请注意，在 stream 模式下，结果仅为算法计算出的种子集。其他节点被认为没有影响力，因此不包含在结果中。

变异

mutate 执行模式在 stats 模式的基础上增加了一个重要的副作用：用包含该节点传播范围的新节点属性更新命名图。新属性的名称由强制配置参数 mutateProperty 指定。结果是单行摘要，类似于 stats，但包含一些额外的指标。当多个算法协同使用时，mutate 模式特别有用。

有关 mutate 模式的更多详细信息，请参阅变更。

以下代码将运行算法，并使用 mutateProperty 更新图

CALL gds.influenceMaximization.celf.mutate('myGraph', {
  mutateProperty: 'celfSpread',
  seedSetSize: 3
})
YIELD nodePropertiesWritten

表 16. 结果
nodePropertiesWritten
10

流式传输变异后的节点属性

CALL gds.graph.nodeProperty.stream('myGraph', 'celfSpread')
YIELD nodeId, propertyValue
RETURN gds.util.asNode(nodeId).name as name, propertyValue AS spread
ORDER BY spread DESC, name ASC

表 17. 结果
名称 (name)	spread (传播范围)
"Alice"	1.46
"Ethan"	1.2
“Michael”	1.1
"Amir"	0.0
"Ceri"	0.0
"Jack"	0.0
"Jimmy"	0.0
"Lara"	0.0
"Mohammed"	0.0
"Willie"	0.0

请注意，在 mutate 模式下，内存中图的所有节点都会获得 spread 属性。被算法认为没有影响力的节点，其值为零。

写入

write 执行模式在 stats 模式的基础上增加了一个重要的副作用：将每个节点的传播范围作为属性写入 Neo4j 数据库。新属性的名称由强制配置参数 writeProperty 指定。结果是单行摘要，类似于 stats，但包含一些额外的指标。write 模式支持将结果直接持久化到数据库中。

有关 write 模式的更多详细信息，请参阅写入。

以下内容将运行算法并流式传输结果

CALL gds.influenceMaximization.celf.write('myGraph', {
  writeProperty: 'celfSpread',
  seedSetSize: 3
})
YIELD nodePropertiesWritten

表 18. 结果
nodePropertiesWritten
10

查询写入的节点属性

MATCH (n) RETURN n.name AS name, n.celfSpread AS spread
ORDER BY spread DESC, name ASC

表 19. 结果
名称 (name)	spread (传播范围)
"Alice"	1.46
"Ethan"	1.2
“Michael”	1.1
"Amir"	0.0
"Ceri"	0.0
"Jack"	0.0
"Jimmy"	0.0
"Lara"	0.0
"Mohammed"	0.0
"Willie"	0.0

请注意，在 write 模式下，Neo4j 图中映射的所有节点都会获得 spread 属性。被算法认为没有影响力的节点，其值为零。