关于数据库:基于-Nebula-Graph-的-BetweennessCentrality-算法

本文首发于 Nebula Graph Community 公众号

​在图论中，介数（Betweenness）反馈节点在整个网络中的作用和影响力。而本文次要介绍如何基于 Nebula Graph 图数据库实现 Betweenness Centrality 介数核心性的计算。
   

1. 算法介绍

核心性 是用来掂量一个节点在整个网络图中所在核心水平的概念，包含度核心性、靠近核心性、中介核心性等。其中度核心性通过节点的度数（即关联的边数）来刻画节点的受欢迎水平，靠近核心性是通过计算每个节点到全图其余所有节点的门路和来刻画节点与其余所有节点的关系密切水平。

中介核心性则 用于掂量一个顶点呈现在其余任意两个顶点对之间最短门路上的次数，从而来刻画节点的 重要性。

节点介数核心性的定义是：在所有最短门路中通过该节点的门路数目占最短门路总数的占比。

计算图中节点的介数核心性分为两种状况：有权图上的介数核心性和无权图上的介数核心性。两者的区别在于求最短门路时应用的办法不同，对于无权图采纳 BFS（宽度优先遍历）求最短门路，对于有权图采纳 Dijkstra 算法求最短门路。

上面所介绍的算法都是针对无向图的。

2. 利用场景

介数反馈节点在整个网络中的作用和影响力，次要用于掂量一个顶点在图或网络中承当“桥梁”角色的水平，图中节点 C 就是一个重要的桥梁节点。

核心性 可用于金融风控畛域中 反欺诈场景里中介实体 的辨认。也可用于医药畛域中 特定疾病管制基因 的辨认，用以改良药品的靶点。

3. 介数核心性公式

节点介数核心性的计算公式如下：

（公式 1）

其中

：通过节点 v 的 s 到 t 的最短门路条数；
：节点 s 到节点 t 的所有最短门路条数；

s 和 t 是属于节点汇合的任意一个节点对。

为不便计算，将每对顶点的介数计算定义为：

（公式 2）

所以下面的公式 1 能够用公式 2 代替，即

（公式 3）

4. 求解思路

求节点 v 的介数核心性，即计算，须要晓得节点 v 是否在 s 到 t 的门路上。

（1）求节点 v 是否在 s 到 t 的最短门路上，采纳上面公式判断 示意两点之间的最短门路长度)：

当 v 位于 s 到 t 的最短门路上时，有

（公式 4）

又因为 和 是相互独立的，依据数学组合常识得悉 s 到 t 的最短门路总数是 s 到 v 的最短门路数与 v 到 t 的最短门路数的乘积。

所以有上面公式：

（公式 5）

（2）依据下面公式可得：

节点 s 到节点 t 的通过 w 的最短门路条数为 ，在图中节点 v 是 w 的前置节点，所以 st 之间通过节点 v 和 w 的最短门路条数计算公式为：

（公式 6）

上面分为两种状况：别离是 和

（一）

（公式 7）

（二） 时

（公式 8）

（3）所以将下面两种状况加起来，失去通过 v 的 s 到所有顶点的最短门路数占 s 到所有顶点的最短门路数的比值。

（公式 9）

其中 即 v 是 s 到 w 门路中 w 的前驱节点。

（4）依据下面的求 的公式，上面给出论文中求解无权图时的算法流程，如下所示。

对于无权图实现依据下面流程实现。

有权图的介数核心性计算须要将求解最短门路的办法改成采纳 Dijkstra 办法，即改变第一个 while 循环内的代码。

基于 Nebula Graph 的 Betweenness Centrality 实现了针对有权图和无权图的计算，实现代码见 https://github.com/vesoft-inc/nebula-algorithm/blob/master/nebula-algorithm/src/main/scala/com/vesoft/nebula/algorithm/lib/BetweennessCentralityAlgo.scala。

5. 计算示例

首先读取 Nebula Graph 中的图数据，能够指定其边数据进行数据读取。

其次针对 Nebula Graph 的边数据结构拓扑图，执行核心性计算。

读取的 Nebula Graph 图数据以该无权图为例：

计算节点 1 的 BC：

计算节点 2 的 BC：

计算节点 3 的 BC：

计算节点 4 的 BC：

计算节点 5 的 BC：

所以每个节点的 BC 值是：
1: 1/3
2: 1
3: 1/3
4: 1
5: 1/3

6. 算法后果示例

数据：读取 Nebula Graph test 中的边数据，以 srcId、dstId 和 rank 别离作为拓扑图中的边的三元组（终点、重点、权重）

(root@nebula) [test]> match (v:node) -[e:relation] -> ()  return e
+------------------------------------+
| e                                  |
+------------------------------------+
| [:relation "3"->"4" @1 {col: "f"}] |
+------------------------------------+
| [:relation "2"->"3" @2 {col: "d"}] |
+------------------------------------+
| [:relation "2"->"5" @4 {col: "e"}] |
+------------------------------------+
| [:relation "4"->"5" @2 {col: "g"}] |
+------------------------------------+
| [:relation "1"->"5" @1 {col: "a"}] |
+------------------------------------+
| [:relation "1"->"2" @3 {col: "b"}] |
+------------------------------------+
| [:relation "1"->"4" @5 {col: "c"}] |
+------------------------------------+

读取 Nebula Graph 边数据，设置无权重并执行 BC 算法，输入后果如下：

vid: 4 BC: 1.0
vid: 1 BC: 0.3333333333333333
vid: 3 BC: 0.3333333333333333
vid: 5 BC: 0.3333333333333333
vid: 2 BC: 1.0

读取 Nebula Graph 边数据，设置有权重并执行 BC 算法，输入后果如下：

vid: 4 BC: 2.0
vid: 1 BC: 0.5
vid: 3 BC: 1.0
vid: 5 BC: 2.0
vid: 2 BC: 0.0

7. 参考资料

• 论文《A Faster Algorithm for Betweenness Centrality》
• Python 的 NetworkX 实现介数核心性的源码：https://github.com/networkx/networkx/blob/master/networkx/algorithms/centrality

本文中如有任何谬误或疏漏，欢送去 GitHub：https://github.com/vesoft-inc/nebula issue 区向咱们提 issue 或者返回官方论坛：https://discuss.nebula-graph.com.cn/ 的 倡议反馈 分类下提倡议 👏；交换图数据库技术？退出 Nebula 交换群请先填写下你的 Nebula 名片，Nebula 小助手会拉你进群~~