Betweenness centrality measures how often a node is in the shortest path of all other network nodes.
Closeness centrality measures the reachability of a node, which can be interpreted as the importance of a vertex in a network. On the other hand, cut vertices, a vertex whose removal partitions the graph, can play a central and essential role in the network. Based on this observation, researchers in social sciences introduced the concept of betweenness centrality, a widespread measure of centrality these days.
Each pair of nodes exchange information with an equal probability per unit of time. The information flow follows the shortest path.
After a period of time large enough, the flow rate at a node is proportional to the number of shortest paths through this node.
Let \(G=(V,E)\) be a connected undirected graph. The betweenness centrality for a node \(v\) is given by
\[ c_B(v) = \sum_{s,t \in V(G), s\neq v, t\neq v} \frac{\sigma_{st}(v)}{\sigma_{st}} \]where \(\sigma_{st}\) is the total number of shortest paths from \(t\) to \(s\) and \(\sigma_{st}(v)\) is the number of shortest paths from \(t\) to \(s\) which contain the node \(v\).
Betweenness centrality can be computed in \(\mathcal{O}(nm)\) for unweighted graphs. The time complexity for weighted graphs is \(\mathcal{O}(nm + n^2\log n)\).
The algorithm is based on two main components:
Dependency partial sum \[ \delta_s(v) = \sum_{w:v\in P(w)} \frac{\sigma_{sv}}{\sigma_{sw}} ( 1 + \delta_s(w)) \]
The betweenness centrality of a node is obtained as follows: \[ c_B(v) = \sum_{s \in V, s \neq v} \delta_s(v) \]