局部聚类系数 (Local Clustering Coefficient)

术语表

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

简介

局部聚类系数算法用于计算图中每个节点的局部聚类系数。节点 n 的局部聚类系数 C_n 描述了 n 的邻居之间也相互连接的可能性。为了计算 C_n，我们使用节点参与的三角形数量 T_n 以及节点的度 d_n。计算局部聚类系数的公式如下：

如我们所见，计算局部聚类系数需要用到三角形计数。为此，算法会调用三角形计数 (Triangle Count) 算法。

此外，该算法还可以计算整个图的平均聚类系数。这是所有局部聚类系数的归一化总和。

更多信息，请参阅聚类系数。

语法

本节涵盖执行局部聚类系数算法在各种模式下的语法。我们描述的是命名图变体的语法。要了解更多关于通用语法变体的信息，请参阅语法概述。

局部聚类系数各模式的语法

在命名图上以流模式 (stream) 运行局部聚类系数

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

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

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

表 3. 结果
名称	类型	描述
nodeId	整数	节点 ID。
localClusteringCoefficient	双精度浮点数	局部聚类系数。

在命名图上以统计模式 (stats) 运行局部聚类系数

CALL gds.localClusteringCoefficient.stats(
  graphName: String,
  configuration: Map
)
YIELD
  averageClusteringCoefficient: Double,
  nodeCount: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  configuration: Map

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

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

表 6. 结果
名称	类型	描述
averageClusteringCoefficient	双精度浮点数	平均聚类系数。
nodeCount	整数	图中的节点数。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算全局指标所耗费的毫秒数。
配置	Map	用于运行算法的配置。

在命名图上以变异模式 (mutate) 运行局部聚类系数

CALL gds.localClusteringCoefficient.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  averageClusteringCoefficient: Double,
  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 以更轻松地跟踪算法的进度。
triangleCountProperty	字符串	`不适用`	是	包含预计算三角形计数的节点属性。

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

在命名图上以写入模式 (write) 运行局部聚类系数

CALL gds.localClusteringCoefficient.write(
  graphName: String,
  configuration: Map
)
YIELD
  averageClusteringCoefficient: Double,
  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 数据库中用于写入局部聚类系数的节点属性。
triangleCountProperty	字符串	`不适用`	是	包含预计算三角形计数的节点属性。
3. 在 GDS 会话中，默认值为可用处理器的数量。

