三角形计数

有向

无向

异构节点

异构关系

加权关系

词汇表

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

简介

三角形计数算法计算图中每个节点的三角形数量。三角形是由三个节点组成的集合，其中每个节点都与其他两个节点有关系。在图论术语中，这有时被称为 3-团。GDS 库中的三角形计数算法仅在无向图中查找三角形。

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

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

三角形计数和聚类系数已被证明可作为特征，用于将给定网站分类为垃圾邮件或非垃圾邮件内容。这在"用于大型图中局部三角形计数的有效半流算法"中进行了描述。

语法

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

每种模式下的三角形计数语法

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

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

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

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供的 ID，以便更轻松地跟踪算法的进度。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
maxDegree	整数	`2⁶³ - 1`	是	如果节点的度数高于此值，则算法不会考虑该节点。这些节点的三角形计数将为`-1`。

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

表 5. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供的 ID，以便更轻松地跟踪算法的进度。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
maxDegree	整数	`2⁶³ - 1`	是	如果节点的度数高于此值，则算法不会考虑该节点。这些节点的三角形计数将为`-1`。

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

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

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

表 8. 配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`n/a`	否	GDS 图中将三角形计数写入的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供的 ID，以便更轻松地跟踪算法的进度。
maxDegree	整数	`2⁶³ - 1`	是	如果节点的度数高于此值，则算法不会考虑该节点。这些节点的三角形计数将为`-1`。

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

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

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

表 11. 配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`n/a`	否	GDS 图中将三角形计数写入的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供的 ID，以便更轻松地跟踪算法的进度。
maxDegree	整数	`2⁶³ - 1`	是	如果节点的度数高于此值，则算法不会考虑该节点。这些节点的三角形计数将为`-1`。

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

三角形列表

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

此功能处于 Alpha 级别。有关功能级别的更多信息，请参阅API 级别。

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

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

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

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

表 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的度数。

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

三角形列表

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

此功能处于 Alpha 级别。有关功能级别的更多信息，请参阅API 级别。

以下操作将为每个三角形计算节点 ID 流并返回节点的名称属性

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”不属于任何三角形，因此不会出现在三角形列表中。