Betweenness Centrality
- The higher a node’s centrality is the more “dependent” other nodes are on it
- Based on shortest paths between nodes and the number of paths that pass through two points and the total number of paths
- BC(i) = SUM_{s≠i≠ t∈V}μ_{st}(i) / μ_{st} where μ_{st} is the number of paths from s and t and μ_{st}(i) is the number of paths from s and t that pass through node i
Algorithm
Input: V, a vertex and G, a graph
- For all pairs of vertices (v_{1} and v_{2}) in graph G, compute every shortest path between them
- Using v_{1} and v_{2}, compute the fraction of paths between these vertices that pass through V
- Sum over all pairs of vertices
More Information and other Algorithms:
References to use of this measure in literature: