接近中心性

有向

无向

异构节点

异构关系

加权关系

词汇表

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

简介

接近中心性是一种检测能够非常有效地通过图传播信息的节点的方法。

一个节点的接近中心性衡量了它到所有其他节点的平均远度（距离的倒数）。接近分数高的节点到所有其他节点的距离最短。

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

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

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

更常见的是对这个分数进行归一化，使其代表最短路径的平均长度而不是它们的总和。这种调整允许比较不同大小图的节点的接近中心性。

节点 u 的归一化接近中心性公式如下

归一化接近中心性(u) = (节点数 - 1) / sum(从 u 到所有其他节点的距离)

Wasserman 和 Faust 提出了一种改进的公式来处理非连通图。假设 n 是从 u 可达的节点数（包括 u 本身），他们为给定节点 u 修正后的公式如下：

Wasserman-Faust 归一化接近中心性(u) = (n-1)^2 / (节点数 - 1) * sum(从 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	字符串	`不适用`	否	目录中存储的图的名称。
configuration	映射	`{}`	是	算法特定和/或图过滤的配置。

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

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

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

表 6. 结果
名称	类型	描述
centralityDistribution	映射	包含 min, max, mean 以及 p50, p75, p90, p95, p99 和 p999 百分位中心性值的映射。
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	字符串	`不适用`	否	目录中存储的图的名称。
configuration	映射	`{}`	是	算法特定和/或图过滤的配置。

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

表 9. 结果
名称	类型	描述
nodePropertiesWritten	整数	添加到内存图的属性数量。
preProcessingMillis	整数	图预处理的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算统计数据的毫秒数。
mutateMillis	整数	变异 GDS 图的毫秒数。
centralityDistribution	映射	包含 min, max, mean 以及 p50, p75, p90, p95, p99 和 p999 百分位中心性值的映射。
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	字符串	`不适用`	否	目录中存储的图的名称。
configuration	映射	`{}`	是	算法特定和/或图过滤的配置。

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

表 12. 结果
名称	类型	描述
nodePropertiesWritten	整数	写入 Neo4j 的属性数量。
preProcessingMillis	整数	图预处理的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算统计数据的毫秒数。
writeMillis	整数	变异 GDS 图的毫秒数。
centralityDistribution	映射	包含 min, max, mean 以及 p50, p75, p90, p95, p99 和 p999 百分位中心性值的映射。
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