概述
一个点的图中心性(Graph Centrality)是由该点到它可连通的其它各点的最短距离的最大值来衡量的。我们可综合考量这个指标与其它指标(如接近中心性、图直径等),判定一个点是否真正位于图的最中心。
图中心性的取值范围是0到1,节点的分值越大,越靠近中心。
基本概念
最短距离
两个点之间的最短距离是指它们之间最短路径的边数。具体可参看接近中心性。
图中心性
在本算法中,节点的图中心性分值等于该点与其他能够相连的各节点的最短距离最大值的倒数。计算公式为:
![](https://img.ultipa.cn/img/2023-03-07-14-21-05-gc.jpg)
其中,x
为待计算的目标节点,y
为通过边与x
相连的任意一个节点(不包含x
),d(x,y)
为x
到y
的最短距离。
![](https://img.ultipa.cn/draw/draw_26771c0b3279432fb74d7ceb6502c9c5.jpg?v='1643192998970')
上图中,各点旁的绿色和红色文字分别是该点到绿、红两个节点的最短距离,绿、红两个节点的图中心性分别为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
。两个节点的接近中心性分值相同时,图中心性可作为辅助依据判断哪个节点更靠近中心。
特殊说明
- 孤点的图中心性分值为0。
- 图中心性算法忽略边的方向,按照无向边进行计算。
语法
- 命令:
algo(graph_centrality)
- 参数:
名称 | 类型 | 规范 | 默认 |
可选 |
描述 |
---|---|---|---|---|---|
ids / uuids | []_id / []_uuid |
/ | / | 是 | 待计算节点的ID/UUID,忽略则计算全部点 |
direction | string | in , out |
/ | 是 | 最短路径中所有边的方向,in 是入方向,out 是出方向 |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
order | string | asc , desc |
/ | 是 | 按中心性分值大小对结果进行排序 |
示例
示例图如下:
![](https://img.ultipa.cn/draw/draw_ca1cdc0e7a2e41869b2ffb79e920cd86.jpg?v='1680579972910')
文件回写
配置项 | 回写内容 |
---|---|
filename | _id ,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
属性回写
配置项 | 回写内容 | 回写至 | 数据类型 |
---|---|---|---|
property | centrality |
点属性 | float |
algo(graph_centrality).params().write({
db:{
property: 'gc'
}
})
结果:每个节点的中心性分值回写至名为gc的点属性下
直接返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其中心性 | _uuid , centrality |
algo(graph_centrality).params({
ids: ['A', 'B', 'C'],
order: 'asc'
}) as gc
return gc
结果:gc
_uuid | centrality |
---|---|
2 | 0.2 |
3 | 0.2 |
1 | 0.25 |
流式返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其中心性 | _uuid , centrality |
algo(graph_centrality).params().stream() as gc
where gc.centrality > 0.25
return gc
结果:gc
_uuid | centrality |
---|---|
6 | 0.333333 |
5 | 0.333333 |