ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs with Rademacher Averages

Posted on September 18, 2016

Authors: Matteo Riondato (Two Sigma), Eli Upfal

Published in: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 1145–1154

Repeated at:

  • Center of Data Science, New York University, New York (NY, USA), May 17, 2017
  • Department of Computer Science, Boston University, Boston (MA, USA), November 18, 2016
  • 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), San Francisco (CA, USA), August 15, 2016
  • Network Science Institute, Northeastern University, Boston (MA, USA), October 17, 2016
  • Social Impact through Network Science (SINS), Venice (Italy), June 8, 2016

Abstract:  We present ABRA, a suite of algorithms to compute and maintain probabilistically-guaranteed, high-quality, approximations of the betweenness centrality of all nodes (or edges) on both static and fully dynamic graphs. Our algorithms use progressive random sampling and their analysis rely on Rademacher averages and pseudodimension, fundamental concepts from statistical learning theory. To our knowledge, this is the first application of these concepts to the field of graph analysis. Our experimental results show that ABRA is much faster than exact methods, and vastly outperforms, in both runtime and number of samples, state-of-the-art algorithms with the same quality guarantees.

DOI: https://doi.org/10.1145/2939672.2939770

Download PDF — 1.23 MB

This article is not an endorsement by Two Sigma of the papers discussed, their viewpoints or the companies discussed. The views expressed above reflect those of the authors and are not necessarily the views of Two Sigma Investments, LP or any of its affiliates (collectively, “Two Sigma”). The information presented above is only for informational and educational purposes and is not an offer to sell or the solicitation of an offer to buy any securities or other instruments. Additionally, the above information is not intended to provide, and should not be relied upon for investment, accounting, legal or tax advice. Two Sigma makes no representations, express or implied, regarding the accuracy or completeness of this information, and the reader accepts all risks in relying on the above information for any purpose whatsoever. Click here for other important disclaimers and disclosures.