The algorithmic analysis of complex networks has become
a highly active research area recently. One important task in network analysis is to rank
nodes by their structural importance using centrality measures.
Betweenness
centrality (BC) measures the participation of a node
in the shortest paths of the network.
Let the graph \(G\)  represent a network with \(n\)  nodes and \(m\)  edges.
Naming \(\sigma _{st}\)  the number of shortest paths from a node \(s\)  to a node \(t\)  and \(\sigma _{st}(v)\)  the number of shortest paths from \(s\)  to \(t\)  that go through \(v\) , the (normalized) BC
of \(v\)  is defined as [1]}:
\(c_{B}(v)=\frac{1}{n(n-1)}\sum _{s\ne v \ne t}\frac{\sigma _{st}(v)}{\sigma _{st}}\) .
Nodes with high betweenness can be important in routing, spreading processes
and mediation of interactions.
Depending on the context, this can mean, for example, finding the
most influential persons in a social network, the key infrastructure
nodes in the internet, or super spreaders of a disease.
