Brandes' algorithm

Brandes' algorithm

An undirected graph colored based on the betweenness centrality of each vertex from least (red) to greatest (blue).
Class	Greedy algorithm Dynamic programming
Worst-case performance	$\Theta (|V||E|)$

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. Calculating betweenness centrality is of great interest to some people such as __ and __.

Definitions

There are several metrics for the centrality of a node, one such metric being the betweenness centrality. For a node $v$ in a connected graph, we first define the pair dependency of $v$ with respect to $s$ and $t$ as:

$\delta _{st}(v)={\frac {\sigma _{st}(v)}{\sigma _{st}}}$,

where $\sigma _{st}$ is the total number of shortest paths from node $s$ to node $t$, and $\sigma _{st}(v)$ is the number of these paths which pass through $v$. By convention, $\sigma _{st}=1$ whenever $s=t$. For an unweighted graph, the length of a path is the number of edges. In other words, the pair dependency is the proportion of shortest paths that go through $v$.

The betweenness centrality of $v$ is simply the sum of its pair dependencies, taken over all pairs $s$ and $t$ excluding $v$:

$C_{B}(v)=\sum _{s,t\neq v}\delta _{st}(v)$

Algorithm

The algorithm performs the following steps:

$C_{B}(v)\leftarrow 0$ for every $v\in V$

$\sigma _{uv}\leftarrow 1$ if $u=v$, and $0$ otherwise

For every $s\in V$:

$\delta (v)\leftarrow 0$ for every $v\in V$

$\mathrm {dist} (v)\leftarrow \infty$ for every $v\in V$

$\mathrm {dist} (s)\leftarrow 0$

$\mathrm {prev} (v)\leftarrow \emptyset$ for every $v\in V$

$Q\leftarrow \{s\}$ (a queue containing only $s$)

$S\leftarrow \emptyset$ (an empty stack)

While $|Q|>0$:

$u\leftarrow Q.\mathrm {dequeue} ()$

For each neighbour $v$ of $u$:

If $\mathrm {dist} (w)=\infty$:

$\mathrm {dist} (v)\leftarrow \mathrm {dist} (u)+1$

$Q.\mathrm {enqueue} (v)$

If $\mathrm {dist} (v)=\mathrm {dist} (u)+1$:

$\sigma _{sv}\leftarrow \sigma _{sv}+\sigma _{su}$

$\mathrm {prev} (v)\leftarrow \mathrm {prev} (v)\cup \{u\}$

While $|S|>0$:

$v\leftarrow S.\mathrm {pop} ()$

For every $u\in P(v)$:

$\delta (u)\leftarrow \delta (u)+{\frac {\sigma _{su}}{\sigma _{sv}}}(1+\delta (v))$.

If $u\neq s$:

$C_{B}(v)\leftarrow C_{B}(v)+\delta _{s}(w)$.

$C_{B}(v)$ is now the betweenness centrality of $v$.

In pseudocode:

function Brandes(graph):
    for u in graph.vertices:
        for v in graph.vertices:
            if u = v:
                σ[u, v] = 1
            else:
                σ[u, v] = 0

    for v in graph.vertices:
        CB[v] ← 0

    for s in graph.vertices:
        for v in graph.vertices:
            δ[v] ← 0
            dist[v] ← ∞
            
        Q ← queue containing only s
        S ← empty stack
        
        while Q is not empty:
            u ← Q.dequeue()
            for v in graph.neighbours[u]:
                if dist[v] = ∞:
                    dist[v] = dist[u] + 1
                    Q.enqueue(v)
                if dist[v] = dist[u] + 1:
                    σ[s, v] ← σ[s, v] + σ[s, u]
                    append u to prev[v]

        while S is not empty:
            v ← S.pop()
            for u in prev[v]:
                δ[u] ← δ[u] + σ[s, u]/σ[s, v] : (1 + δ[v])
                
            if v ≠ s:
                CB[v] ← CB[v] + δ[v]

    return CB

Brandes' algorithm calculates betweenness centrality for all nodes in a graph. Several algorithms have been proposed in the past, including a modification of the Floyd–Warshall algorithm. To calculate the number of shortest paths, breadth-first search can be used. For a breadth-first search starting from node $s$, we keep track of the set of immediate predecessors $P_{s}(v)$ for each node $v$. The shortest path count $\sigma _{sv}$ can be calculated by summing the counts of its predecessors:

$\sigma _{sv}=\sum _{u\in P_{s}(v)}\sigma _{su}$

If this process is repeated for every starting node $s$, the time complexity is $O(|V||E|)$.

A naive algorithm does this on every node, counting the number of shortest paths, and summing them up. This is possible by However, this is inefficient, as it would take $O(|V|^{3})$ time and $O(|V|^{2})$ space to store data.

The naive algorithm explicitly sums all pair dependencies.

We define the dependency of a vertex as the sum of its pair dependencies, with respect to a fixed $s$ and summed over all $t$:

$\delta _{s}(v)=\sum _{t\in V}\delta _{st}(v)$

Proof of correctness

The algorithm relies on the following recursive formula for vertex dependencies:

$\delta _{s}(v)=\sum _{v\in V}\sum _{u\in P_{s}(v)}{\frac {\sigma _{su}}{\sigma _{sv}}}\cdot (1+\delta _{s}(w))$

Variants

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

Sources

Brandes 2001, primary

Brandes 2008

Wasserman Faust 1994, social network analysis

Scott 1991, methods of network analysis

Freeman 1977, measures of centrality

Sabidussi 1966, the centrality index

Borgatti Everett 2006, Graph perspective on centrality

Kleinberg 1999, internet networks

Brin Page 1998, anatomy of the web

Bharat Henzinger 1998, hyperlinked environments

Anthonisse 1971, the rush in a directed graph