Matteo Riondato
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.
Want to be notified about upcoming NetSI events? Sign up for our email list below!
Thank you! You have been added to our email list.
Oops! Something went wrong while submitting the form
Matteo Riondato
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.
