CELF

有向

无向

异构节点

异构关系

加权关系

词汇表

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

介绍

影响力最大化问题要求找到一组k个节点，以最大化网络中影响力的预期传播。这组初始k称为种子集。

Neo4j GDS 库支持在独立级联传播模型下对最佳种子集进行近似计算。在这个传播模型中，我们最初假设种子集中的节点受到影响，并且该过程按以下方式进行。一个受影响的节点以概率p影响其每个邻居。然后，传播是受影响节点的数量。

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

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

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

CELF 算法通过引入延迟转发机制扩展了贪婪算法，该机制可以剪枝许多节点，从而大量减少了执行的模拟次数。这使得 CELF 在大型网络上的速度比贪婪算法快得多。

语法

每个模式的 CELF 语法

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

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

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

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

表 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	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	地图	`{}`	是	算法特定和/或图过滤的配置。

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

表 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	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	地图	`{}`	是	算法特定和/或图过滤的配置。

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

表 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	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	地图	`{}`	是	算法特定和/或图过滤的配置。

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

表 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
"Alice"	1.46
"Ethan"	1.2
"Michael"	1.1

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

变异

mutate执行模式通过一个重要的副作用扩展了stats模式：使用包含该影响力最大化值的传播的新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
"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属性。算法认为没有影响力的节点接收值为零。