介数中心性

有向

无向

异构节点

异构关系

加权关系

术语表

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

简介

介数中心性是一种检测节点在图中信息流中影响程度的方法。它通常用于查找充当图中一个部分到另一个部分的桥梁的节点。

该算法计算图中所有节点对之间的最短路径。每个节点都会获得一个分数，该分数基于通过该节点的最短路径的数量。更频繁地位于其他节点之间最短路径上的节点将具有更高的介数中心性分数。

介数中心性适用于没有权重或具有正权重的图。GDS 实现基于 Brandes 的近似算法，用于无权图。对于加权图，使用多个并发 Dijkstra 算法。该实现需要 O(n + m) 空间，并在 O(n * m) 时间内运行，其中 n 是图中节点的数量，m 是关系的数量。

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

运行此算法需要足够的内存可用性。在运行此算法之前，建议您阅读内存估算.

考量因素和采样

介数中心性算法的计算可能非常占用资源。 Brandes 的近似算法为一组源节点计算单源最短路径 (SSSP)。当所有节点都被选为源节点时，该算法会产生精确的结果。但是，对于大型图，这可能导致非常长的运行时间。因此，通过仅为源节点子集计算 SSSP 来近似结果可能会有用。在 GDS 中，我们将此技术称为 *采样*，其中源节点集的大小为 *采样大小*。

在大型图上执行算法时，需要考虑两件事。

更高的并行度会导致更高的内存消耗，因为每个线程都会顺序地为源节点子集执行 SSSP。
- 在最坏的情况下，单个 SSSP 需要将整个图复制到内存中。
更高的采样大小会导致更准确的结果，但也可能导致更长的执行时间。

分别更改配置参数 concurrency 和 samplingSize 的值可以帮助管理这些问题。

采样策略

Brandes 定义了多种选择源节点的策略。GDS 实现基于随机度选择策略，该策略以与度成正比的概率选择节点。该策略背后的理念是，此类节点很可能位于图中的许多最短路径上，因此对介数中心性分数的贡献更大。

语法

本节介绍在每种执行模式下执行介数中心性算法时使用的语法。我们正在描述命名的图语法变体。要了解有关一般语法变体的更多信息，请参阅语法概述。

每个模式的介数中心性语法

在命名图上以流模式运行介数中心性。

CALL gds.betweenness.stream(
  graphName: String,
  configuration: Map
)
YIELD
  nodeId: Integer,
  score: Float

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

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有给定标签的任何节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有给定类型的任何关系都将被包含。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供的 ID，用于更轻松地跟踪算法的进度。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
samplingSize	整数	`节点计数`	是	要考虑用于计算中心性分数的源节点数。
samplingSeed	整数	`空`	是	选择起始节点的随机数生成器的种子值。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性的名称。如果未指定，则算法将以未加权的方式运行。

表 3. 结果
名称	类型	描述
nodeId	整数	节点 ID。
score	浮点数	介数中心性分数。

在命名图上以统计模式运行介数中心性。

CALL gds.betweenness.stats(
  graphName: String,
  configuration: Map
)
YIELD
  centralityDistribution: Map,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  configuration: Map

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

表 5. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有给定标签的任何节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有给定类型的任何关系都将被包含。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供的 ID，用于更轻松地跟踪算法的进度。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
samplingSize	整数	`节点计数`	是	要考虑用于计算中心性分数的源节点数。
samplingSeed	整数	`空`	是	选择起始节点的随机数生成器的种子值。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性的名称。如果未指定，则算法将以未加权的方式运行。

表 6. 结果
名称	类型	描述
centralityDistribution	映射	包含中心性值的最小值、最大值、平均值以及 p50、p75、p90、p95、p99 和 p999 百分位数的映射。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算统计信息的毫秒数。
configuration	映射	用于运行算法的配置。

在命名图上以变异模式运行介数中心性。

CALL gds.betweenness.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  centralityDistribution: Map,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  mutateMillis: Integer,
  nodePropertiesWritten: Integer,
  configuration: Map

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

表 8. 配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`n/a`	否	GDS 图中将中心性写入的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供的 ID，用于更轻松地跟踪算法的进度。
samplingSize	整数	`节点计数`	是	要考虑用于计算中心性分数的源节点数。
samplingSeed	整数	`空`	是	选择起始节点的随机数生成器的种子值。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性的名称。如果未指定，则算法将以未加权的方式运行。

表 9. 结果
名称	类型	描述
centralityDistribution	映射	包含中心性值的最小值、最大值、平均值以及 p50、p75、p90、p95、p99 和 p999 百分位数的映射。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算统计信息的毫秒数。
mutateMillis	整数	将属性添加到内存中图的毫秒数。
nodePropertiesWritten	整数	添加到内存中图的属性数。
configuration	映射	用于运行算法的配置。

在命名图上以写入模式运行介数中心性。

