概述
中介中心性(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)
基本概念
中介概率
本算法中的中介是指一个点通过最短路径到达另一个点时途经的各点。
上图中红、绿节点间的最短路径经过了蓝、黄两个节点,蓝、黄节点均为其中介点。
中介概率是指某点在某个节点对的所有最短路径中出现的概率。
上图中红、绿节点对之间有三条步数为 3 的最短路径,其中两条有黄色节点出现,因此黄色节点对于红绿节点对的中介概率为 2 / 3 = 0.6667
。
对于两个不连通的节点,任何其他一个节点针对他们的中介概率都是 0。
中介中心性
计算中介中心性,需要先列出全图除该点外的所有节点对,计算该点对于每个节点对的中介概率,再对这些概率求平均值:
其中,x
为待计算的节点,i
、j
为图中不同于 x
且互异的任意两节点,i
、j
配对不重复,σ
为 i
、j
间的所有最短路径的数量,σ(x)
为这些最短路径中包含点 x
的路径的数量,σ(x)
/σ
就是 x
对于 i
、j
的中介概率(i
、j
不连通时为 0),k
为图中的节点数量,即 (k-1)(k-2)/2
为 i
、j
节点对的数量。
计算上图中红色节点的中介中心性。根据找出的各节点对的最短路径算出红色节点对他们的中介概率,取平均值后得到中介中心性为 (1/2 + 1 + 2/3) / 6 = 0.3611
。
由于需要计算全图经过该某个点的最短路径数量,中介中心性会消耗较多的计算资源。在进行中介中心性计算时,可对点的数量大于 10,000 的图集进行采样计算,建议采样个数为以 10 为底的对数
log(点数量)
;可通过配置项决定是否采样。
特殊处理
孤点、不连通图
孤点不与任何其它节点相连,其中介中心性为 0;但孤点参与点对的构成,影响节点对的数量。
对于不连通图中的两个不连通的节点,任何其他一个节点针对他们的中介概率都是 0。
自环边
中介中心性计算的是节点之间的最短距离,自环边不构成最短路径,因此不参与计算。
有向边
对于有向边,中介中心性算法会忽略边的方向,按照无向边进行计算。
结果和统计值
以下面的 7 人小型社交网络为例,针对所有点运行中介中心性算法:
算法结果:为每个点计算中介中心性,根据算法执行方式,返回 _id
、centrality
两列或 _uuid
、centrality
两列
_uuid | _id | centrality |
---|---|---|
1 | Sue | 0.0000000 |
2 | Dave | 0.33333334 |
3 | Ann | 0.13333334 |
4 | Mark | 0.13333334 |
5 | May | 0.066666670 |
6 | Jay | 0.066666670 |
7 | Billy | 0.0000000 |
算法统计值:无
命令及配置项
- 命令:
algo(betweenness_centrality)
params()
参数配置项如下:
名称 |
类型 |
默认值 |
规范 |
描述 |
---|---|---|---|---|
sample_size | int | -1 | -1,-2 或 (0,节点总数] | 随机采样的点个数,-1 表示采样 log(<全图点数量>) 个点进行计算,-2 或忽略表示不采样,用所有点进行精确计算 |
limit | int | -1 | >=-1 | 需要返回的结果条数,-1 或忽略表示返回所有结果 |
order | string | / | ASC/DESC,大小写不敏感 | 对返回结果进行排序;忽略表示不排序 |
示例:计算所有点的中介中心性,进行精确不采样计算,并返回 6 条结果
algo(betweenness_centrality).params({
limit: 6,
sample_size: -2
}) as bc
return bc
算法执行
任务回写
1. 文件回写
配置项 | 各列数据 |
---|---|
filename | _id ,centrality |
示例:计算所有点的中介中心性,将算法结果回写至名为 cen 的文件
algo(betweenness_centrality).params().write({
file:{
filename: "cen"
}
})
2. 属性回写
配置项 | 回写内容 | 类型 | 数据类型 |
---|---|---|---|
property | centrality |
点属性 | float |
示例:计算所有点的中介中心性,将中介中心性回写至名为 bc 的点属性
algo(betweenness_centrality).params().write({
db:{
property: "bc"
}
})
3. 统计回写
算法无统计值。
直接返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其中介中心性 | _uuid , centrality |
示例:计算所有点的中介中心性,将算法结果定义为别名 results 并返回中心性最大的三个结果
algo(betweenness_centrality).params({
order: "desc",
limit: 3
}) as results
return results
流式返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其中介中心性 | _uuid , centrality |
示例:计算图中中介中心性为 0 的节点数量
algo(betweenness_centrality).params().stream() as results
where results.centrality == 0
return count(results)
实时统计
算法无统计值。