三角形计数 (Triangle Count)

术语表

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

简介

三角形计数算法用于计算图中每个节点的三角形数量。三角形是指三个节点的集合，其中每个节点都与其他两个节点存在关系。在图论术语中，这有时被称为 3-派系 (3-clique)。GDS 库中的三角形计数算法仅在无向图中查找三角形。

三角形计数在社交网络分析中广受欢迎，常用于检测社区并衡量这些社区的凝聚力。它也可用于确定图的稳定性，并且通常作为计算网络指数（如聚类系数）的一部分。三角形计数算法也用于计算局部聚类系数。

有关此算法的更多信息，请参阅

研究表明，三角形计数和聚类系数可作为将特定网站分类为垃圾内容或非垃圾内容的有效特征。这在“海量图中局部三角形计数的高效半流式算法”一文中有详细描述。

节点标签过滤

对于某些用例，仅计算包含特定节点标签的三角形非常有用。这也能节省计算时间，因为算法无需考虑不具备指定标签的节点。

该算法支持通过在配置中指定最多三个节点标签来进行节点标签过滤。如果指定了三个标签，算法将仅计算包含具备所有这三个标签的节点的三角形，且三角形中的每个标签必须至少由一个节点代表。如果指定的标签少于三个，算法将计算三角形中每个指定标签至少由一个节点代表的三角形，但未指定标签的节点也可以是三角形的一部分。如果列表中重复出现某个标签，则该标签必须由列表中出现的次数相同的节点数来代表。

语法

本节涵盖了在每种执行模式下执行三角形计数算法所使用的语法。我们将描述命名图的语法变体。要了解更多关于通用语法变体的信息，请参阅语法概述。

各模式下的三角形计数语法

在命名图上以流模式运行三角形计数

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

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

表 2. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
maxDegree	整数	`2⁶³ - 1`	是	如果节点的度数高于此值，算法将不予考虑。这些节点的三角形计数将为 `-1`。
labelFilter	字符串列表	`[]`	是	由最多三个节点标签组成的列表（字符串形式）。仅计算包含具有每个指定标签代表的节点的三角形。如果留空（默认），将计算所有三角形。
1. 在 GDS 会话中，默认值为可用处理器的数量。

表 3. 结果
名称	类型	描述
nodeId	整数	节点 ID。
triangleCount	整数	该节点所属的三角形数量。如果该节点因使用 `maxDegree` 配置参数而被排除在计算之外，则为 `-1`。

在命名图上以统计模式运行三角形计数

CALL gds.triangleCount.stats(
  graphName: String,
  configuration: Map
)
YIELD
  globalTriangleCount: Integer,
  nodeCount: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  configuration: Map

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

表 5. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[2]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
maxDegree	整数	`2⁶³ - 1`	是	如果节点的度数高于此值，算法将不予考虑。这些节点的三角形计数将为 `-1`。
labelFilter	字符串列表	`[]`	是	由最多三个节点标签组成的列表（字符串形式）。仅计算包含具有每个指定标签代表的节点的三角形。如果留空（默认），将计算所有三角形。
2. 在 GDS 会话中，默认值为可用处理器的数量。

表 6. 结果
名称	类型	描述
globalTriangleCount	整数	图中三角形的总数。
nodeCount	整数	图中的节点数。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算全局指标所耗费的毫秒数。
配置	Map	用于运行算法的配置。

在命名图上以变更模式运行三角形计数

CALL gds.triangleCount.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  globalTriangleCount: Integer,
  nodeCount: Integer,
  nodePropertiesWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  mutateMillis: Integer,
  configuration: Map

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

表 8. 配置
名称	类型	默认	可选	描述
mutateProperty	字符串	`不适用`	否	GDS 图中用于写入三角形计数的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
maxDegree	整数	`2⁶³ - 1`	是	如果节点的度数高于此值，算法将不予考虑。这些节点的三角形计数将为 `-1`。
labelFilter	字符串列表	`[]`	是	由最多三个节点标签组成的列表（字符串形式）。仅计算包含具有每个指定标签代表的节点的三角形。如果留空（默认），将计算所有三角形。

表 9. 结果
名称	类型	描述
globalTriangleCount	整数	图中三角形的总数。
nodeCount	整数	图中的节点数。
nodePropertiesWritten	整数	添加到投影图中的属性数量。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算全局指标所耗费的毫秒数。
mutateMillis	整数	向投影图添加属性的毫秒数。
配置	Map	用于运行算法的配置。

在命名图上以写入模式运行三角形计数

CALL gds.triangleCount.write(
  graphName: String,
  configuration: Map
)
YIELD
  globalTriangleCount: Integer,
  nodeCount: Integer,
  nodePropertiesWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  writeMillis: Integer,
  configuration: Map

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

表 11. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[3]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeProperty	字符串	`不适用`	否	Neo4j 数据库中用于写入三角形计数的节点属性。
maxDegree	整数	`2⁶³ - 1`	是	如果节点的度数高于此值，算法将不予考虑。这些节点的三角形计数将为 `-1`。
labelFilter	字符串列表	`[]`	是	由最多三个节点标签组成的列表（字符串形式）。仅计算包含具有每个指定标签代表的节点的三角形。如果留空（默认），将计算所有三角形。
3. 在 GDS 会话中，默认值为可用处理器的数量。

