Authors: Matteo Riondato (Two Sigma), Eli Upfal
- 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.