Betweenness Centrality of a Graph

Betweenness centrality of a node $v$ is measurement of how likely the shortest path between two nodes $u_s$ and $u_t$ is gonna pass through node $v$,

$$ c(v) = \sum_{v\neq u_s\neq u_t} \frac{\sigma_{u_su_t}(v) }{\sigma_{u_su_t}}, $$

where $\sigma_{u_su_t}(v)$ is the number of shortest path between $u_s$ and $u_t$, and passing through $u$, while $\sigma_{u_su_t}$ is the number of shortest path between $u_s$ and $u_t$.

A figure from wikipedia demonstrates this idea well. The nodes on the outreach have smaller betweenness centrality, while the nodes in the core have higher betweenness centrality.

Source: Wikipedia

Source: Wikipedia

Outreach and Core

It is almost like cheating using the work “outreach” and “core” here. They are somewhat defined by betweenness centrality.

Planted: by ;

L Ma (2021). 'Betweenness Centrality of a Graph', Datumorphism, 09 April. Available at: