CELF

有向

无向

异构节点

异构关系

加权关系

词汇表

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

简介

影响力最大化问题旨在寻找一组 k 个节点，以最大化网络中影响力预期的传播范围。这些初始 k 个节点的集合称为种子集。

Neo4j GDS 库支持在独立级联传播模型下近似计算最佳种子集。在该传播模型中，最初我们假设种子集中的节点受到影响，过程如下：一个受影响的节点以概率 p 影响其每个邻居。传播范围则是受影响节点的数量。

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

CELF 算法基于该问题的贪心算法。它以 k 个步骤迭代工作，创建返回的种子集 S，其中每一步都将产生最大预期传播增益的节点添加到 S 中。

节点 u 不在 S 中的预期传播增益通过运行 mc 次不同的蒙特卡洛传播过程模拟来估计，并针对每次模拟计算如果将 u 添加到 S 中将受影响的节点数量。

CELF 算法通过引入一种惰性转发机制扩展了贪心算法，该机制修剪了大量不被检查的节点，从而大大减少了模拟次数。这使得 CELF 在大型网络上比贪心算法快得多。

语法

CELF 各模式语法

在命名图上以流模式运行 CELF。

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

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

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

表 3. 结果
名称	类型	描述
nodeId	整数	节点 ID。
spread	浮点数	通过选择该节点获得的传播范围。

在命名图上以统计模式运行 CELF。

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

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

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

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

在命名图上以变异模式运行 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	字符串	`不适用`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定和/或图过滤的配置。

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

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

在命名图上以写入模式运行 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	字符串	`不适用`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定和/或图过滤的配置。

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

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

示例

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

示例通常使用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
"爱丽丝"	1.46
"伊森"	1.2
"迈克尔"	1.1

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

变异

mutate 执行模式扩展了 stats 模式，并带有一个重要的副作用：用包含该 influenceMaximization 传播范围的新 influenceMaximization 属性更新命名图。新属性的名称通过强制配置参数 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
"爱丽丝"	1.46
"伊森"	1.2
"迈克尔"	1.1
"阿米尔"	0.0
"塞里"	0.0
"杰克"	0.0
"吉米"	0.0
"劳拉"	0.0
"穆罕默德"	0.0
"威利"	0.0

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

写入

write 执行模式扩展了 stats 模式，并带有一个重要的副作用：将每个 influenceMaximization 的传播范围作为属性写入 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
"爱丽丝"	1.46
"伊森"	1.2
"迈克尔"	1.1
"阿米尔"	0.0
"塞里"	0.0
"杰克"	0.0
"吉米"	0.0
"劳拉"	0.0
"穆罕默德"	0.0
"威利"	0.0

请注意，在 write 模式下，Neo4j 投影图中的所有节点都将获得 spread 属性。算法不认为有影响力的节点将获得零值。