Betweenness problem

Betweenness is a centrality measure of a vertex within a graph. Vertices that occur on many shortest paths between other vertices have higher betweenness than those that do not.

Definition

For a graph $G:=(V,E)$ with n vertices, the betweenness $C_{B}(v)$ for vertex $v$ is:

$C_{B}(v)=\sum _{s\neq v\neq t\in V}{\frac {\sigma _{st}(v)}{\sigma _{st}}}$

Where $\sigma _{st}$ is the number of shortest geodesic paths from s to t, and $\sigma _{st}(v)$ the number of shortest geodesic paths from s to t that pass through a vertex v. This may be normalised by dividing through by $(n-1)(n-2)$.

See also

• Centrality
• Closeness
• Distance in graphs
• Graph theory

References

Freeman, L. C. (1977) A set of measures of centrality based on betweenness. Sociometry 40, 35--41.