弱连接组件

词汇表

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

简介

弱连接组件 (WCC) 算法用于查找有向图和无向图中相互连接的节点集合。如果两个节点之间存在路径，则称它们是连接的。所有相互连接的节点集合形成一个组件。与强连接组件 (SCC) 不同，WCC 不考虑两个节点之间路径上关系的方向。例如，在有向图 (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	字符串	`不适用`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	用于算法特定设置和/或图过滤的配置。

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

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

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

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

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

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

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

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

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

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

示例

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

这些示例使用 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. 结果
名称	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

以下将使用 seedProperty 在 stream 模式下运行算法

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. 结果
名称	componentId
"Alice"	0
"Charles"	0
"Bridget"	1
"Mats"	1
"Doug"	3
"Mark"	3
"Michael"	3

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

写入预置组件

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

以下将使用 seedProperty 在 write 模式下运行算法

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. 结果
名称	componentId
"Alice"	0
"Bridget"	0
"Charles"	0
"Doug"	3
"Mark"	3
"Michael"	3

实际的组件 ID 可能会因图采样优化中的随机性而异。在这种情况下，获得逆解同样是合理的，例如当我们的社区 0 节点被映射到社区 3，反之亦然。