Paper Info
Title
A Benchmark for Betweenness Centrality Approximation Algorithms on Large Graphs.
Abstract
Betweenness centrality quantifies the importance of graph nodes in a variety of applications including social, biological and communication networks. Its computation is very costly for large graphs; therefore, many approximate methods have been proposed. Given the lack of a golden standard, the accuracy of most approximate methods is evaluated on tiny graphs and is not guaranteed to be representative of realistic datasets that are orders of magnitude larger. In this paper, we develop BeBeCA, a benchmark for betweenness centrality approximation methods on large graphs. Specifically: (i) We generate a golden standard by deploying a parallel implementation of Brandes algorithm using 96,000 CPU cores on a supercomputer to compute exact betweenness centrality values for several large graphs with up to 126M edges. (ii) We propose an evaluation methodology to assess various aspects of approximation accuracy, such as average error and quality of node ranking. (iii) We survey a large number of existing approximation methods and compare their performance and accuracy using our benchmark. (iv) We publicly share our benchmark, which includes the golden standard exact betweenness centrality values together with the scripts that implement our evaluation methodology; for researchers to compare their own algorithms and practitioners to select the appropriate algorithm for their application and data.
Year
DOI
Venue
2017
10.1145/3085504.3085510
SSDBM
Keywords
Field
DocType
Social Networks,Betweenness Centrality,Approximation Algorithms,Experimental Evaluation
Network science,Data mining,Approximation algorithm,Ranking,Supercomputer,Computer science,Centrality,Theoretical computer science,Betweenness centrality,Network theory,Computation
Conference
Citations 
PageRank 
References 
2
0.37
20
Authors
4
Name
Order
Citations
PageRank
Ziyad AlGhamdi120.37
Fuad T. Jamour2263.19
Spiros Skiadopoulos3113965.60
Panos Kalnis43297141.30