团计数 (Clique Counting)

术语表

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

简介

团（Clique）是指图中节点的一个子集，其中所有节点彼此相连，有时也被称为完全子图。团计数算法用于计算图中各种规模的团的数量。在 GDS 中，通过一种简洁的团树结构（Succinct Clique Tree-structure），无需枚举每个团即可高效完成此计算，详情请参阅 The Power of Pivoting for Exact Clique Counting。

计算图中的团数量，有助于了解整个图以及单个节点的拓扑结构和聚类情况。该算法仅计算规模为 3 或更大的团，因为规模为 1 和 2 的团是平凡的（分别对应节点和关系）。如果您只对三角形（规模为 3 的团）感兴趣，三角形计数 (Triangle Count) 是更好的选择。

有关团的更多信息，包括其应用场景，请参阅 https://en.wikipedia.org/wiki/Clique_(graph_theory)。

语法

本节介绍在每种执行模式下运行团计数算法所使用的语法。此处描述的是命名图变体语法。要了解更多关于通用语法变体的信息，请参阅语法概述。

各模式下的团计数语法

在命名图上以流模式 (stream mode) 运行团计数

CALL gds.cliqueCounting.stream(
  graphName: String,
  configuration: Map
)
YIELD
  nodeId: Integer,
  counts: List

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

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

表 3. 结果
名称	类型	描述
nodeId	整数	节点 ID。
counts	整数列表	该节点所属的规模 ≥ 3 的团的数量。

在命名图上以统计模式 (stats mode) 运行团计数

CALL gds.cliqueCounting.stats(
  graphName: String,
  configuration: Map
)
YIELD
  globalCount: List,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  configuration: Map

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

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

表 6. 结果
名称	类型	描述
globalCount	整数列表	图中规模 ≥ 3 的团的总数。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
配置	Map	用于运行算法的配置。

在命名图上以变更模式 (mutate mode) 运行团计数

CALL gds.cliqueCounting.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  globalCount: List,
  nodePropertiesWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  mutateMillis: Integer,
  configuration: Map

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

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

表 9. 结果
名称	类型	描述
globalCount	整数列表	图中规模 ≥ 3 的团的总数。
nodePropertiesWritten	整数	添加到投影图中的属性数量。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
mutateMillis	整数	向投影图添加属性的毫秒数。
配置	Map	用于运行算法的配置。

在命名图上以写入模式 (write mode) 运行团计数

CALL gds.cliqueCounting.write(
  graphName: String,
  configuration: Map
)
YIELD
  globalCount: List,
  nodePropertiesWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  writeMillis: Integer,
  configuration: Map

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

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

表 12. 结果
名称	类型	描述
globalCount	整数列表	图中规模 ≥ 3 的团的总数。
nodePropertiesWritten	整数	写入 Neo4j 的属性数量。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
writeMillis	整数	将结果写回 Neo4j 所需的毫秒数。
配置	Map	用于运行算法的配置。

示例

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

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

在本节中，我们将展示在具体图上运行团计数算法的示例。旨在说明结果的形式，并指导如何在实际场景中使用该算法。我们将使用一个小型社交网络图，其中少数节点以特定模式连接。示例图如下所示

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

CREATE
  (alice:Person {name: 'Alice'}),
  (michael:Person {name: 'Michael'}),
  (karin:Person {name: 'Karin'}),
  (chris:Person {name: 'Chris'}),
  (will:Person {name: 'Will'}),
  (mark:Person {name: 'Mark'}),

  (alice)-[:KNOWS]->(michael),
  (alice)-[:KNOWS]->(karin),
  (alice)-[:KNOWS]->(chris),
  (michael)-[:KNOWS]->(karin),
  (michael)-[:KNOWS]->(chris),
  (karin)-[:KNOWS]->(chris),

  (karin)-[:KNOWS]->(will),
  (chris)-[:KNOWS]->(will),
  (will)-[:KNOWS]->(mark)

图表已存在于 Neo4j 中，现在我们可以将其投影到图目录（graph catalog）中，为算法执行做准备。我们使用针对 Person 节点和 KNOWS 关系的 Cypher 投影来完成此操作。对于关系，我们必须使用 UNDIRECTED（无向）方向，因为团计数算法仅定义用于无向图。

