介数中心性

有向

无向

异构节点

异构关系

加权关系

术语表

有向: 有向特性。该算法在有向图上定义良好。
有向: 有向特性。该算法忽略图的方向。
有向: 有向特性。该算法不在有向图上运行。
无向: 无向特性。该算法在无向图上定义良好。
无向: 无向特性。该算法忽略图的无向性。
异构节点: 异构节点完全支持。该算法能够区分不同类型的节点。
异构节点: 异构节点允许。该算法对所有选定的节点一视同仁，无论其标签如何。
异构关系: 异构关系完全支持。该算法能够区分不同类型的关系。
异构关系: 异构关系允许。该算法对所有选定的关系一视同仁，无论其类型如何。
加权关系: 加权特性。该算法支持将关系属性用作权重，通过 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	字符串	`不适用`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定和/或图筛选的配置。

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

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

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

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

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

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

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

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

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

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

表 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. 结果
名称	分数
"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 用于控制采样。我们将在示例图上通过采样大小为二来近似介数中心性。种子值是任意整数，使用相同的值将在该过程的不同运行之间产生相同的结果。

以下将在 stream 模式下运行算法，采样大小为二

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. 结果
名称	分数
"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' 节点的得分增加四分，而 'Alice'、'Bob' 和 'Carol' 中的每一个都会给 'Dan'、'Eve' 和 'Frank' 的每个节点增加一分。

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

无向

介数中心性也可以在无向图上运行。为了说明这一点，我们将使用 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. 结果
名称	分数
"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. 结果
名称	分数
"Alice"	0.0
"Bob"	0.0
"Carol"	8.0
"Dan"	0.0
"Eve"	6.0
"Frank"	5.0
"Gale"	0.0