CALL gds.betweenness.write(
  graphName: String,
  configuration: Map
)
YIELD
  centralityDistribution: Map,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  writeMillis: Integer,
  nodePropertiesWritten: Integer,
  configuration: Map

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

表 11. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有给定标签的任何节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有给定类型的任何关系都将被包含。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供的 ID，用于更轻松地跟踪算法的进度。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeProperty	字符串	`n/a`	否	Neo4j 数据库中将中心性写入的节点属性。
samplingSize	整数	`节点计数`	是	要考虑用于计算中心性分数的源节点数。
samplingSeed	整数	`空`	是	选择起始节点的随机数生成器的种子值。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性的名称。如果未指定，则算法将以未加权的方式运行。

表 12. 结果
名称	类型	描述
centralityDistribution	映射	包含中心性值的最小值、最大值、平均值以及 p50、p75、p90、p95、p99 和 p999 百分位数的映射。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算统计信息的毫秒数。
writeMillis	整数	将结果数据写回的毫秒数。
nodePropertiesWritten	整数	写入 Neo4j 的属性数。
configuration	映射	用于运行算法的配置。

示例

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

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

在本节中，我们将展示在具体图上运行介数中心性算法的示例。目的是说明结果的样子，并提供如何在实际设置中使用该算法的指南。我们将使用一小部分节点以特定模式连接的社交网络图来进行此操作。示例图如下所示

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

CREATE
  (alice:User {name: 'Alice'}),
  (bob:User {name: 'Bob'}),
  (carol:User {name: 'Carol'}),
  (dan:User {name: 'Dan'}),
  (eve:User {name: 'Eve'}),
  (frank:User {name: 'Frank'}),
  (gale:User {name: 'Gale'}),

  (alice)-[:FOLLOWS {weight: 1.0}]->(carol),
  (bob)-[:FOLLOWS {weight: 1.0}]->(carol),
  (carol)-[:FOLLOWS {weight: 1.0}]->(dan),
  (carol)-[:FOLLOWS {weight: 1.3}]->(eve),
  (dan)-[:FOLLOWS {weight: 1.0}]->(frank),
  (eve)-[:FOLLOWS {weight: 0.5}]->(frank),
  (frank)-[:FOLLOWS {weight: 1.0}]->(gale);

有了 Neo4j 中的图，我们现在可以将其投影到图目录中，为算法执行做好准备。我们使用针对 User 节点和 FOLLOWS 关系的 Cypher 投影来实现此操作。

以下语句将使用 Cypher 投影创建图，并将其存储在图目录中，名称为 'myGraph'。

MATCH (source:User)-[r:FOLLOWS]->(target:User)
RETURN gds.graph.project(
  'myGraph',
  source,
  target,
  { relationshipProperties: r { .weight } }
)

在以下示例中，我们将演示如何在该图上使用介数中心性算法。

内存估计

首先，我们将使用 estimate 过程来估计运行算法的成本。这可以使用任何执行模式来完成。在此示例中，我们将使用 write 模式。估计算法有助于了解在图上运行算法将产生的内存影响。当你稍后实际上以某种执行模式运行算法时，系统将执行估计。如果估计表明执行有很高的概率超过其内存限制，则会禁止执行。要详细了解这方面的信息，请参阅自动估计和执行阻止。

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

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

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

表 13. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
7	7	2944	2944	"2944 字节"

正如在注意事项和采样中所讨论的，我们可以使用 concurrency 配置参数来配置内存需求。

以下将估计以单线程运行算法所需的内存。

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

表 14. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
7	7	856	856	"856 字节"

在这里，我们可以注意到，估计的内存需求低于使用默认并发设置运行时的需求。类似地，使用更高的值将增加估计的内存需求。

流

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

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

以下将在 stream 模式下运行算法

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

表 15. 结果
name	score
"Alice"	0.0
"Bob"	0.0
"Carol"	8.0
"Dan"	3.0
"Eve"	3.0
"Frank"	5.0
"Gale"	0.0

我们注意到，'Carol' 节点具有最高的分数，其次是 'Frank' 节点。研究示例图，我们可以看到这些节点位于图中的瓶颈位置。'Carol' 节点将 'Alice' 和 'Bob' 节点连接到所有其他节点，这会增加其分数。特别是，从 'Alice' 或 'Bob' 到任何其他可达节点的最短路径都经过 'Carol'。类似地，所有通向 'Gale' 节点并经过 'Frank' 节点。由于 'Gale' 从所有其他节点可达，这导致 'Frank' 的分数很高。

相反，没有最短路径经过 'Alice'、'Bob' 或 'Gale' 中的任何一个节点，这导致它们的介数中心性分数为零。

统计信息

在 stats 执行模式下，算法会返回包含算法结果摘要的一行。特别是，介数中心性会返回所有中心性分数的最小值、最大值和总和。此执行模式不会产生任何副作用。通过检查 computeMillis 返回项，它可以用于评估算法性能。在以下示例中，我们将省略返回时间。过程的完整签名可以在语法部分中找到。

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

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

