{{Short description|Algorithm for finding important nodes in a graph}} {{Use dmy dates|date=May 2024}} {{Infobox algorithm |name=Brandes' algorithm |class=Centrality<br>Network theory |image=Graph_betweenness.svg |caption = An undirected graph colored based on the betweenness centrality of each vertex from least (red) to greatest (blue) |data= Connected graph |time= <math>O(|V||E|)</math> (unweighted) <br><math>O(|V||E|+|V|^2 \log |V|)</math> (weighted) |space=<math>O(|V|+|E|)</math> }}
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.<ref name="Brandes2001">{{cite journal |last1=Brandes |first1=Ulrik |date=June 2001 |title=A faster algorithm for betweenness centrality |url=https://doi.org/10.1080/0022250X.2001.9990249 |journal=The Journal of Mathematical Sociology |language=en |volume=25 |issue=2 |pages=163–177 |doi=10.1080/0022250X.2001.9990249 |issn=0022-250X |access-date=10 May 2024|url-access=subscription }}</ref> Betweenness centrality, along with other measures of centrality, is an important measure in many real-world networks, such as social networks and computer networks.<ref>{{Cite book |last1=Wasserman |first1=Stanley |url=https://www.cambridge.org/core/books/social-network-analysis/90030086891EB3491D096034684EFFB8 |title=Social Network Analysis: Methods and Applications |last2=Faust |first2=Katherine |date=1994 |publisher=Cambridge University Press |isbn=978-0-521-38707-1 |series=Structural Analysis in the Social Sciences |location=Cambridge |doi=10.1017/cbo9780511815478}}</ref><ref name="BorgattiEverett2006">{{cite journal |last1=Borgatti |first1=Stephen P. |last2=Everett |first2=Martin G. |date=1 October 2006 |title=A Graph-theoretic perspective on centrality |url=http://dx.doi.org/10.1016/j.socnet.2005.11.005 |journal=Social Networks |volume=28 |issue=4 |pages=466–484 |doi=10.1016/j.socnet.2005.11.005 |issn=0378-8733 |access-date=10 May 2024|url-access=subscription }}</ref><ref name="Kleinberg1999">{{cite journal |last1=Kleinberg |first1=Jon M. |date=1 September 1999 |title=Authoritative sources in a hyperlinked environment |url=https://dl.acm.org/doi/10.1145/324133.324140 |journal=Journal of the ACM |volume=46 |issue=5 |pages=604–632 |doi=10.1145/324133.324140 |issn=0004-5411 |access-date=10 May 2024}}</ref>
== Definitions == There are several metrics for the centrality of a node, one such metric being the ''betweenness centrality''.<ref name="Sabidussi1966">{{cite journal |last1=Sabidussi |first1=Gert |date=1 December 1966 |title=The centrality index of a graph |url=https://link.springer.com/article/10.1007/BF02289527 |journal=Psychometrika |language=en |volume=31 |issue=4 |pages=581–603 |doi=10.1007/BF02289527 |pmid=5232444 |issn=1860-0980 |access-date=10 May 2024|url-access=subscription }}</ref> For a node <math>v</math> in a connected graph, the betweenness centrality is defined as:<ref name="Freeman1977">{{Cite journal |last=Freeman |first=Linton C. |date=1977 |title=A Set of Measures of Centrality Based on Betweenness |url=https://www.jstor.org/stable/3033543 |journal=Sociometry |volume=40 |issue=1 |pages=35–41 |doi=10.2307/3033543 |jstor=3033543 |issn=0038-0431|url-access=subscription }}</ref><ref name="Anthonisse1971">{{Cite journal |last=Anthonisse |first=J. M. |date=1971-01-01 |title=The rush in a directed graph |url=https://ir.cwi.nl/pub/9791 |journal=Stichting Mathematisch Centrum |language=en}}</ref><blockquote><math>C_B(v)= \sum_{s \in V} \sum_{t \in V} \frac{\sigma_{st}(v)}{\sigma_{st}}</math></blockquote>where <math>\sigma_{st}</math> is the total number of shortest paths from node <math>s</math> to node <math>t</math>, and <math>\sigma_{st}(v)</math> is the number of these paths which pass through <math>v</math>. For an unweighted graph, the length of a path is considered to be the number of edges it contains.
By convention, <math>\sigma_{st} = 1</math> whenever <math>s=t</math>, since the only path is the empty path. Also, <math>\sigma_{st}(v) = 0</math> if <math>v</math> is either <math>s</math> or <math>t</math>, since shortest paths do not pass ''through'' their endpoints.
The quantity<blockquote><math>\delta_{st}(v) = \frac{\sigma_{st}(v)}{\sigma_{st}}</math></blockquote>is known as the ''pair dependency'' of <math>st</math> on <math>v</math>, and represents the proportion of the shortest <math>s</math>–<math>t</math> paths which travel via <math>v</math>. 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 <math>v</math> , with respect to a particular vertex <math>s</math>:<blockquote><math>\delta_s(v) = \sum_{t \in V} \delta_{st}(v)</math>,</blockquote>with which, we can obtain the concise formulation<blockquote><math>C_B(v) = \sum_{s \in V} \delta_s(v)</math>.</blockquote>
== Algorithm == Brandes' algorithm calculates the betweenness centrality of all nodes in a graph. For every vertex <math>s</math>, there are two stages.
=== Single-source shortest path === The number of shortest paths <math>\sigma_{sv}</math> between <math>s</math> and every vertex <math>v</math> is calculated using breadth-first search. The breadth-first search starts at <math>s</math>, and the shortest distance <math>d(v)</math> of each vertex from <math>s</math> is recorded, dividing the graph into discrete layers. Additionally, each vertex <math>v</math> keeps track of the set of vertices which in the preceding layer which point to it, <math>p(v)</math>. Described in set-builder notation, it can be written as:<blockquote><math>p(v) = \{u \in V \mid (u, v) \in E \and d(u) + 1 = d(v)\}</math>.</blockquote>This lends itself to a simple iterative formula for <math>\sigma_{sv}</math>:<blockquote><math>\sigma_{sv} = \sum_{u \in p(v)} \sigma_{su}</math>,</blockquote>which essentially states that, if <math>v</math> is at depth <math>d(v)</math>, then any shortest path at depth <math>d(v)-1</math> extended by a single edge to <math>v</math> becomes a shortest path to <math>v</math>.
=== Backpropagation === Brandes proved the following recursive formula for vertex dependencies:<ref name="Brandes2001" /><blockquote><math>\delta_s(u) = \sum_{v \mid u \in p(v)} \frac{\sigma_{su}}{\sigma_{sv}} \cdot (1 + \delta_s(v))</math>,</blockquote>where the sum is taken over all vertices <math>v</math> that are one edge further away from <math>s</math> than <math>u</math>. This lemma eliminates the need to explicitly sum all of the pair dependencies. Using this formula, the single dependency of <math>s</math> on a vertex <math>u</math> at depth <math>d(u)</math> is determined by the layer at depth <math>d(u)+1</math>. 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 <math>s</math> on all other vertices <math>u</math> can be computed in <math>O(|E|)</math> 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 <math>s</math>, descending.
For each popped node <math>v</math>, we iterate over its predecessors <math>u \in p(v)</math>: the contribution of <math>v</math> towards <math>\delta_s(u)</math> is added, that is,<blockquote><math>\frac{\sigma_{su}}{\sigma_{sv}} \cdot (1 + \delta_s(v))</math>.</blockquote>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 <math>s</math>, every vertex <math>v</math> now contains <math>\delta_s(v)</math>. These can simply be added to <math>C_B(v)</math>, since<blockquote><math>C_B(v) = \sum_{s \in V} \delta_s(v)</math>.</blockquote>After <math>|V|</math> iterations of ''single-source shortest path'' and ''backpropagation'', each <math>C_B(v)</math> contains the betweenness centrality for <math>v</math>.
== Pseudocode == The following pseudocode illustrates Brandes' algorithm on an unweighted directed graph.<ref name="Brandes2008">{{cite journal |last1=Brandes |first1=Ulrik |date=May 2008 |title=On variants of shortest-path betweenness centrality and their generic computation |url=https://doi.org/10.1016/j.socnet.2007.11.001 |journal=Social Networks |volume=30 |issue=2 |pages=136–145 |doi=10.1016/j.socnet.2007.11.001 |issn=0378-8733 |access-date=10 May 2024|url-access=subscription }}</ref> '''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''' ''v'' ≠ ''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 <math>|V|</math> and the number of edges <math>|E|</math>.
For each vertex <math>s</math>, we run breadth-first search, which takes <math>O(|V|+|E|)</math> time. Since the graph is connected, the <math>|E|</math> component subsumes the <math>|V|</math> term, since the number of edges is at least <math>|V|-1</math>.
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 <math>O(|E|)</math>.
The overall running time of the algorithm is therefore <math>O(|V||E|)</math>, an improvement on the <math>O(|V|^3)</math> time bounds achieved by prior algorithms.<ref name="Brandes2001" /> In addition, Brandes' algorithm improves on the space complexity of naive algorithms, which typically require <math>O(|V|^2)</math> space. Brandes' algorithm only stores at most <math>|E|</math> predecessors, along with data for each vertex, making its extra space complexity <math>O(|V|+|E|)</math>
== 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 <math>k</math>, ''edge betweenness'', ''load betweenness'', and ''stress betweenness''.<ref name="Brandes2008" />
== References == {{reflist}} Category:Graph algorithms Category:Networking algorithms Category:Articles with example pseudocode Category:2001 in computing