强连通分量 (Strongly Connected Components)

强连通分量 (SCC) 算法用于查找有向图中最大的连通节点集。如果一个集合中的每对节点之间都存在有向路径，则该集合被视为一个强连通分量。它通常在图分析过程的早期使用，帮助我们了解图的结构。

术语表

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

历史与解释

SCC 是最早的图算法之一，第一个线性时间算法由 Tarjan 于 1972 年描述。将有向图分解为其强连通分量是深度优先搜索算法的经典应用。

用例 - 何时使用强连通分量算法

在对大型跨国公司进行分析时，SCC 可用于查找这样一组公司：其中的每个成员都直接或间接地拥有其他所有成员的股份。尽管这种结构具有减少交易成本和增加信任等好处，但它可能会削弱市场竞争。阅读更多内容请参见 "全球企业控制网络" (The Network of Global Corporate Control)。
SCC 可用于在衡量多跳无线网络中的路由性能时，计算不同网络配置的连通性。阅读更多内容请参见 "多跳无线网络中存在单向链路时的路由性能" (Routing performance in the presence of unidirectional links in multihop wireless networks)
强连通分量算法可以用作许多仅适用于强连通图的图算法的第一步。在社交网络中，一群人通常是强连通的（例如，同一个班级或在同一个公共场所的学生）。这些群体中的许多人通常喜欢一些共同的页面，或玩共同的游戏。SCC 算法可用于查找此类群体，并向群体中尚未喜欢这些页面或游戏的人推荐他们可能喜欢的页面或游戏。

语法

各模式下的分解语法

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

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

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

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

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

以下代码将在统计 (stats) 模式下运行该算法

CALL gds.scc.stats(
  graphName: string,
  configuration: map
)
YIELD
  componentCount: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  componentDistribution: Map,
  configuration: Map

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

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

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

以下代码将运行算法并改变内存中的图

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

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

表 8. 配置
名称	类型	默认	可选	描述
mutateProperty	字符串	`不适用`	否	GDS 图中写入组件的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
consecutiveIds	布尔值	`false`	是	用于决定组件标识符是否映射到连续 ID 空间的标志（需要额外的内存）。

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

以下代码将运行算法并回写结果：

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

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

表 11. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[3]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeProperty	字符串	`不适用`	否	Neo4j 数据库中写入组件的节点属性。
consecutiveIds	布尔值	`false`	是	用于决定组件标识符是否映射到连续 ID 空间的标志（需要额外的内存）。
3. 在 GDS 会话中，默认值为可用处理器的数量。

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

强连通分量算法示例

以下代码将创建一个示例图

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

CREATE (nAlice)-[:FOLLOW]->(nBridget)
CREATE (nAlice)-[:FOLLOW]->(nCharles)
CREATE (nMark)-[:FOLLOW]->(nDoug)
CREATE (nMark)-[:FOLLOW]->(nMichael)
CREATE (nBridget)-[:FOLLOW]->(nMichael)
CREATE (nDoug)-[:FOLLOW]->(nMark)
CREATE (nMichael)-[:FOLLOW]->(nAlice)
CREATE (nAlice)-[:FOLLOW]->(nMichael)
CREATE (nBridget)-[:FOLLOW]->(nAlice)
CREATE (nMichael)-[:FOLLOW]->(nBridget);

以下代码将投影并存储一个命名图

MATCH (source:User)-[r:FOLLOW]->(target:User)
RETURN gds.graph.project(
  'graph',
  source,
  target
)

内存估算

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

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

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

CALL gds.scc.write.estimate('graph', { writeProperty: 'componentId' })
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 13. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
6	10	33332	33332	"32 KiB"

流 (Stream)

在 stream 执行模式下，算法返回每个节点的组件。这使我们可以直接检查结果，或在 Cypher 中进行后续处理，而不会产生任何副作用。

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

以下代码将运行算法并流式返回结果

CALL gds.scc.stream('graph', {})
YIELD nodeId, componentId
RETURN gds.util.asNode(nodeId).name AS Name, componentId AS Component
ORDER BY Component, Name DESC

表 14. 结果
名称	Component (组件)
`“Michael”`	`0`
`“Bridget”`	`0`
`"Alice"`	`0`
`“Charles”`	`3`
`“Mark”`	`4`
`“Doug”`	`4`

在我们的示例图中，有 3 个强连通分量。

第一个也是最大的组件包含 Alice、Bridget 和 Michael，而第二个最大的组件包含 Doug 和 Mark。Charles 最终处于他自己的组件中，因为没有从该节点指向其他任何节点的传出关系。

统计 (Stats)

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

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

以下命令将运行算法并以统计和测量值的形式返回结果

CALL gds.scc.stats('graph')
YIELD componentCount

表 15. 结果
componentCount
3

改变 (Mutate)

mutate 执行模式扩展了 stats 模式，并带有一个重要的副作用：使用包含该节点组件的新节点属性来更新命名图。新属性的名称使用必需的配置参数 mutateProperty 指定。结果是一行汇总数据，类似于 stats，但包含一些额外的指标。mutate 模式在同时使用多种算法时特别有用。

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

以下代码将运行算法并将结果存储在 graph 中

CALL gds.scc.mutate('graph', { mutateProperty: 'componentId'})
YIELD componentCount

表 16. 结果
componentCount
3

写入 (Write)

write 执行模式扩展了 stats 模式，并带有一个重要的副作用：将每个节点的组件作为属性写入 Neo4j 数据库。新属性的名称使用必需的配置参数 writeProperty 指定。结果是一行汇总数据，类似于 stats，但包含一些额外的指标。write 模式可以直接将结果持久化到数据库中。

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