CALL gds.betweenness.stats('myGraph')
YIELD centralityDistribution
RETURN centralityDistribution.min AS minimumScore, centralityDistribution.mean AS meanScore

表 16. 结果
minimumScore	meanScore
0.0	2.714292253766741

将此与我们在流示例中看到的結果相比，我们可以从表格中找到最小值和最大值。值得注意的是，除非图具有包含有向循环的特定形状，否则最小分数几乎总是为零。

变异

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

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

以下将在 mutate 模式下运行算法

CALL gds.betweenness.mutate('myGraph', { mutateProperty: 'betweenness' })
YIELD centralityDistribution, nodePropertiesWritten
RETURN centralityDistribution.min AS minimumScore, centralityDistribution.mean AS meanScore, nodePropertiesWritten

表 17. 结果
minimumScore	meanScore	nodePropertiesWritten
0.0	2.7142922538	7

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

写入

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

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

以下将在 write 模式下运行算法

CALL gds.betweenness.write('myGraph', { writeProperty: 'betweenness' })
YIELD centralityDistribution, nodePropertiesWritten
RETURN centralityDistribution.min AS minimumScore, centralityDistribution.mean AS meanScore, nodePropertiesWritten

表 18. 结果
minimumScore	meanScore	nodePropertiesWritten
0.0	2.714292253766741	7

返回的结果与 stats 示例中的结果相同。此外，七个节点中的每一个现在在 Neo4j 数据库中都具有一个新的属性 betweenness，其中包含该节点的介数中心性分数。

采样

介数中心性计算可能非常占用资源。为了解决这个问题，可以使用采样技术来近似结果。配置参数 samplingSize 和 samplingSeed 用于控制采样。我们通过使用采样大小为 2 来近似介数中心性，在示例图上说明这一点。种子值是一个任意整数，使用相同的种子值将在不同运行过程中产生相同的结果。

以下将在 stream 模式下使用采样大小为 2 运行算法

CALL gds.betweenness.stream('myGraph', {samplingSize: 2, samplingSeed: 4})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY name ASC

表 19. 结果
name	score
"Alice"	0.0
"Bob"	0.0
"Carol"	4.0
"Dan"	2.0
"Eve"	2.0
"Frank"	2.0
"Gale"	0.0

在这里我们可以看到，'Carol' 节点具有最高分数，其次是 'Dan'、'Eve' 和 'Frank' 节点之间的三方并列。我们只从两个节点中进行采样，其中节点被选中进行采样的概率与其出度成正比。'Carol' 节点具有最大度数，最有可能被选中。'Gale' 节点具有零出度，不太可能被选中。其他节点被选中的概率相同。

对于我们选择的种子值为 0 的采样，我们似乎选择了 'Alice' 和 'Bob' 节点中的任何一个，以及 'Carol' 节点。我们可以看到，因为 'Alice' 和 'Bob' 中的任何一个都会在 'Carol' 节点的分数上加 4，而 'Alice'、'Bob' 和 'Carol' 中的每一个都会在 'Dan'、'Eve' 和 'Frank' 中的每一个上加 1。

为了提高近似值的准确性，可以增加采样大小。实际上，将 samplingSize 设置为图的节点数（在本例中为 7）将产生精确的结果。

无向

介数中心性也可以在无向图上运行。为了说明这一点，我们将使用 UNDIRECTED 方向投影我们的示例图。

以下语句将使用 Cypher 投影投影图，并将其存储在图目录中，名为 'myUndirectedGraph'。

MATCH (source:User)-[r:FOLLOWS]->(target:User)
RETURN gds.graph.project(
  'myUndirectedGraph',
  source,
  target,
  { relationshipProperties: r { .cost } },
  { undirectedRelationshipTypes: ['*'] }
)

现在，我们可以对无向图运行介数中心性。算法会自动识别出图是无向的。

与有向图相比，在无向图上运行算法的计算量大约是其两倍。

以下将在 stream 模式下在无向图上运行算法

CALL gds.betweenness.stream('myUndirectedGraph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY name ASC

表 20. 结果
name	score
"Alice"	0.0
"Bob"	0.0
"Carol"	9.5
"Dan"	3.0
"Eve"	3.0
"Frank"	5.5
"Gale"	0.0

由于图中存在更多最短路径，并且这些路径更有可能穿过中心节点，因此中心节点现在的分数略高。'Dan' 和 'Eve' 节点的中心性分数与有向情况下的分数相同。

加权

以下将在 stream 模式下使用权重运行算法

CALL gds.betweenness.stream('myGraph', {relationshipWeightProperty: 'weight'})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY name ASC

表 21. 结果
name	score
"Alice"	0.0
"Bob"	0.0
"Carol"	8.0
"Dan"	0.0
"Eve"	6.0
"Frank"	5.0
"Gale"	0.0