接近中心性 (Closeness Centrality)

术语表

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

简介

紧密度中心性是一种用于检测图中能够非常高效地传播信息的节点的方法。

节点的紧密度中心性衡量其到所有其他节点的平均远近程度（距离的倒数）。具有高紧密度分数的节点，到所有其他节点的最短路径距离之和最小。

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

节点 u 的原始紧密度中心性 (raw closeness centrality) 使用以下公式计算：

原始紧密度中心性(u) = 1 / sum(节点 u 到所有其他节点的距离)

更常见做法是对该分数进行归一化，使其代表最短路径的平均长度，而不是其总和。这种调整允许对不同规模图中的节点进行紧密度中心性比较。

归一化紧密度中心性 (normalized closeness centrality) 的计算公式如下：

归一化紧密度中心性(u) = (节点总数 - 1) / sum(节点 u 到所有其他节点的距离)

Wasserman 和 Faust 提出了一种改进公式，用于处理非连通图。假设 n 是从 u 可达的节点数（包括其自身），则针对给定节点 u 的修正公式如下：

Wasserman-Faust 归一化紧密度中心性(u) = (n-1)^2 / (节点总数 - 1) * sum(节点 u 到所有其他节点的距离)

请注意，对于有向图，紧密度中心性的定义会有所不同。即，我们不是考虑从 u 到其他所有节点的距离，而是求从其他所有节点到 u 的距离之和并取平均值。

用例 - 何时使用紧密度中心性算法

紧密度中心性常用于研究组织网络，其中具有高紧密度中心性的个人处于有利位置，能够控制和获取组织内的重要信息和资源。Valdis E. Krebs 的论文《绘制恐怖分子网络图》(Mapping Networks of Terrorist Cells)便是此类研究之一。
在电信或包裹递送网络中，当信息通过最短路径流向预定目标时，紧密度中心性可被解释为信息到达的估计时间。它也适用于信息同时通过所有最短路径传播的网络，例如在社交网络中传播的传染病。更多详细信息，请参见 Stephen P. Borgatti 的论文《中心性与网络流》(Centrality and network flow)。
紧密度中心性已被用于评估文档中词语的重要性，该方法基于一种图论的关键短语提取过程。Florian Boudin 在《基于图的关键短语提取的中心性度量比较》(A Comparison of Centrality Measures for Graph-Based Keyphrase Extraction)一文中描述了此过程。

限制 - 何时不使用紧密度中心性算法

从学术角度来看，紧密度中心性在连通图中效果最好。如果我们在非连通图上使用原始公式，可能会导致两个分属不同连通分量的节点之间的距离变为无穷大。这意味着在对该节点的所有距离求和时，最终会得到无限大的紧密度中心性分数。

在实际应用中，通常会使用原始公式的变体，以避免这些问题。

语法

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

各模式下的紧密度中心性语法

在命名图上以流模式 (stream mode) 运行紧密度中心性。

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

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

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

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

在命名图上以统计模式 (stats mode) 运行紧密度中心性。

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

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

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

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

在命名图上以变异模式 (mutate mode) 运行紧密度中心性。

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

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

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

在命名图上以写入模式 (write mode) 运行紧密度中心性。

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

表 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	Map	包含中心性分数的最小值、最大值、平均值以及 p50、p75、p90、p95、p99 和 p999 百分位值的映射。
配置	Map	运行算法所使用的配置。

示例

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

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

在以下示例中，我们将演示如何在此时图上使用紧密度中心性算法。

内存估计

首先，我们将使用 estimate 过程来估算运行该算法的成本。这可以在任何执行模式下完成。在本示例中，我们将使用 stream 模式。估算算法有助于了解在图上运行算法对内存的影响。当您稍后在其中一种执行模式下实际运行算法时，系统将执行一次估算。如果估算显示执行超出内存限制的可能性非常高，则禁止执行。要了解更多信息，请参阅自动估算与执行阻塞。

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

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

CALL gds.closeness.stream.estimate('myGraph',{})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 13. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
5	8	1504	1504	"1504 字节"

流 (Stream)

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

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

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

统计 (Stats)

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

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

以下语句将以 stats 模式运行该算法：

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

表 15. 结果
minimumScore	meanScore
0.399999618530273	0.521904373168945

变异 (Mutate)

`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

表 16. 结果
minimumScore	meanScore	nodePropertiesWritten
0.399999618530273	0.521904373168945	5

写入 (Write)

`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

表 17. 结果
minimumScore	meanScore	nodePropertiesWritten
0.399999618530273	0.521904373168945	5