U. Brandes. Journal of Mathematical Sociology25 (2):
163--177(2001)
The betweenness centrality index is essential in the analysis of social networks, but costly to compute. Currently, the fastest known algorithms require #(n ) time and #(n ) space, where n is the number of actors in the network.