中介中心性算法详解与应用

中介中心性算法详解与应用

v4.5

• v5.0
• v4.5

中介中心性

✓ 文件回写✓ 属性回写✓ 直接返回✓ 流式返回✕ 统计值

概述

中介中心性（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）是指经过的边数最少（非权重图）或所有边的权重和最小（权重图）的路径。
在上面的非权重图中，红、绿两点间存在三条最短路径，其中有两条经过黄色节点，因此，黄色节点对于红绿节点对的中介概率为
2 / 3 = 0.6667
。

中介中心性

在本算法中，节点的中介中心性分值计算公式为：
其中，
x
为待计算的目标节点，
i
、
j
为图中互异的任意两个节点（不包含
x
），
σ
为
ij
点对最短路径的数量，
σ(x)
为
ij
点对经过
x
的最短路径的数量，
σ(x)
/
σ
就是
x
对于
ij
点对的中介概率（
i
、
j
不连通时该概率为0），
k
为图中节点的数量，
(k-1)(k-2)/2
为
ij
节对的数量。

计算上图中红色节点的中介中心性。图中共有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] -2 是 采样节点数；-1代表采样数为log(V)，-2代表不采样进行精确计算，一个介于 [1, V] 的数代表采样规定数目的节点
  limit int ≥-1 -1 是 返回的结果条数，-1返回所有结果
  order string asc,desc / 是 按中心性分值大小对结果进行排序

示例

示例图是一个小型社交网络，点代表user，边代表know关系：

文件回写

配置项 回写内容
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