The betweenness centrality of a graph vertex 
in a graph 
is a measure of how often 
lies on shortest paths between
pairs of other vertices. It is commonly defined by
 |
where 
is the number of shortest paths from 
to 
, and 
is the number of such paths passing through 
.
For a connected vertex-transitive graph on 
vertices, all vertices have the same betweenness centrality. If 
is their common vertex
transmission, then the ordered-pair convention above gives
 |
The value is 
when unordered pairs are counted. For each source-target pair, summing the fractional
shortest-path contributions over all internal vertices gives 
, while vertex
transitivity makes all vertex totals equal.
Betweenness centrality was introduced in social network analysis as a way to identify vertices that mediate communication or flow between other vertices (Freeman 1977). It is therefore used to find brokers, bridges, and bottlenecks in social, communication, transportation, and biological networks. Unlike local measures such as degree centrality, betweenness centrality is global, since it depends on shortest paths between pairs of vertices throughout the graph. Edge betweenness centrality applies the same shortest-path idea to edges instead of vertices.
Betweenness centrality is implemented in the Wolfram Language as BetweennessCentrality[g], and precomputed values for many named graphs can be obtained using GraphData[graph, "BetweennessCentralities"].
