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)={\frac {\sum _{s\neq v\neq t\in V}\sigma _{st}(v)}{(n-1)(n-2)}}$

Where $\sigma _{st}(v)=1$ if the shortest path from s to t passes through v and 0 otherwise.

See also graph theory measures of distance.

References

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