接近中心度

有向

无向

异构节点

异构关系

加权关系

词汇表

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

简介

接近中心度是一种检测能够在图中高效传播信息的节点的方法。

节点的接近中心度衡量其到所有其他节点的平均距离（逆距离）。接近中心度得分高的节点与所有其他节点的距离最短。

对于每个节点 u，接近中心度算法计算其到所有其他节点的距离之和，基于计算所有节点对之间的最短路径。然后将所得的总和取倒数，以确定该节点的接近中心度得分。

节点 u 的**原始接近中心度**使用以下公式计算

原始接近中心度(u) = 1 / 从 u 到所有其他节点的距离之和

更常见的是将此得分标准化，使其表示最短路径的平均长度，而不是它们的总和。此调整允许比较不同大小的图中节点的接近中心度

节点 u 的**标准化接近中心度**公式如下

标准化接近中心度(u) = (节点数 - 1) / 从 u 到所有其他节点的距离之和

Wasserman 和 Faust 提出了一种改进的公式来处理未连接的图。假设 n 是从 u 可到达的节点数（包括自身），则对于给定节点 u，它们的校正公式如下

Wasserman-Faust 标准化接近中心度(u) = (n-1)^2/ 节点数 - 1) * 从 u 到所有其他节点的距离之和

请注意，在有向图的情况下，接近中心度的定义有所不同。也就是说，与其考虑从 u 到每个其他节点的距离，我们改为对从每个其他节点到 u 的距离进行求和和平均。

用例 - 何时使用接近中心度算法

接近中心性用于研究组织网络，其中接近中心性高的个人处于有利地位，可以控制和获取组织内的重要信息和资源。其中一项研究是 Valdis E. Krebs 的 "恐怖主义细胞网络映射"。
接近中心性可以解释为信息通过电信或包裹递送网络流动时估计的到达时间，其中信息通过最短路径流向预定义的目标。它也可以用于信息同时通过所有最短路径传播的网络，例如感染通过社交网络传播。在 Stephen P. Borgatti 的 "中心性和网络流" 中可以找到更多详细信息。
接近中心性已被用于根据基于图的关键短语提取过程来估计文档中单词的重要性。Florian Boudin 在 "基于图的关键短语提取的中心性度量比较" 中描述了此过程。

约束 - 何时不使用接近中心性算法

在学术上，接近中心性最适用于连通图。如果我们在非连通图上使用原始公式，则最终可能会在两个不同连通分量的节点之间得到无限距离。这意味着当我们对来自该节点的所有距离求和时，最终会得到无限的接近中心性得分。

在实践中，使用了原始公式的变体，这样我们就不会遇到这些问题。

语法

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

每种模式的接近中心性语法

在命名图上以流模式运行接近中心性。

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

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

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供的 ID，以便更容易跟踪算法的进度。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
useWassermanFaust	布尔值	`假`	是	使用改进的 Wasserman-Faust 公式进行接近性计算。

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

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

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

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

表 5. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供的 ID，以便更容易跟踪算法的进度。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
useWassermanFaust	布尔值	`假`	是	使用改进的 Wasserman-Faust 公式进行接近性计算。

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

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

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

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

表 8. 配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`n/a`	否	GDS 图中写入中心性的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供的 ID，以便更容易跟踪算法的进度。
useWassermanFaust	布尔值	`假`	是	使用改进的 Wasserman-Faust 公式进行接近性计算。

表 9. 结果
名称	类型	描述
nodePropertiesWritten	整数	添加到内存图中的属性数量。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算统计信息的毫秒数。
mutateMillis	整数	变异 GDS 图的毫秒数。
centralityDistribution	映射	包含中心值最小值、最大值、平均值以及第 50、75、90、95、99 和 999 百分位数的映射。
configuration	映射	用于运行算法的配置。

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

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

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

表 11. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供的 ID，以便更容易跟踪算法的进度。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeProperty	字符串	`n/a`	否	Neo4j 数据库中写入中心性的节点属性。
useWassermanFaust	布尔值	`假`	是	使用改进的 Wasserman-Faust 公式进行接近性计算。

表 12. 结果
名称	类型	描述
nodePropertiesWritten	整数	写入 Neo4j 的属性数量。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算统计信息的毫秒数。
writeMillis	整数	变异 GDS 图的毫秒数。
centralityDistribution	映射	包含中心值最小值、最大值、平均值以及第 50、75、90、95、99 和 999 百分位数的映射。
configuration	映射	用于运行算法的配置。

示例

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

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

在本节中，我们将展示在具体图上运行接近中心性算法的示例。目的是说明结果是什么样的，并提供有关如何在实际环境中使用该算法的指南。我们将在少量节点以特定模式连接的小样本图上执行此操作。示例图如下所示

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

CREATE (a:Node {id:"A"}),
       (b:Node {id:"B"}),
       (c:Node {id:"C"}),
       (d:Node {id:"D"}),
       (e:Node {id:"E"}),
       (a)-[:LINK]->(b),
       (b)-[:LINK]->(a),
       (b)-[:LINK]->(c),
       (c)-[:LINK]->(b),
       (c)-[:LINK]->(d),
       (d)-[:LINK]->(c),
       (d)-[:LINK]->(e),
       (e)-[:LINK]->(d);

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

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

MATCH (source:Node)-[r:LINK]->(target:Node)
RETURN gds.graph.project(
  'myGraph',
  source,
  target
)

在以下示例中，我们将演示在此图上使用接近中心性算法。

流

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

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

以下将以 stream 模式运行算法

CALL gds.closeness.stream('myGraph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).id AS id, score
ORDER BY score DESC

表 13. 结果
id	score
"C"	0.6666666666666666
"B"	0.5714285714285714
"D"	0.5714285714285714
"A"	0.4
"E"	0.4

C 是此图中连接性最好的节点，尽管 B 和 D 也不差。A 和 E 与许多其他节点没有紧密联系，因此它们的得分较低。任何与所有其他节点直接连接的节点的分数都将为 1。

统计

在 stats 执行模式下，算法返回包含算法结果摘要的单行。此执行模式没有任何副作用。通过检查 computeMillis 返回项，它可用于评估算法性能。在下面的示例中，我们将省略返回时间。可以在语法部分中找到过程的完整签名。

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

以下将以 stats 模式运行算法

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

表 14. 结果
minimumScore	meanScore
0.399999618530273	0.521904373168945

变异

mutate 执行模式通过一个重要的副作用扩展了 stats 模式：使用包含该节点中心性的新节点属性更新命名图。新属性的名称使用必填配置参数 mutateProperty 指定。结果是与 stats 类似的单个摘要行，但包含一些其他指标。当多个算法结合使用时，mutate 模式特别有用。

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

以下将以 mutate 模式运行算法

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

表 15. 结果
minimumScore	meanScore	nodePropertiesWritten
0.399999618530273	0.521904373168945	5

写入

write 执行模式通过一个重要的副作用扩展了 stats 模式：将每个节点的中心性作为属性写入 Neo4j 数据库。新属性的名称使用必填配置参数 writeProperty 指定。结果是与 stats 类似的单个摘要行，但包含一些其他指标。write 模式能够将结果直接持久化到数据库中。

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

以下将以 write 模式运行算法

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

表 16. 结果
minimumScore	meanScore	nodePropertiesWritten
0.399999618530273	0.521904373168945	5