BrandesAlgorithmus

The BrandesAlgorithmus, named after Ulrik Brandes, is an algorithm for computing the betweenness centrality of all vertices in a graph. It is applicable to directed and undirected graphs and to both unweighted and weighted variants, providing a principled measure of how often a node lies on shortest paths between pairs of other nodes.

The method performs a single-source shortest-path computation from every source vertex s. During each run, it records for each vertex v the number sigma[v] of shortest paths from s to v, as well as the predecessor set P[v] on these shortest paths and the vertices in nondecreasing distance order (stored on a stack S). After exploring all shortest paths from s, the algorithm executes a back-propagation of dependencies delta by processing vertices in reverse distance order. For each w popped from S, it updates delta[v] for every v in P[w] with delta[v] += (sigma[v]/sigma[w]) (1 + delta[w]). If w is not the source, the centrality score is updated as C[w] += delta[w]. Repeating this for all sources s yields the betweenness centrality for all vertices.

Complexity-wise, for unweighted graphs the total time is O(nm), with n nodes and m edges. For weighted graphs with nonnegative weights, the approach uses a Dijkstra run per source, resulting in O(n(m + n log n)) time (often cited as O(nm + n^2 log n)). Memory usage is O(n + m).

Normalization varies by graph type. In undirected graphs, raw scores are often divided by (n−1)(n−2)/2; in directed graphs, by (n−1)(n−2). The BrandesAlgorithmus also supports variants for large networks, including approximations.