以下语句将使用 Cypher 投影来投影一个图，并将其以“myGraph”的名称存储在图目录中。

MATCH (source:Person)-[r:KNOWS]->(target:Person)
RETURN gds.graph.project(
  'myGraph',
  source,
  target,
  {},
  { undirectedRelationshipTypes: ['*'] }
)

团计数算法要求图的关系使用 UNDIRECTED 方向。您可以创建带有无向关系的图，或者通过将有向关系转换为新的无向关系来更新图。

在以下示例中，我们将演示如何在图上使用团计数算法。

内存估算

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

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

以下内容将估算以写入模式运行算法所需的内存要求：

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

表 13. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
6	18	64	952	"[64 Bytes ... 952 Bytes]"

流模式 (Stream)

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

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

以下语句将以 stream 模式运行该算法：

CALL gds.cliqueCounting.stream('myGraph')
YIELD nodeId, counts
RETURN gds.util.asNode(nodeId).name AS name, counts
ORDER BY name ASC

表 14. 结果
名称 (name)	counts
"Alice"	[3, 1]
"Chris"	[4, 1]
"Karin"	[4, 1]
“Mark”	[]
“Michael”	[3, 1]
"Will"	[1]

在这里我们发现 'Chris' 节点参与了 4 个三角形和 1 个四元团，而 'Will' 节点仅参与了 1 个三角形。这可以在示例图中得到验证。由于 'Mark' 节点仅与 'Will' 节点相连，它不属于任何规模为 3 或更大的团，因此我们得到一个空列表。

请注意，对于规模为 k 的团，必然也存在规模为 k-1 的团，因为团的任何子集本身也是一个团。

统计模式 (Stats)

在 stats 执行模式下，算法返回包含算法结果摘要的单行数据。摘要结果包含全局团计数，即整个图中每种规模的团的总数。该执行模式没有任何副作用。它对于通过检查 computeMillis 返回项来评估算法性能非常有用。在下面的示例中，我们将省略返回的时间信息。程序的完整签名可以在语法部分找到。

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

以下语句将以 stats 模式运行该算法：

CALL gds.cliqueCounting.stats('myGraph')
YIELD globalCount

表 15. 结果
globalCount
[5, 1]

由此可见，该图有 6 个节点，总共有 5 个三角形，1 个四元团，没有更大的团。将其与流模式示例进行比较，我们可以看到 'Chris' 节点几乎参与了每一个团。例外情况是 'Michael-Karin-Alice' 三角形。换句话说，该节点参与了图中大部分的团，因此在图中处于非常核心的位置。

变更模式 (Mutate)

mutate 执行模式在 stats 模式的基础上增加了一个重要的副作用：使用包含该节点团计数的新节点属性来更新命名图。新属性的名称由强制配置参数 mutateProperty 指定。结果与 stats 类似，为单行摘要结果，但包含一些额外的指标。当多个算法协同使用时，mutate 模式特别有用。

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

以下语句将以 mutate 模式运行该算法：

CALL gds.cliqueCounting.mutate('myGraph', {
  mutateProperty: 'cliqueCount'
})
YIELD globalCount

表 16. 结果
globalCount
[5, 1]

返回的结果与 stats 示例相同。此外，图 'myGraph' 现在拥有了一个节点属性 cliqueCount，其中存储了每个节点的团计数。要了解如何检查内存中图的新架构，请参阅列出图 (Listing graphs)。

写入模式 (Write)

write 执行模式在 stats 模式的基础上增加了一个重要的副作用：将每个节点的团计数作为属性写入 Neo4j 数据库。新属性的名称由强制配置参数 writeProperty 指定。结果与 stats 类似，为单行摘要结果，但包含一些额外的指标。write 模式能够将结果直接持久化到数据库中。

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

以下语句将以 write 模式运行该算法：

CALL gds.cliqueCounting.write('myGraph', {
  writeProperty: 'cliqueCount'
})
YIELD globalCount

表 17. 结果
globalCount
[5, 1]

返回的结果与 stats 示例相同。此外，6 个节点中的每一个现在在 Neo4j 数据库中都有一个新的属性 cliqueCount，其中包含了该节点的团计数。