弱连接组件

词汇表

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

简介

弱连接组件 (WCC) 算法在有向图和无向图中查找连接节点集。如果两个节点之间存在路径，则这两个节点是连接的。所有彼此连接的节点集形成一个组件。与强连接组件 (SCC) 相比，路径上两个节点之间关系的方向不予考虑。例如，在有向图 (a)→(b) 中，即使不存在有向关系 (b)→(a)，a 和 b 也会位于同一个组件中。

WCC 通常在分析初期用于了解图的结构。使用 WCC 了解图结构使能够在识别出的集群上独立运行其他算法。

该算法的实现基于以下论文

语法

本节介绍在每种执行模式下执行弱连接组件算法时使用的语法。我们正在描述命名图变体的语法。要了解有关一般语法变体的更多信息，请参阅语法概述。

WCC 每个模式的语法

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

CALL gds.wcc.stream(
  graphName: String,
  configuration: Map
)
YIELD
  nodeId: Integer,
  componentId: Integer

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

表 2. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点将被包含在内。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系将被包含在内。
并发	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性的名称。如果未指定，则算法将无权重运行。
seedProperty	字符串	`n/a`	是	用于设置节点的初始组件。属性值需要是数字。
threshold	浮点数	`null`	是	关系在计算中被考虑的权重值。
consecutiveIds	布尔值	`false`	是	标志，用于决定组件标识符是否映射到连续的 ID 空间（需要额外的内存）。
minComponentSize	整数	`0`	是	仅返回大小大于或等于给定值的社区中的节点。

表 3. 结果
名称	类型	描述
nodeId	整数	节点 ID。
componentId	整数	组件 ID。

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

CALL gds.wcc.stats(
  graphName: String,
  configuration: Map
)
YIELD
  componentCount: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  componentDistribution: Map,
  configuration: Map

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

表 5. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点将被包含在内。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系将被包含在内。
并发	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性的名称。如果未指定，则算法将无权重运行。
seedProperty	字符串	`n/a`	是	用于设置节点的初始组件。属性值需要是数字。
threshold	浮点数	`null`	是	关系在计算中被考虑的权重值。
consecutiveIds	布尔值	`false`	是	标志，用于决定组件标识符是否映射到连续的 ID 空间（需要额外的内存）。

表 6. 结果
名称	类型	描述
componentCount	整数	计算出的组件数量。
preProcessingMillis	整数	预处理数据所用的毫秒数。
computeMillis	整数	运行算法所用的毫秒数。
postProcessingMillis	整数	计算组件计数和分布统计所用的毫秒数。
componentDistribution	地图	包含组件大小的最小值、最大值、平均值以及 p1、p5、p10、p25、p50、p75、p90、p95、p99 和 p999 百分位数的映射。
配置	地图	用于运行算法的配置。

在命名图上以修改模式运行 WCC。

CALL gds.wcc.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  componentCount: Integer,
  nodePropertiesWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  mutateMillis: Integer,
  postProcessingMillis: Integer,
  componentDistribution: Map,
  configuration: Map

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

表 8. 配置
名称	类型	默认	可选	描述
mutateProperty	字符串	`n/a`	否	GDS 图中将组件 ID 写入的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
并发	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可用于更轻松地跟踪算法进度的 ID。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性的名称。如果未指定，则算法将无权重运行。
seedProperty	字符串	`n/a`	是	用于设置节点的初始组件。属性值需要是数字。
threshold	浮点数	`null`	是	关系在计算中被考虑的权重值。
consecutiveIds	布尔值	`false`	是	标志，用于决定组件标识符是否映射到连续的 ID 空间（需要额外的内存）。

表 9. 结果
名称	类型	描述
componentCount	整数	计算出的组件数量。
nodePropertiesWritten	整数	写入的节点属性数量。
preProcessingMillis	整数	预处理数据所用的毫秒数。
computeMillis	整数	运行算法所用的毫秒数。
mutateMillis	整数	向投影图添加属性所用的毫秒数。
postProcessingMillis	整数	计算组件计数和分布统计所用的毫秒数。
componentDistribution	地图	包含组件大小的最小值、最大值、平均值以及 p1、p5、p10、p25、p50、p75、p90、p95、p99 和 p999 百分位数的映射。
配置	地图	用于运行算法的配置。

在命名图上以写入模式运行 WCC。

CALL gds.wcc.write(
  graphName: String,
  configuration: Map
)
YIELD
  componentCount: Integer,
  nodePropertiesWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  writeMillis: Integer,
  postProcessingMillis: Integer,
  componentDistribution: Map,
  configuration: Map

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

