中介中心性的定义是在路径基础之上的。从节点s到节点t的路径是指通过边连接一个节点序列，每一个节点连接了其前一个节点和后一个节点。路径的长度是指路径上所有边的权重之和，用d(s,t)表示，也称为节点s到节点t的距离。在图论中，一般使用最短路径计算各种指标。σst表示节点s到节点t的最短路径数量，σst(v)表示节点s到节点t的最短路径中经过节点v的数量。根据Freeman(1977)的定义，中介中心性是指经过节点v的所有最短路径的数量，若节点s到节点t的最短路径有两条，经过节点v的路径只有一条，那么节点v所得值normalize为1/2。

        根据最短路径和中介中心性的定义，有：

        Bellman标准：如果节点v在节点s和t的最短路径上，那么d(s,t)= d(s,v)+d(v,t)。即s到v和v到t都需要是最短路径。

        节点v来自于节点对<s,t>最短路径的中介中心性δst（节点对依赖值），其所获取的最短路径数量：

      那么节点v的最终中介中心性是网络中所有节点对的最短路径经过该节点的δst之和。

      因此，中介中心性的计算方法一般分为两步：

      （1）计算所有节点对的最短路径数和最短路径长度；

      （2）针对单个节点，加总其所有节点对依赖值。

l  最短路径数量计算

        从一个起点s开始搜寻，在无权网络中使用广度优先算法和在加权网络中使用Dijkstra算法开始计算。在每一步，选择到已发现节点集合中最近的节点，其目的是寻找到该起点s的所有最短路径。节点v的直接前序节点集合为：      

      那么，根据节点v的前序节点可以算出经过该节点的最短路径数：

l  汇总节点对依赖值

定义节点v来自于节点s的中介中心性依赖值为所有以节点s为起点经过节点v的节点对的节点对依赖值之和。

下图可以形象地表示该定义：

        如果s,t之间仅有一条最短路径，则可以将v对s的依赖值，转化为其前序节点对s的依赖值：

为什么括号中要加1？是因为w,v之间也是一条最短路径，需要加总到v上。

        去除只有一条最短路径的限制，则：

根据以上公式，算法描述如下：    

算法空间复杂度O(n + m)，无权网络的时间复杂度O(nm)，加权网络的时间复杂度O(nm + n2 log n)

该方法是用于计算节点的中介中心性值，边的中介中心性也可以相应的得到。

参考文献：

[1]Ulrik Brandes: A Faster Algorithm forBetweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001.