表 12. 结果
名称	类型	描述
globalTriangleCount	整数	图中三角形的总数。
nodeCount	整数	图中的节点数。
nodePropertiesWritten	整数	写入 Neo4j 的属性数量。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算全局指标所耗费的毫秒数。
writeMillis	整数	将结果写回 Neo4j 所需的毫秒数。
配置	Map	用于运行算法的配置。

三角形列表

除了标准执行模式外，还有一个名为 gds.triangles 的过程，可用于列出图中的所有三角形。

以下内容将返回每个三角形的节点 ID 流

CALL gds.triangles(
  graphName: String,
  configuration: Map
)
YIELD nodeA, nodeB, nodeC

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

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

表 15. 结果
名称	类型	描述
nodeA	整数	给定三角形中第一个节点的 ID。
nodeB	整数	给定三角形中第二个节点的 ID。
nodeC	整数	给定三角形中第三个节点的 ID。

示例

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

这些示例将 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'}),

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

在 Neo4j 中拥有该图后，我们可以将其投影到图目录中，为算法执行做准备。我们使用针对 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.triangleCount.write.estimate('myGraph', { writeProperty: 'triangleCount' })
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 16. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
6	16	160	160	"160 字节"

请注意，关系计数为 16，尽管我们在原始 Cypher 语句中仅投影了 8 个关系。这是因为我们使用了 UNDIRECTED 方向，它会将每个关系在两个方向上进行投影，实际上将关系数量翻了一番。

流模式

在 stream 执行模式下，算法返回每个节点的三角形计数。这使我们可以直接检查结果，或在 Cypher 中进行后处理而无需任何副作用。例如，我们可以对结果进行排序以找到三角形计数最高的节点。

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

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

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

表 17. 结果
名称 (name)	triangleCount
“Michael”	3
"Chris"	2
"Will"	2
"Karin"	1
“Mark”	1
"Alice"	0

在此我们发现 'Michael' 节点拥有的三角形最多。这可以在示例图中验证。由于 'Alice' 节点只 KNOWS 另一个节点，它不能成为任何三角形的一部分，因此算法报告计数为零。

统计模式

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

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

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

CALL gds.triangleCount.stats('myGraph')
YIELD globalTriangleCount, nodeCount

表 18. 结果
globalTriangleCount	nodeCount
3	6

这里我们可以看到该图有六个节点，总共三个三角形。与流模式示例相比，我们可以看到 'Michael' 节点的三角形计数等于全局三角形计数。换句话说，该节点是图中所有三角形的一部分，因此在图中处于非常核心的位置。

变更模式

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

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

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

CALL gds.triangleCount.mutate('myGraph', {
  mutateProperty: 'triangles'
})
YIELD globalTriangleCount, nodeCount

表 19. 结果
globalTriangleCount	nodeCount
3	6

返回的结果与 stats 示例中的相同。此外，图 'myGraph' 现在具有一个节点属性 triangles，其中存储了每个节点的三角形计数。要了解如何检查内存中图的新模式，请参阅列出图。

写入模式

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

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

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

CALL gds.triangleCount.write('myGraph', {
  writeProperty: 'triangles'
})
YIELD globalTriangleCount, nodeCount

表 20. 结果
globalTriangleCount	nodeCount
3	6

返回的结果与 stats 示例中的相同。此外，这六个节点中的每一个现在在 Neo4j 数据库中都有一个新的属性 triangles，其中包含该节点的三角形计数。

最大度数

三角形计数算法支持 maxDegree 配置参数，如果节点的度数大于配置的值，则可以使用它将节点从处理中排除。当图中存在度数非常高的节点（所谓的超级节点）时，这对于加速计算非常有用。超级节点对三角形计数算法的性能有很大影响。要了解图的度数分布，请参阅列出图。

被排除在计算之外的节点被分配的三角形计数为 -1。

以下内容将以 stream 模式运行带有 maxDegree 参数的算法

CALL gds.triangleCount.stream('myGraph', {
  maxDegree: 4
})
YIELD nodeId, triangleCount
RETURN gds.util.asNode(nodeId).name AS name, triangleCount
ORDER BY name ASC

表 21. 结果
名称 (name)	triangleCount
"Alice"	0
"Chris"	0
"Karin"	0
“Mark”	0
“Michael”	-1
"Will"	0

在 maxDegree: 4 的示例图上运行该算法会将 'Michael' 节点从计算中排除，因为它有 5 个度数。

由于该节点是示例图中所有三角形的一部分，将其排除会导致没有三角形。

三角形列表

在 Aura Graph Analytics 中，此功能仅通过 Python 客户端提供。它目前无法作为 Cypher 过程或函数使用。

也可以列出图中的所有三角形。为此，我们使用过程 gds.triangles。

以下内容将计算每个三角形的节点 ID 流并返回节点的 name 属性

CALL gds.triangles('myGraph')
YIELD nodeA, nodeB, nodeC
RETURN
  gds.util.asNode(nodeA).name AS nodeA,
  gds.util.asNode(nodeB).name AS nodeB,
  gds.util.asNode(nodeC).name AS nodeC
ORDER BY nodeA, nodeB, nodeC ASC

表 22. 结果
nodeA	nodeB	nodeC
“Michael”	"Chris"	"Karin"
“Michael”	“Mark”	"Will"
“Michael”	"Will"	"Chris"

我们可以看到图中共有三个三角形：“Will、Michael 和 Chris”、“Will、Mark 和 Michael”以及“Michael、Karin 和 Chris”。节点“Alice”不属于任何三角形，因此不会出现在三角形列表中。