表 11. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点将被包含在内。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系将被包含在内。
并发	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数量。
writeProperty	字符串	`n/a`	否	Neo4j 数据库中将组件 ID 写入的节点属性。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性的名称。如果未指定，则算法将无权重运行。
seedProperty	字符串	`n/a`	是	用于设置节点的初始组件。属性值需要是数字。
threshold	浮点数	`null`	是	关系在计算中被考虑的权重值。
consecutiveIds	布尔值	`false`	是	标志，用于决定组件标识符是否映射到连续的 ID 空间（需要额外的内存）。
minComponentSize	整数	`0`	是	仅将大小大于或等于给定值的社区中的节点写入底层 Neo4j 数据库。

表 12. 结果
名称	类型	描述
componentCount	整数	计算出的组件数量。
nodePropertiesWritten	整数	写入的节点属性数量。
preProcessingMillis	整数	预处理数据所用的毫秒数。
computeMillis	整数	运行算法所用的毫秒数。
writeMillis	整数	将结果写回 Neo4j 所用的毫秒数。
postProcessingMillis	整数	计算组件计数和分布统计所用的毫秒数。
componentDistribution	地图	包含组件大小的最小值、最大值、平均值以及 p1、p5、p10、p25、p50、p75、p90、p95、p99 和 p999 百分位数的映射。
配置	地图	用于运行算法的配置。

示例

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

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

在本节中，我们将展示在具体图上运行弱连接组件算法的示例。目的是说明结果看起来是什么样的，并提供如何在实际环境中使用该算法的指南。我们将在一个小的用户网络图上进行此操作，该图只有几个以特定模式连接的节点。示例图如下所示

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

CREATE
  (nAlice:User {name: 'Alice'}),
  (nBridget:User {name: 'Bridget'}),
  (nCharles:User {name: 'Charles'}),
  (nDoug:User {name: 'Doug'}),
  (nMark:User {name: 'Mark'}),
  (nMichael:User {name: 'Michael'}),

  (nAlice)-[:LINK {weight: 0.5}]->(nBridget),
  (nAlice)-[:LINK {weight: 4}]->(nCharles),
  (nMark)-[:LINK {weight: 1.1}]->(nDoug),
  (nMark)-[:LINK {weight: 2}]->(nMichael);

该图有两个连接的组件，每个组件都有三个节点。连接每个组件中的节点的关系具有一个属性 weight，该属性决定关系的强度。

以下语句将使用 Cypher 投影投影图，并将其存储在图目录中，名称为 'myGraph'。

MATCH (source:User)-[r:LINK]->(target:User)
RETURN gds.graph.project(
  'myGraph',
  source,
  target,
  { relationshipProperties: r { .weight } }
)

在以下示例中，我们将演示在该图上使用弱连接组件算法。

内存估算

首先，我们将使用 estimate 过程估算运行算法的成本。这可以使用任何执行模式完成。在本例中，我们将使用 write 模式。估算算法对于了解在图上运行算法将产生的内存影响很有用。当您稍后在某个执行模式中实际运行算法时，系统将执行估算。如果估算显示执行极有可能超过其内存限制，则将禁止执行。有关更多信息，请参阅自动估算和执行阻止。

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

以下将估算在写入模式下运行算法的内存需求

CALL gds.wcc.write.estimate('myGraph', { writeProperty: 'component' })
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 13. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
6	4	112	112	"112 字节"

流

在 stream 执行模式中，算法将返回每个节点的组件 ID。这允许我们直接检查结果或在 Cypher 中对它们进行后处理，而不会产生任何副作用。例如，我们可以对结果进行排序，以查看属于同一组件的节点彼此相邻显示。

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

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

CALL gds.wcc.stream('myGraph')
YIELD nodeId, componentId
RETURN gds.util.asNode(nodeId).name AS name, componentId
ORDER BY componentId, name

表 14. 结果
name	componentId
"Alice"	0
"Bridget"	0
"Charles"	0
"Doug"	3
"Mark"	3
"Michael"	3

结果显示算法识别出两个组件。这可以在示例图中验证。

算法的默认行为是运行 unweighted，即不使用 relationship 权重。weighted 选项将在加权中演示

实际的组件 ID 可能会有所不同，因为内存中图中投影的节点顺序没有保证。对于这种情况，获得反向解决方案也是同样合理的，例如，当我们的社区 0 节点映射到社区 3 而不是相反时。

统计信息

