A benchmark for betweenness centrality approximation algorithms on large graphs

Ziyad Alghamdi, Spiros Skiadopoulos, Fuad Jamour, Panagiotis Kalnis

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationSSDBM 2017
Subtitle of host publication29th International Conference on Scientific and Statistical Database Management
PublisherAssociation for Computing Machinery
ISBN (Electronic)9781450352826
DOIs
StatePublished - Jun 27 2017
Event29th International Conference on Scientific and Statistical Database Management, SSDBM 2017 - Chicago, United States
Duration: Jun 27 2017Jun 29 2017

Publication series

NameACM International Conference Proceeding Series
VolumePart F128636

Conference

Conference29th International Conference on Scientific and Statistical Database Management, SSDBM 2017
CountryUnited States
CityChicago
Period06/27/1706/29/17

Keywords

  • Approximation algorithms
  • Betweenness centrality
  • Experimental evaluation
  • Social networks

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'A benchmark for betweenness centrality approximation algorithms on large graphs'. Together they form a unique fingerprint.

Cite this