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

概述

中介中心性（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