中介中心性

概述

中介中心性（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)
• 参数：

示例

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

文件回写

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

属性回写

示例：计算所有点的中介中心性，将中介中心性回写至名为 bc 的点属性

algo(betweenness_centrality).params().write({
  db:{ 
    property: 'bc'
  }
})

结果：每个节点的中心性分值回写至名为bc的点属性下

直接返回

algo(betweenness_centrality).params({
  order: 'desc',
  limit: 3
}) as bc
return bc

结果：bc

流式返回

algo(betweenness_centrality).params().stream() as bc
where bc.centrality == 0
return count(bc)

结果：2