Betweenness

From Wikipedia, the free encyclopedia

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.

[edit] 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 $σ s t$ is the number of shortest geodesic paths from s to t, and $σ s t (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 the number of pairs of vertices not including v, which is $(n - 1)(n - 2)$ .