概述
中介中心性(Betweenness Centrality)衡量节点处于其它任意两点间最短路径之中的概率。该概念由Linton C. Freeman于1977年提出,能有效地计算出在图的多个部分间起桥梁或媒介作用的点。
中介中心性的取值范围是0到1,节点的分值越大,对于网络流通性或连通性的影响力越大。
相关资料如下:
- L.C. Freeman, A Set of Measures of Centrality Based on Betweenness (1977)
- L.C. Freeman, Centrality in Social Networks Conceptual Clarification (1978)
基本概念
最短路径
在连通图中,两点间的最短路径(Shortest Path)是指经过的边数最少(非权重图)或所有边的权重和最小(权重图)的路径。
![](https://img.ultipa.cn/draw/draw_5c95ee7a59464081af24a920c65ab070.jpg?v='1643255279330')
在上面的非权重图中,红、绿两点间存在三条最短路径,其中有两条经过黄色节点,因此,黄色节点对于红绿节点对的中介概率为2 / 3 = 0.6667
。
中介中心性
在本算法中,节点的中介中心性分值计算公式为:
![](https://img.ultipa.cn/img/2023-03-07-14-12-39-bc.jpg)
其中,x
为待计算的目标节点,i
、j
为图中互异的任意两个节点(不包含x
),σ
为ij
点对最短路径的数量,σ(x)
为ij
点对经过x
的最短路径的数量,σ(x)
/σ
就是x
对于ij
点对的中介概率(i
、j
不连通时该概率为0),k
为图中节点的数量,(k-1)(k-2)/2
为ij
节对的数量。
![](https://img.ultipa.cn/draw/draw_7ee226215cd64f2f987e8bb4bf76d4b7.jpg?v='1643281463997')
计算上图中红色节点的中介中心性。图中共有5个节点,除了红色节点有(5-1)(5-2)/2 = 6
组点对,红色节点对于各节点对的中介概率分别为0、1/2、2/2、0、2/3和0,因此其中介中心性分值为(0 + 1/2 + 2/2 + 0 + 2/3 + 0) / 6 = 0.3611
。
中介中心性算法会消耗很多计算资源。在一个有V个节点的图中,建议当V>10000时通过采样进行近似计算,推荐的采样个数是节点数以10为底的对数(
log(V)
)。
每次执行算法时,只进行一次采样,每个节点的中心性分值是所有样本节点间的最短路径计算的。
特殊说明
- 孤点的中介中心性分值为0。
- 中介中心性算法忽略边的方向,按照无向边进行计算。在包含
k
个节点的无向图中,参与计算的点对数量是(k-1)(k-2)/2
。
语法
- 命令:
algo(betweenness_centrality)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
sample_size | int | -1 , -2 , [1, V] |
-1 |
是 | 采样节点数;-1 代表采样数为log(V) ,-2 代表不采样进行精确计算,一个介于 [1, V] 的数代表采样规定数目的节点 |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
order | string | asc , desc |
/ | 是 | 按中心性分值大小对结果进行排序 |
示例
示例图是一个小型社交网络,点代表user,边代表know关系:
![](https://img.ultipa.cn/draw/draw_1740726ba6764a969783089016141bbe.jpg?v='1680580132694')
文件回写
配置项 | 回写内容 |
---|---|
filename | _id ,centrality |
algo(betweenness_centrality).params().write({
file:{
filename: 'centrality'
}
})
结果:文件centrality
Billy,0
Jay,0.0666667
May,0.0666667
Mark,0.133333
Ann,0.133333
Dave,0.333333
Sue,0
属性回写
配置项 | 回写内容 | 类型 | 数据类型 |
---|---|---|---|
property | centrality |
点属性 | float |
示例:计算所有点的中介中心性,将中介中心性回写至名为 bc 的点属性
algo(betweenness_centrality).params().write({
db:{
property: 'bc'
}
})
结果:每个节点的中心性分值回写至名为bc的点属性下
直接返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其中心性 | _uuid , centrality |
algo(betweenness_centrality).params({
order: 'desc',
limit: 3
}) as bc
return bc
结果:bc
_uuid | centrality |
---|---|
2 | 0.33333299 |
4 | 0.13333300 |
3 | 0.13333300 |
流式返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其中心性 | _uuid , centrality |
algo(betweenness_centrality).params().stream() as bc
where bc.centrality == 0
return count(bc)
结果:2