表 12. 结果
名称	类型	描述
averageClusteringCoefficient	双精度浮点数	平均聚类系数。
nodeCount	整数	图中的节点数。
nodePropertiesWritten	整数	写入 Neo4j 的属性数量。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算全局指标所耗费的毫秒数。
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'}),

  (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 方向。您可以创建带有无向关系的图，或者通过将有向关系转换为新的无向关系来更新它。

在接下来的示例中，我们将演示如何在 'myGraph' 上使用局部聚类系数算法。

内存估算

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

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

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

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

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

请注意，尽管我们在原始 Cypher 语句中只创建了 8 个关系，但关系计数为 16。这是因为我们使用了 UNDIRECTED 方向，它会将每个关系在两个方向上进行投影，从而使关系数量加倍。

流模式 (Stream)

在 stream 执行模式下，算法返回每个节点的局部聚类系数。这使我们能够直接检查结果或在 Cypher 中进行后续处理，而不会产生任何副作用。例如，我们可以对结果进行排序，找出局部聚类系数最高的节点。

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

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

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

表 14. 结果
名称 (name)	localClusteringCoefficient
"Karin"	1.0
“Mark”	1.0
"Chris"	0.6666666666666666
"Will"	0.6666666666666666
“Michael”	0.3
"Alice"	0.0

从结果中可以看出，节点 'Karin' 和 'Mark' 的局部聚类系数最高。这表明他们在社交介绍方面最有效——所有认识他们的人彼此也都认识！这一点可以在示例图中得到验证。

统计模式 (Stats)

在 stats 执行模式下，算法返回包含算法结果摘要的单行数据。摘要结果包含图的平均聚类系数，即所有局部聚类系数的归一化总和。此执行模式不会产生任何副作用。通过检查 computeMillis 返回项，它对于评估算法性能很有用。在下面的示例中，我们将省略返回的时间信息。程序的完整签名可以在语法部分找到。

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

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

CALL gds.localClusteringCoefficient.stats('myGraph')
YIELD averageClusteringCoefficient, nodeCount

表 15. 结果
averageClusteringCoefficient	nodeCount
0.6055555555555555	6

结果表明，在我们的示例图中，平均每个节点约有 60% 的邻居是相互连接的。

变异模式 (Mutate)

mutate 执行模式扩展了 stats 模式，并带有一个重要的副作用：用包含该节点局部聚类系数的新节点属性更新命名图。新属性的名称使用强制配置参数 mutateProperty 指定。结果与 stats 类似，也是单行摘要，但包含一些额外的指标。当多个算法结合使用时，mutate 模式特别有用。

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

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

CALL gds.localClusteringCoefficient.mutate('myGraph', {
  mutateProperty: 'localClusteringCoefficient'
})
YIELD averageClusteringCoefficient, nodeCount

表 16. 结果
averageClusteringCoefficient	nodeCount
0.6055555555555555	6

返回的结果与 stats 示例中相同。此外，图 'myGraph' 现在拥有一个节点属性 localClusteringCoefficient，用于存储每个节点的局部聚类系数。要了解如何检查内存中图的新模式，请参阅列出图 (Listing graphs)。

写入模式 (Write)

write 执行模式扩展了 stats 模式，并带有一个重要的副作用：将每个节点的局部聚类系数作为属性写入 Neo4j 数据库。新属性的名称使用强制配置参数 writeProperty 指定。结果与 stats 类似，也是单行摘要，但包含一些额外的指标。write 模式支持将结果直接持久化到数据库中。

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

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

CALL gds.localClusteringCoefficient.write('myGraph', {
  writeProperty: 'localClusteringCoefficient'
})
YIELD averageClusteringCoefficient, nodeCount

表 17. 结果
averageClusteringCoefficient	nodeCount
0.6055555555555555	6

返回的结果与 stats 示例中相同。此外，六个节点中的每一个现在在 Neo4j 数据库中都有一个新属性 localClusteringCoefficient，其中包含该节点的局部聚类系数。

预计算计数 (Pre-computed Counts)

默认情况下，局部聚类系数算法在计算过程中会执行三角形计数。也可以通过配置局部聚类系数算法从节点属性读取三角形计数来避免重复计算。为此，我们指定 triangleCountProperty 配置参数。请注意，为了获得准确的局部聚类系数，局部聚类系数算法依赖于该属性中存储的是真实的三角形计数值。

为了说明这一点，我们以 mutate 模式使用三角形计数算法。三角形计数算法将其结果存储回 'myGraph'。也可以在创建内存图时，通过带有节点属性的图投影从 Neo4j 数据库获取该属性值。

以下操作计算三角形计数并将结果存储到内存图中：

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

以下操作将使用预计算的三角形计数以 stream 模式运行算法：

CALL gds.localClusteringCoefficient.stream('myGraph', {
  triangleCountProperty: 'triangles'
})
YIELD nodeId, localClusteringCoefficient
RETURN gds.util.asNode(nodeId).name AS name, localClusteringCoefficient
ORDER BY localClusteringCoefficient DESC, name

表 18. 结果
名称 (name)	localClusteringCoefficient
"Karin"	1.0
“Mark”	1.0
"Chris"	0.6666666666666666
"Will"	0.6666666666666666
“Michael”	0.3
"Alice"	0.0

如我们所见，结果与我们没有指定 triangleCountProperty 的 stream 示例中的结果相同。