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.[2][3][4]

Brandes' algorithm
An undirected graph colored based on the betweenness centrality of each vertex from least (red) to greatest (blue).
ClassCentrality
Network theory
Data structureConnected graph
Worst-case performance (unweighted)
(weighted)
Worst-case space complexity

Definitions edit

There are several metrics for the centrality of a node, one such metric being the betweenness centrality.[5] For a node   in a connected graph, the betweenness centrality is defined as:[6][7]

 

where   is the total number of shortest paths from node   to node  , and   is the number of these paths which pass through  . For an unweighted graph, the length of a path is considered to be the number of edges it contains.

By convention,   whenever  , since the only path is the empty path. Also,   if   is either   or  , since shortest paths are considered not to have truly passed through their endpoints.

The quantity

 

is known as the pair dependency on  , and represents the proportion of the shortest    paths which travel via  . 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   , with respect to a particular vertex  :

 ,

with which, we can obtain the concise formulation

 .

Algorithm edit

Brandes' algorithm calculates the betweenness centrality of all nodes in a graph. For every vertex  , there are two stages.

1. Single-source shortest path edit

The number of shortest paths   between   and every vertex   is calculated using breadth-first search. The breadth-first search starts at  , and the shortest distance   of each vertex from   is recorded, dividing the graph into discrete layers. Additionally, each vertex   keeps track of the set of vertices which in the preceding layer which point to it,  . Described in set-builder notation, it can be written as:

 .

This lends itself to a simple iterative formula for  :

 ,

which essentially states that, if   is at depth  , then any shortest path at depth   extended by a single edge to   becomes a shortest path to  .

2. Backpropagation edit

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

 ,

where the sum is taken over all vertices   that are one edge further away from   than  . This lemma eliminates the need to explicitly sum all of the pair dependencies. Using this formula, the single dependency of   on a vertex   at depth   is determined by the layer at depth  . 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   on all other vertices   can be computed in   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  , descending.

For each popped node  , we iterate over its predecessors  : the contribution of   towards   is added, that is,

 .

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  , every vertex   now contains  . These can simply be added to  , since

 .

After   iterations of single-source shortest path and backpropagation, each   contains the betweenness centrality for  .

Pseudocode edit

The following pseudocode illustrates Brandes' algorithm on an unweighted graph.[8]

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
            uQ.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
            vS.pop()

            for each u in prev[v] do
                δ[u] ← δ[u] + σ[u] / σ[v] * (1 + δ[v])

                if us then
                    CB[v] ← CB[v] + δ[v]

    return CB

Running time edit

The running time of the algorithm is expressed in terms of the number of vertices   and the number of edges  .

For each vertex  , we run a breadth-first search, which takes   time. Since the graph is connected, the   component subsumes the   term, since the number of edges is at least  .

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, and vice versa, this stage is also bounded by  .

The overall running time of the algorithm is therefore  . This is an improvement on the   time bounds achieved by prior algorithms.[1] The improvement can be attributed to the fact that the dependency on a vertex can be calculated from just its neighbours that are one level deeper. In addition, Brandes' algorithm improves on the space complexity of naive algorithms, which typically require   space. Brandes' algorithm only stores at most   predecessors, along with data for each vertex, making its extra space complexity  

Variants edit

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  , edge betweenness, load betweenness, and stress betweenness.[8]

References edit

  1. ^ a b c Brandes, Ulrik (June 2001). "A faster algorithm for betweenness centrality:". The Journal of Mathematical Sociology. 25 (2): 163–177. doi:10.1080/0022250X.2001.9990249. ISSN 0022-250X. Retrieved 10 May 2024.
  2. ^ Wasserman, Stanley; Faust, Katherine (1994). Social Network Analysis: Methods and Applications. Structural Analysis in the Social Sciences. Cambridge: Cambridge University Press. doi:10.1017/cbo9780511815478. ISBN 978-0-521-38707-1.
  3. ^ Borgatti, Stephen P.; Everett, Martin G. (1 October 2006). "A Graph-theoretic perspective on centrality". Social Networks. 28 (4): 466–484. doi:10.1016/j.socnet.2005.11.005. ISSN 0378-8733. Retrieved 10 May 2024.
  4. ^ Kleinberg, Jon M. (1 September 1999). "Authoritative sources in a hyperlinked environment". Journal of the ACM. 46 (5): 604–632. doi:10.1145/324133.324140. ISSN 0004-5411. Retrieved 10 May 2024.
  5. ^ Sabidussi, Gert (1 December 1966). "The centrality index of a graph". Psychometrika. 31 (4): 581–603. doi:10.1007/BF02289527. ISSN 1860-0980. Retrieved 10 May 2024.
  6. ^ Freeman, Linton C. (1977). "A Set of Measures of Centrality Based on Betweenness". Sociometry. 40 (1): 35–41. doi:10.2307/3033543. ISSN 0038-0431.
  7. ^ Anthonisse, J. M. (1 January 1971). "The rush in a directed graph". Stichting Mathematisch Centrum.
  8. ^ a b Brandes, Ulrik (May 2008). "On variants of shortest-path betweenness centrality and their generic computation". Social Networks. 30 (2): 136–145. doi:10.1016/j.socnet.2007.11.001. ISSN 0378-8733. Retrieved 10 May 2024.