在 stats 执行模式中，算法返回包含算法结果摘要的单行。此执行模式没有任何副作用。它对于通过检查 computeMillis 返回项来评估算法性能很有用。在以下示例中，我们将省略返回计时。过程的完整签名可以在语法部分中找到。

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

以下将以 stats 模式运行算法

CALL gds.wcc.stats('myGraph')
YIELD componentCount

表 15. 结果
componentCount
2

结果显示 myGraph 有两个组件，这可以通过查看示例图来验证。

修改

mutate 执行模式扩展了 stats 模式，并具有一个重要的副作用：使用新的节点属性更新命名图，该属性包含该节点的组件 ID。新属性的名称使用强制配置参数 mutateProperty 指定。结果是单行摘要，类似于 stats，但有一些额外的指标。mutate 模式在将多个算法结合使用时特别有用。

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

以下将以 mutate 模式运行算法

CALL gds.wcc.mutate('myGraph', { mutateProperty: 'componentId' })
YIELD nodePropertiesWritten, componentCount;

表 16. 结果
nodePropertiesWritten	componentCount
6	2

写入

write 执行模式扩展了 stats 模式，并具有一个重要的副作用：将每个节点的组件 ID 作为属性写入 Neo4j 数据库。新属性的名称使用强制配置参数 writeProperty 指定。结果是单行摘要，类似于 stats，但有一些额外的指标。write 模式能够将结果直接持久化到数据库中。

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

以下将以 write 模式运行算法

CALL gds.wcc.write('myGraph', { writeProperty: 'componentId' })
YIELD nodePropertiesWritten, componentCount;

表 17. 结果
nodePropertiesWritten	componentCount
6	2

正如我们从结果中看到的，算法将彼此连接的节点计算为属于同一连接的组件。

加权

通过配置算法以使用权重，我们可以增加算法计算组件分配方式的粒度。我们通过使用 relationshipWeightProperty 配置参数指定属性键来实现这一点。此外，我们可以为权重值指定一个阈值。然后，只有大于阈值的值的权重才会被算法考虑。我们通过使用 threshold 配置参数指定阈值来实现这一点。

如果关系没有指定权重属性，则算法将回退到使用默认值零。

以下将使用关系权重运行算法并流式传输结果

CALL gds.wcc.stream('myGraph', {
  relationshipWeightProperty: 'weight',
  threshold: 1.0
}) YIELD nodeId, componentId
RETURN gds.util.asNode(nodeId).name AS Name, componentId AS ComponentId
ORDER BY ComponentId, Name

表 18. 结果
名称	ComponentId
`"Alice"`	`0`
`"Charles"`	`0`
`"Bridget"`	`1`
`"Doug"`	`3`
`"Mark"`	`3`
`"Michael"`	`3`

正如我们从结果中看到的，名为 'Bridget' 的节点现在处于自己的组件中，因为它的关系权重小于配置的阈值，因此被忽略了。

我们使用流模式来说明以加权或无权重方式运行算法，所有其他算法模式也支持此配置参数。

种子组件

可以使用 seedProperty 配置参数为节点定义初步组件 ID。如果我们想要保留先前运行的组件，并且已知没有组件通过删除关系而被拆分，这将非常有用。属性值需要是数字。

该算法首先检查节点是否分配了种子组件 ID。如果存在，则使用该组件 ID。否则，会为节点分配一个新的唯一组件 ID。

一旦每个节点都属于一个组件，算法就会合并连接节点的组件。当组件合并时，生成的组件始终是组件 ID 最小的那个。请注意，为了保留种子值，不能将 consecutiveIds 配置选项与种子一起使用。

该算法假设具有相同种子值的节点实际上属于同一个组件。如果不同组件中的两个节点具有相同的种子，则行为未定义。建议在没有种子时运行 WCC。

为了在实践中演示这一点，我们将执行几个步骤

我们将运行该算法并将结果写入 Neo4j。
然后我们将向我们的图中添加另一个节点，该节点将不会具有在步骤 1 中计算的属性。
我们将创建一个新的图，该图将步骤 1 的结果作为 nodeProperty。
然后我们将再次运行该算法，这次以 stream 模式运行，并将使用 seedProperty 配置参数。

我们将使用 WCC 的加权变体。

步骤 1

以下将以 write 模式运行算法

CALL gds.wcc.write('myGraph', {
  writeProperty: 'componentId',
  relationshipWeightProperty: 'weight',
  threshold: 1.0
})
YIELD nodePropertiesWritten, componentCount;

