图中心性

概述

一个点的图中心性（Graph Centrality）是由该点到它可连通的其它各点的最短距离的最大值来衡量的。我们可综合考量这个指标与其它指标（如接近中心性、图直径等），判定一个点是否真正位于图的最中心。

图中心性的取值范围是0到1，节点的分值越大，越靠近中心。

基本概念

最短距离

两个点之间的最短距离是指它们之间最短路径的边数。具体可参看接近中心性。

图中心性

在本算法中，节点的图中心性分值等于该点与其他能够相连的各节点的最短距离最大值的倒数。计算公式为：

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

上图中，各点旁的绿色和红色文字分别是该点到绿、红两个节点的最短距离，绿、红两个节点的图中心性分别为1/4 = 0.25和1/3 = 0.3333。

考虑这两个点的接近中心性，绿色节点的分值为8/(1+1+1+1+2+3+4+3) = 0.5，红色节点的分值为8/(3+3+3+2+1+1+2+1) = 0.5。两个节点的接近中心性分值相同时，图中心性可作为辅助依据判断哪个节点更靠近中心。

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

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

特殊说明

• 孤点的图中心性分值为0。
• 图中心性算法忽略边的方向，按照无向边进行计算。

语法

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

示例

示例图如下：

文件回写

algo(graph_centrality).params().write({
  file:{ 
    filename: 'res'
  }
})

结果：文件res

J,0
I,0.25
H,0.2
F,0.333333
G,0.25
D,0.2
E,0.333333
C,0.2
A,0.25
B,0.2

属性回写

algo(graph_centrality).params().write({
  db:{ 
    property: 'gc'
  }
})

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

直接返回

algo(graph_centrality).params({
  ids: ['A', 'B', 'C'],
  order: 'asc'
}) as gc
return gc

结果：gc

流式返回

algo(graph_centrality).params().stream() as gc
where gc.centrality > 0.25
return gc

结果：gc