Approximating Betweenness Centrality through Sampling with the Rademacher Averages

Tuesday, September 18, 2018

12.00 p.m.

ISI seminar room 1st floor

Dr. Matteo Riondato Research Scientist, Labs, Two Sigma Investments

We show a sampling-based randomized approximation algorithm for estimating the betweenness centrality of all nodes in a graph, and to keep the estimations up-to-date as the graph evolves.
Our algorithm, called ABRA, employs progressive sampling and a stopping condition that uses efficient-to-compute bounds to the Rademacher Averages, a fundamental concept from statistical learning theory. We also use pseudodimension to prove an upper bound to the number of samples needed by the algorithm.
ABRA outperforms existing state-of-the-art algorithms offering the same quality guarantees, both in running time and in the number of samples needed.
Joint work with Eli Upfal, published at KDD’16 and in ACM TKDD.

Matteo Riondato is a Research Scientist in the Labs at Two Sigma Investments and an Adjunct Assistant Professor in Computer Science at Brown University. In January 2019 he will join Amherst College as an Assistant Professor. His research focus is in algorithmic data science, developing theory and methods to extract the most information from large datasets, as fast as possible and in a statistically sound way. He got is PhD from Brown and held postdoc positions at Brown and Stanford. His works received the best student poster award at the 2014 SIAM International Conference on Data Mining (SDM) and the best student paper award at the 2016 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). He tweets @teorionda and lives at .