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)$ is the number of shortest geodesic paths from s to t that pass through a vertex v. This may be normalised by dividing through by the number of pairs of vertices not including v, which is $(n-1)(n-2)$ .