表 19. 结果
nodePropertiesWritten	componentCount
6	3

步骤 2

算法完成写入 Neo4j 后，我们希望在数据库中创建一个新节点。

以下操作将在 Neo4j 图中创建一个新节点，该节点没有组件 ID

MATCH (b:User {name: 'Bridget'})
CREATE (b)-[:LINK {weight: 2.0}]->(new:User {name: 'Mats'})

步骤 3

请注意，我们不能使用已经投影的图，因为它不包含组件 ID。因此，我们将投影第二个包含先前计算的组件 ID 的图。

以下操作将投影一个包含先前计算的组件 ID 的新图

MATCH (source:User)-[r:LINK]->(target:User)
RETURN gds.graph.project(
  'myGraph-seeded',
  source,
  target,
  {
    sourceNodeProperties: source { .componentId },
    targetNodeProperties: target { .componentId },
    relationshipProperties: r { .weight }
  }
)

步骤 4

以下操作将以 stream 模式运行该算法，使用 seedProperty

CALL gds.wcc.stream('myGraph-seeded', {
  seedProperty: 'componentId',
  relationshipWeightProperty: 'weight',
  threshold: 1.0
}) YIELD nodeId, componentId
RETURN gds.util.asNode(nodeId).name AS name, componentId
ORDER BY componentId, name

表 20. 结果
name	componentId
"Alice"	0
"Charles"	0
"Bridget"	1
"Mats"	1
"Doug"	3
"Mark"	3
"Michael"	3

结果表明，尽管在投影时没有 seedProperty，但节点 'Mats' 已被分配到与节点 'Bridget' 相同的组件中。这是正确的，因为这两个节点是连接的。

写入带种子的组件

在上一节中，我们演示了 seedProperty 在 stream 模式下的用法。它也可以在算法的其他模式下使用。以下是关于如何在 write 模式下使用 seedProperty 的示例。请注意，以下示例依赖于上一节的步骤 1-3。

以下操作将以 write 模式运行该算法，使用 seedProperty

CALL gds.wcc.write('myGraph-seeded', {
  seedProperty: 'componentId',
  writeProperty: 'componentId',
  relationshipWeightProperty: 'weight',
  threshold: 1.0
})
YIELD nodePropertiesWritten, componentCount;

表 21. 结果
nodePropertiesWritten	componentCount
1	3

如果 seedProperty 配置参数的值与 writeProperty 相同，则该算法仅为组件 ID 发生变化的节点写入属性。如果它们不同，则该算法为所有节点写入属性。

图采样优化

WCC 实现提供了两种计算策略

未采样策略，如无等待并行算法用于并查集问题中所述。
采样策略，如通过子图采样优化并行图连通性计算中所述

虽然两种策略都提供了非常好的性能，但采样策略通常更快。使用哪种策略的决定取决于输入图。如果图的关系是 …

… 无向的，该算法将选择采样策略。
… 有向的，该算法将选择未采样策略。
… 有向且反向索引的，该算法将选择采样策略。

关系的方向由 orientation 定义，可以在图投影期间设置。虽然 NATURAL 和 REVERSE 方向导致有向图，但 UNDIRECTED 方向会导致无向关系。为了创建具有反向索引关系的有向图，可以使用 indexInverse 参数作为关系投影的一部分。反向索引允许该算法根据相反的方向遍历节点的关系。如果图使用 NATURAL 方向投影，则反向索引表示 REVERSE 方向，反之亦然。

以下语句将使用带有反向索引的 Cypher 投影投影上述示例图，并将其存储在图目录中，名为 myIndexedGraph。

MATCH (source:User)-[r:LINK]->(target:User)
RETURN gds.graph.project(
  'myIndexedGraph',
  source,
  target,
  {},
  { inverseIndexedRelationshipTypes: ['*'] }
)

以下查询与上一节中的流示例相同。这次，我们在 myIndexedGraph 上执行 WCC，这将允许该算法使用采样策略。

以下操作将使用采样策略运行该算法并流式传输结果

CALL gds.wcc.stream('myIndexedGraph')
YIELD nodeId, componentId
RETURN gds.util.asNode(nodeId).name AS name, componentId
ORDER BY componentId, name

表 22. 结果
name	componentId
"Alice"	0
"Bridget"	0
"Charles"	0
"Doug"	3
"Mark"	3
"Michael"	3

由于图采样优化中的随机性，实际的组件 ID 可能会有所不同。对于这种情况，获得反向解决方案同样可能，例如，当我们的社区 0 节点映射到社区 3 而不是相反时。