Algorithm for finding important nodes in a graph
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. Betweenness centrality, along with other measures of centrality, is an important measure in many real-world networks, such as social networks and computer networks.
Definitions.
There are several metrics for the centrality of a node, one such metric being the "betweenness centrality". For a node formula_1 in a connected graph, the betweenness centrality is defined as:formula_2where formula_3 is the total number of shortest paths from node formula_4 to node formula_5, and formula_6 is the number of these paths which pass through formula_1. For an unweighted graph, the length of a path is considered to be the number of edges it contains.
By convention, formula_8 whenever formula_9, since the only path is the empty path. Also, formula_10 if formula_1 is either formula_4 or formula_5, since shortest paths do not pass "through" their endpoints.
The quantityformula_14is known as the "pair dependency" of formula_15 on formula_1, and represents the proportion of the shortest formula_4–formula_5 paths which travel via formula_1. The betweenness centrality is simply the sum of the pair dependencies over all pairs.
As well as the pair dependency, it is also useful to define the ("single) dependency" on formula_1 , with respect to a particular vertex formula_4:formula_22,with which, we can obtain the concise formulationformula_23.
Algorithm.
Brandes' algorithm calculates the betweenness centrality of all nodes in a graph. For every vertex formula_4, there are two stages.
Single-source shortest path.
The number of shortest paths formula_25 between formula_4 and every vertex formula_1 is calculated using breadth-first search. The breadth-first search starts at formula_4, and the shortest distance formula_29 of each vertex from formula_4 is recorded, dividing the graph into discrete layers. Additionally, each vertex formula_1 keeps track of the set of vertices which in the preceding layer which point to it, formula_32. Described in set-builder notation, it can be written as:formula_33.This lends itself to a simple iterative formula for formula_25:formula_35,which essentially states that, if formula_1 is at depth formula_29, then any shortest path at depth formula_38 extended by a single edge to formula_1 becomes a shortest path to formula_1.
Backpropagation.
Brandes proved the following recursive formula for vertex dependencies:formula_41,where the sum is taken over all vertices formula_1 that are one edge further away from formula_4 than formula_44. This lemma eliminates the need to explicitly sum all of the pair dependencies. Using this formula, the single dependency of formula_4 on a vertex formula_44 at depth formula_47 is determined by the layer at depth formula_48. Furthermore, the order of summation is irrelevant, which allows for a bottom up approach starting at the deepest layer.
It turns out that the dependencies of formula_4 on all other vertices formula_44 can be computed in formula_51 time. 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 formula_4, descending.
For each popped node formula_1, we iterate over its predecessors formula_54: the contribution of formula_1 towards formula_56 is added, that is,formula_57.Crucially, every layer propagates its dependencies completely, before moving to the layer with lower depth, due to the nature of breadth-first search. Once the propagation reaches back to formula_4, every vertex formula_1 now contains formula_60. These can simply be added to formula_61, sinceformula_23.After formula_63 iterations of "single-source shortest path" and "backpropagation", each formula_61 contains the betweenness centrality for formula_1.
Pseudocode.
The following pseudocode illustrates Brandes' algorithm on an unweighted directed graph.
 algorithm Brandes("Graph") is
 for each "u" in "Graph.Vertices" do
 CB["u"] ← 0
 for each "s" in "Graph.Vertices" do
 for each "v" in "Graph.Vertices" do
 δ["v"] ← 0 // Single dependency of s on v
 prev["v"] ← empty list // Immediate predecessors of v during BFS
 σ["v"] ← 0 // Number of shortest paths from s to v (s implied)
 dist["v"] ← null // No paths are known initially,
 σ["s"] ← 1 // except the start vertex
 dist["s"] ← 0
 "Q" ← queue containing only "s" // Breadth-first search
 "S" ← empty stack // Record the order in which vertices are visited
 // "Single-source shortest paths"
 while "Q" is not empty do
 "u" ← "Q".dequeue()
 "S".push("u")
 for each "v" in "Graph.Neighbours"["u"] do
 if dist["v"] = null then
 dist["v"] ← dist["u"] + 1
 "Q".enqueue("v")
 if dist["v"] = dist["u"] + 1 then
 σ["v"] ← σ["v"] + σ["u"]
 prev["v"].append("u")
 // "Backpropagation of dependencies"
 while "S" is not empty do
 "v" ← "S".pop()
 for each "u" in prev["v"] do
 δ["u"] ← δ["u"] + σ["u"] / σ["v"] * (1 + δ["v"])
 if "u" ≠ "s" then
 CB["v"] ← CB["v"] + δ["v"] // Halved for undirected graphs
 return CB
Running time.
The running time of the algorithm is expressed in terms of the number of vertices formula_63 and the number of edges formula_67.
For each vertex formula_4, we run breadth-first search, which takes formula_69 time. Since the graph is connected, the formula_67 component subsumes the formula_63 term, since the number of edges is at least formula_72.
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 formula_51.
The overall running time of the algorithm is therefore formula_74, an improvement on the formula_75 time bounds achieved by prior algorithms. In addition, Brandes' algorithm improves on the space complexity of naive algorithms, which typically require formula_76 space. Brandes' algorithm only stores at most formula_67 predecessors, along with data for each vertex, making its extra space complexity formula_69
Variants.
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 formula_79, "edge betweenness", "load betweenness", and "stress betweenness".
References.
 ;templatestyles src="Reflist/styles.css" / ;