In network theory, Brandes' algorithm is an algorithm for calculating the betweenness centrality of vertices in a graph.

The algorithm was first published in 2001 by Ulrik Brandes.

[1] Betweenness centrality, along with other measures of centrality, is an important measure in many real-world networks, such as social networks and computer networks.

in a connected graph, the betweenness centrality is defined as:[6][7]

is the total number of shortest paths from node

For an unweighted graph, the length of a path is considered to be the number of edges it contains.

, since shortest paths do not pass through their endpoints.

, and represents the proportion of the shortest

.Brandes' algorithm calculates the betweenness centrality of all nodes in a graph.

is recorded, dividing the graph into discrete layers.

keeps track of the set of vertices which in the preceding layer which point to it,

.This lends itself to a simple iterative formula for

Brandes proved the following recursive formula for vertex dependencies:[1]

This lemma eliminates the need to explicitly sum all of the pair dependencies.

Furthermore, the order of summation is irrelevant, which allows for a bottom up approach starting at the deepest layer.

During the breadth-first search, the order in which vertices are visited is logged in a stack data structure.

The backpropagation step then repeatedly pops off vertices, which are naturally sorted by their distance from

.Crucially, every layer propagates its dependencies completely, before moving to the layer with lower depth, due to the nature of breadth-first search.

iterations of single-source shortest path and backpropagation, each

The following pseudocode illustrates Brandes' algorithm on an unweighted directed graph.

[8] The running time of the algorithm is expressed in terms of the number of vertices

, we run breadth-first search, which takes

In the backpropagation stage, every vertex is popped off the stack, and its predecessors are iterated over.

However, since each predecessor entry corresponds to an edge in the graph, this stage is also bounded by

time bounds achieved by prior algorithms.

[1] In addition, Brandes' algorithm improves on the space complexity of naive algorithms, which typically require

predecessors, along with data for each vertex, making its extra space complexity

The algorithm can be generalised to weighted graphs by using Dijkstra's algorithm instead of breadth-first search.

When operating on undirected graphs, the betweenness centrality may be divided by 2, to avoid double counting each path's reversed counterpart.

Variants also exist to calculate different measures of centrality, including betweenness with paths at most length