A faster algorithm for betweenness centrality

By U. Brandes. 2001

4,832 citations recorded by the source corpus.

Motivated by the fast‐growing need to compute centrality indices on large, yet very sparse, networks, new algorithms for betweenness are introduced in this paper. They require O(n + m) space and run in O(nm) and O(nm + n2 log n) time on unweighted and weighted networks, respectively, where m is the number of links. Experimental evidence is provided that this substantially increases the range of networks for which centrality analysis is feasible. The betweenness centrality index is essential in the analysis of social networks, but costly to compute. Currently, the fastest known algorithms require ?(n 3) time and ?(n 2) space, where n is the number of actors in the network.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/1ef8c8c815b7268d7f7d4fe76af78aaa8df3e6da

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Quantitative neuroanatomy for connectomics in Drosophila (2015, background): “Other coloring modes include by betweenness centrality (Brandes, 2001) of the wiring diagram (calculated as a directed graph), which stresses the role of a neuron within a circuit; and by the percentage of review of the neuronal arbor, indicating at a glance the approximate level of completeness…”
A history of graph entropy measures (2011, background): “, vertex centrality measures [18], allow for using the local information graph to define more complex information functions on graphs and, hence, to obtain novel families of graph entropy measures.”
Unsupervised Graph-basedWord Sense Disambiguation Using Measures of Word Semantic Similarity (2007, neutral): “mate well the original definition of betweenness, while being significantly more efficient [1].”
Comparing community structure identification (2005, methodology): “ss for later retrieval and analysis. Calculation of link betweenness is the most computer intensive part of the algorithm. Using the fastest methods developed independently by Newman [27] and Brandes [28] and for a network of size n with m links the speed of calculating all link betweenness-es still”
Searching for superspreaders of information in real-world social media (2014, background): “Currently, the most efficient solution is Brandes’ algorithm 49 which takes complexity O ( nm ).”
Social network analysis: A methodological introduction (2008, background): “Betweenness is also fairly expensive to compute, although algorithms such as those of Brandes (2001) produce reasonable performance on sparse networks.”
Exploring the structure of the U.S. intercity passenger air transportation network: a weighted complex network approach (2008, methodology): “A global measure of the centrality of vertices or edges characterizing their betweenness has been used to characterize the role of vertices or edges in control of the communication in networks ( Brandes 2001, 2008; Freeman 1977 ;N ewman 2001 ;N ewman and Girvan2004).”
TrakEM2 Software for Neural Circuit Reconstruction (2012, background): “to label a branch), or follow a color code that expresses betweeness-centrality (computed as in [23]) relative to other nodes, branches or synapses.”
Towards comprehensive support for organizational mining (2008, background): “several centrality measures such as degree [50], betweenness [13], hubs-andauthorities [32].”
Do social networks of female northern long-eared bats vary with reproductive period and age? (2010, background): “Betweenness is the number of shortest paths (or smallest total edge weight) between an individual node and other nodes in the network (Brandes 2001).”
Structured Lexical Similarity via Convolution Kernels on Dependency Trees (2011, background): “A semantic similarity can be deﬁned at structural level over a graph, e.g. (Freeman, 1977; Bunke and Shearer, 1998; Brandes, 2001; Zhao et al., 2009), as well as combining structural and lexical similarity over semantic networks, e.g. (Cowie et al., 1992; Wu and Palmer, 1994; Resnik, 1995; Jiang…”
Community Structure in Graphs (2007, methodology): “The betweenness of all edges of the graph can be calculated in a time that scales as O ( mn ), with techniques based on breadth-ﬁrst-search [26, 38].”
Vital nodes identification in complex networks (2016, background): “Since the link weights in the most of the weighted networks are operationalizations of link strength and not the cost of them [282], both Newman [283] and Brandes [284] proposed to adopt the reciprocal of weights to extend closeness centrality and betweenness centrality (more details are shown in th”
Study on centrality measures in social networks: a survey (2018, methodology): “Time complexity of this measure is O(mn) for all vertices by the algorithm Brandes (2001).”
Evolution and Structure of the Internet: Index (2004, background): “Another quantity closely related to the shortest path length is the betweenness, sometimes also referred to as load or, in sociology, betweenness centrality (Newman, 2001b; Goh et al. 2001; Brandes, 2001).”