✓ 文件回写 ✓ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值

概述

一个点的接近中心性（Closeness Centrality）是由该点到它可连通的其它各点的最短距离的平均值来衡量的。一个点与其他所有点相距越近，这个点的中心性就越高。接近中心性算法广泛应用于关键社交节点发现、功能性场所选址等场景。

接近中心性算法更适用于连通图。对于非连通图，推荐使用它的变体——调和中心性。

接近中心性的取值范围是 0 到 1，节点的分值越大，距离其他节点越近。

接近中心性的原始概念是由 Alex Bavelas 于 1950 年提出的：

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

基本概念

最短距离

两个点之间的最短距离是指它们之间最短路径的边数。最短路径是按照 BFS 的原则进行寻找的，如果将一个点看作起点，另一个点是该点的第 K 步邻居，它们之间的最短距离就是 K。关于 BFS 和 K 邻的详细介绍，请阅读全图 K 邻。

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

将上面的无向图修改为有向图后，再次考察红、绿两点之间的最短距离。如果考虑边的方向。从红色节点到绿色节点入方向最短距离为 3，出方向最短距离为 4。

接近中心性

在本算法中，节点的接近中心性分值等于该点与其他能够相连的各节点的最短距离算数平均值（Arithmetic Mean）的倒数。计算公式为：

其中，x 为待计算的目标节点，y 为通过边与 x 相连的任意一个节点（不包含 x），k-1 为 y 的个数，d(x,y) 为 x 到 y 的最短距离。

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

接近中心性算法会消耗很多计算资源。在一个有 V 个节点的图中，建议当 V > 10000 时通过采样进行近似计算，推荐的采样个数是节点数以 10 为底的对数（log(V)）。

每次执行算法时，只进行一次采样，每个节点的中心性分值是基于该节点到所有样本节点的最短距离计算的。

特殊说明

• 孤点的接近中心性分值为 0。
• 计算某点的接近中心性时，会排除那些不可连通的节点，比如孤点、其他连通分量内的点或是虽然属于同一连通分量但在规定的方向上不可达的节点等。

语法

• 命令：algo(closeness_centrality)
• 参数：

示例

示例图如下：

文件回写

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

结果：文件 centrality

LA,0.583333
LB,0.636364
LC,0.5
LD,0.388889
LE,0.388889
LF,0.368421
LG,0.538462
LH,0.368421

属性回写

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

结果：每个节点的中心性分值回写至名为 cc 的点属性下

直接返回

algo(closeness_centrality).params({
  direction: 'out',
  order: 'desc',
  limit: 3
}) as cc
return cc

结果：cc

流式返回

algo(closeness_centrality).params({
  direction: 'in'
}).stream() as cc
where cc.centrality == 0
return cc

结果：cc