The betweenness centrality of all graph vertices can be computed in O(nm) time

You need to know: Basic graph theory (graphs, vertices, edges, shortest path), notation.

Background: Let be the total number of shortest paths from s to t in an undirected graph G. Let the number of such shortest paths which contain vertex v.  The number is called the betweenness centrality of vertex v.

The Theorem: On 25th September 2000, Ulrik Brandes submitted to The Journal of Mathematical Sociology a paper in which he developed an algorithm which compute the betweenness centrality of all vertices of graph with n vertices and m edges in time .

Short context: The betweenness centrality is important in the analysis of social networks. However, before the Theorem, the fastest algorithm to compute it worked in steps. The Theorem provides a significant improvement for graphs with not too many edges, which is often the case in the applications.

Links: The original paper is available here.

Go to the list of all theorems