中介中心性 (Betweenness Centrality)

术语表

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

简介

中介中心性（Betweenness Centrality）是一种用于检测节点在图中对信息流的影响力的方法。它常用于发现那些在图的不同部分之间起到桥梁作用的节点。

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

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

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

运行此算法需要足够的可用内存。在运行之前，建议您阅读内存估计 (Memory Estimation)。

考量与采样

中介中心性算法的计算可能非常消耗资源。Brandes 的近似算法为一组源节点计算单源最短路径 (SSSP)。当选择所有节点作为源节点时，算法会产生精确结果。然而，对于大型图，这可能导致极长的运行时间。因此，通过仅计算一部分节点的 SSSP 来近似结果会很有用。在 GDS 中，我们将此技术称为采样 (sampling)，其中源节点集的规模即为采样大小 (sampling size)。

在大型图上执行算法时，有两点需要考虑：

更高的并行度会导致更高的内存消耗，因为每个线程会依次为一部分源节点执行 SSSP。
- 在最坏的情况下，单个 SSSP 需要在内存中复制整个图。
更高的采样大小会带来更准确的结果，但也可能导致执行时间大幅增加。

调整配置参数 concurrency 和 samplingSize 的值，可以帮助管理这些考量因素。

采样策略

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

语法

本节涵盖在每种执行模式下运行中介中心性算法所需的语法。此处描述的是命名图变体语法。要了解有关通用语法变体的更多信息，请参阅语法概述。

各模式下的中介中心性语法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

示例

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

这些示例将 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)

在 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)

在 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)

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 的节点属性，存储每个节点的中介中心性得分。要了解如何检查内存中图的新模式，请参阅列出图 (Listing graphs)。

写入模式 (Write)

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，包含该节点的中介中心性得分。

采样 (Sampling)

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

以下语句将以采样大小为 2 的 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. 结果
名称 (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)

中介中心性也可以在无向图上运行。为了说明这一点，我们将使用 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”节点保留了与有向情况相同的中心性得分。

加权 (Weighted)

以下语句将使用权重以 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