概述

接近中心性（Closeness Centrality）用来衡量节点在其连通分量中到其它各点的最短距离的平均值。该概念可以帮助选出连通分量内距离各点最近的点，因而被广泛用于关键社交节点发现、功能性场所选址等应用场景。

接近中心性的取值范围是 [0,1]，数值越大越靠近中心。

接近中心性在实际应用中有着多种定义，其原始概念是由 Alex Bavelas 于 1950 年提出的，相关资料如下：

• A. Bavelas, Communication patterns in task-oriented groups (1950)

基本概念

最短距离

最短距离是指两个点之间的最短路径的边数。最短路径按照 BFS 原则进行搜索，如果将一个点看作起点，将另一个点看作起点的某个 K 邻，此时的 K 值即为起点到 K 邻的最短距离。关于 BFS 和 K 邻的介绍请阅读《全图 K 邻》一章。

考察以上无向图中红、绿两点之间的最短距离。由于是无向图，无论是以红色节点为起点，还是以绿色节点为起点，两点均为对方的 2 步邻居，即两点的最短距离为 2。

将前面的无向图修改为有向图后再次考察红、绿两点之间的最短距离，此时注意路径中边的方向。从红色节点到绿色节点的出方向最短距离为 4，入方向最短距离为 3。

接近中心性

本算法所计算的接近中心性是从原始概念引申而来的，具体定义为某点到能与其相连的各节点的最短距离的平均值的倒数：

其中，x 为待计算的节点，y 为 x 所能达到的任意一个节点（沿出边或入边，或忽略边的方向；不包含 x），d(x, y) 为 x 到 y 的最短距离，k-1 为 y 的个数。

计算上图中红色节点的入方向接近中心性。入方向上可连通蓝、黄、紫三个节点，故接近中心性为 3 / (2 + 1 + 2) = 0.6。注意，入边不可达的绿色、灰色节点不参与计算。

由于需要计算全图从某个点出发的所有最短路径，接近中心性算法会消耗较多的计算资源。在进行接近中心性的计算时，可对点的数量大于 10,000 的图集进行采样计算，建议采样个数为以 10 为底的对数 log(点数量)；可通过配置项决定是否采样。

特殊处理

孤点、不连通图

孤点不与任何其它节点相连，其接近中心性为 0，孤点也不会参与到任何接近中心性的计算中。

一个连通分量内的节点一定不会参与其它连通分量内节点的接近中心性的计算中。对于不连通图，建议使用调和中心性算法。

自环边

接近中心性计算的是节点之间的最短距离，自环边不构成最短路径，因此不参与计算。

有向边

在不规定边的方向时计算接近中心性，边的方向将被忽略，此时起点所在连通分量中的所有节点都参与计算。

结果和统计值

以下面包含 8 个节点的图为例，针对所有节点运行接近中心性算法：

算法结果：为每个点计算接近中心性，根据算法执行方式，返回 _id、centrality 两列或 _uuid、centrality 两列

算法统计值：无

命令和参数配置

• 命令：algo(closeness_centrality)
• params() 参数配置项如下：

示例：计算点 UUID = 1,2,3,4 的接近中心性

algo(closeness_centrality).params({ 
  uuids: [1,2,3,4]
}).stream() as centrality
return centrality

示例：采样计算全图点的出方向接近中心性，返回 5 条结果

algo(closeness_centrality).params({ 
  limit: 5, 
  direction: "out",
  sample_size: -1 
}) as out
return out

算法执行

任务回写

1. 文件回写

示例：计算所有点的接近中心性，将算法结果回写至名为 centrality 的文件

algo(closeness_centrality).params().write({
  file:{ 
    filename: "centrality"
  }
})

2. 属性回写

示例：计算所有点的接近中心性，将接近中心性回写至名为 cc 的点属性

algo(closeness_centrality).params().write({
  db:{ 
    property: "cc"
  }
})

3. 统计回写

算法无统计值。

直接返回

示例：计算所有点的接近中心性，将算法结果定义为别名 results 并返回中心性最大的三个结果

algo(closeness_centrality).params({
  order: "desc",
  limit: 3
}) as results
return results

流式返回

示例：计算所有点的接近中心性，将算法结果定义为别名 results，返回中心性为 0 的结果

algo(closeness_centrality).params().stream() as results
where results.centrality == 0
return results

实时统计

算法无统计值。