概述
图中心性(Graph Centrality)用来衡量节点在其连通分量中到其它各点的最短距离的最大值。该概念与其它概念(如接近中心性、图直径等)一起可以综合判定一个点是否从真正意义上位于图的最中心。
图中心性的取值范围是 [0,1],数值越大越靠近中心。
基本概念
图中心性
图中心性的定义为某点到其连通分量中各节点的最短距离的最大值的倒数。关于最短距离的介绍请阅读《接近中心性》一章。
其中,x
为待计算的节点,y
为 x
所在连通分量中的任意一个节点(不包含 x
),d(x,y)
为 x
到 y
的最短距离。
上图中各点到红、绿节点的最短距离已经标出,可得到红、绿节点的图中性分别为 0.3333 和 0.25;如果仅计算两点的接近中心性,则红色节点为 8/(3+3+3+2+1+1+2+1)=0.5
,绿色节点为 8/(1+1+1+1+2+3+4+3)=0.5
,二值相同;在接近中心性相同时,图中心性可作为判断哪个节点更靠近中心的辅助依据。
特殊处理
孤点、不连通图
孤点不与任何其它节点相连,其图中心性为 0,孤点也不参与到任何图中心性的计算中。
一个连通分量内的节点一定不会参与其它连通分量内节点的图中心性的计算中。
自环边
图中心性计算的是节点之间的最短距离,自环边不构成最短路径,因此不参与计算。
有向边
对于有向边,图中心性算法会忽略边的方向,按照无向边进行计算。
结果和统计值
以下面包含 10 个节点的图为例,针对所有节点运行图中心性算法:
算法结果:为每个点计算图中心性,根据算法执行方式,返回 _id
、centrality
两列或 _uuid
、centrality
两列
_uuid | _id | centrality |
---|---|---|
1 | A | 0.25000000 |
2 | B | 0.20000000 |
3 | C | 0.20000000 |
4 | D | 0.20000000 |
5 | E | 0.33333334 |
6 | F | 0.33333334 |
7 | G | 0.25000000 |
8 | H | 0.20000000 |
9 | I | 0.25000000 |
10 | J | 0.0000000 |
算法统计值:无
命令和参数配置
- 命令:
algo(graph_centrality)
params()
参数配置项如下:
名称 |
类型 |
默认值 |
规范 |
描述 |
---|---|---|---|---|
ids 或 uuids | []_id 或 []_uuid |
/ | / | 待计算节点的 ID 或 UUID;忽略表示计算全部点 |
limit | int | -1 | >=-1 | 需要返回的结果条数,-1 或忽略表示返回所有结果 |
order | string | / | ASC/DESC,大小写不敏感 | 对返回结果进行排序;忽略表示不排序 |
示例:计算所有节点的图中心性,返回所有结果
algo(graph_centrality).params({
limit: -1
}) as gc
return gc
算法执行
任务回写
1. 文件回写
配置项 | 各列数据 |
---|---|
filename | _id ,centrality |
示例:计算所有点的图中心性,将算法结果回写至名为 res.csv 的文件
algo(graph_centrality).params().write({
file:{
filename: "res.csv"
}
})
2. 属性回写
配置项 | 回写内容 | 类型 | 数据类型 |
---|---|---|---|
property | centrality |
点属性 | float |
示例:计算所有点的图中心性,将图中心性回写至名为 graphC 的点属性
algo(graph_centrality).params().write({
db:{
property: "graphC"
}
})
3. 统计回写
算法无统计值。
直接返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其图中心性 | _uuid , centrality |
示例:计算所有点的图中心性,将算法结果定义为别名 results 并返回中心性最大的三个结果
algo(graph_centrality).params({
order: "desc",
limit: 3
}) as results
return results
流式返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其图中心性 | _uuid , centrality |
示例:计算所有点的图中心性,将算法结果定义为别名 results,返回中心性为 0 的结果
algo(graph_centrality).params().stream() as results
where results.centrality == 0
return results
实时统计
算法无统计值。