图算法（十一）：介性中心度（Betweenness Centrality）

如果要衡量一个用户在关注网络中的“重要程度”，我们可以利用这几种指标：

• 该用户的粉丝数，即 入度（In-degree）；
• 该用户的 PageRank值；
• 该用户的 HITS值 【维基百科 、百度百科】

以上3中指标在网络分析中也可被归为同一类指标：点的中心度（Centrality） 。

但我们发现，其实三种指标所表达的“重要”，其含义是不完全一样的，同一个网络，同一个节点，可能不同的中心度排名会有不小的差距。

据Li Yang等人的论文总结了四种衡量网络中一个节点的重要程度的方法：

1. Degree Centrality ：对无向图来说，节点v的degree就是它的直接邻居节点数量。
2. Closeness Centrality ：节点 v 的closeness就是 v 到其他各个节点的最短路径的长度之和的倒数。也就是说如果 v 到各个节点的路径越短，则closeness越大，说明 v 越重要。
3. Betweenness Centrality ：节点 v 的B