局部聚类系数

词汇表

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

简介

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

可以看出，计算局部聚类系数需要三角形计数。为此，将利用三角形计数算法。

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

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

语法

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

每种模式下的局部聚类系数语法

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

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

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

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

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

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

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

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

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

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

在命名图上以修改模式运行局部聚类系数

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

表8. 配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`不适用`	否	GDS图中写入局部聚类系数的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个ID，可以用来更方便地跟踪算法的进度。
triangleCountProperty	字符串	`不适用`	是	包含预计算三角形计数的节点属性。

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

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

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

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

表12. 结果
名称	类型	描述
averageClusteringCoefficient	双精度浮点数	平均聚类系数。
nodeCount	整数	图中节点的数量。
nodePropertiesWritten	整数	写入 Neo4j 的属性数量。
preProcessingMillis	整数	图预处理的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算全局指标的毫秒数。
writeMillis	整数	将结果写回 Neo4j 的毫秒数。
configuration	映射	用于运行算法的配置。

示例

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

示例中使用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 后，我们现在可以将其投影到图目录中，为算法执行做准备。我们使用 Cypher 投影来完成此操作，目标是 `Person` 节点和 `KNOWS` 关系。对于关系，我们必须使用 `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	296	296	"296 字节"

请注意，尽管我们在原始 Cypher 语句中只创建了8个关系，但关系计数为16。这是因为我们使用了 `UNDIRECTED` 方向，这将把每个关系投影到每个方向，从而有效地使关系数量翻倍。

流模式

在 `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. 结果
名称	localClusteringCoefficient
"Karin"	1.0
"Mark"	1.0
"Chris"	0.6666666666666666
"Will"	0.6666666666666666
"Michael"	0.3
"Alice"	0.0

从结果中我们可以看出，节点“Karin”和“Mark”具有最高的局部聚类系数。这表明他们最擅长介绍朋友——所有认识他们的人都相互认识！这可以在示例图中验证。

统计模式

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

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

以下将在 `stats` 模式下运行算法：

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

表15. 结果
averageClusteringCoefficient	nodeCount
0.6055555555555555	6

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

修改模式

`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` 的节点属性，用于存储每个节点的局部聚类系数。要了解如何检查内存中图的新模式，请参阅列出图。

写入模式

`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` 属性，其中包含该节点的局部聚类系数。

预计算计数

默认情况下，局部聚类系数算法执行三角形计数作为其计算的一部分。通过配置局部聚类系数算法从节点属性读取三角形计数，也可以避免三角形计数计算。为此，我们指定 `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. 结果
名称	localClusteringCoefficient
"Karin"	1.0
"Mark"	1.0
"Chris"	0.6666666666666666
"Will"	0.6666666666666666
"Michael"	0.3
"Alice"	0.0

如我们所见，结果与流模式示例中未指定 `triangleCountProperty` 的情况相同。