Bavarian : Betweenness Centrality Approximation with Variance-aware Rademacher Averages
ACM Transactions on Knowledge Discovery from Data · 31.12.2023 · 17 (6) · 1-47
DOI: 10.1145/3577021 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Knowledge Discovery from Data, online erschienen am 06.03.2023. Verfasst von Cyrus Cousins und 2 weiteren Autor:innen. Die Arbeit wurde bisher 14-mal zitiert (Crossref) und nennt 69 Literaturangaben. Gefördert von: National Science Foundation, DARPA/ARFL.
Abstract (Originalsprache)
“[A]llain Gersten, Hopfen, und Wasser” — 1516 Reinheitsgebot We present Bavarian , a collection of sampling-based algorithms for approximating the Betweenness Centrality (BC) of all vertices in a graph. Our algorithms use Monte-Carlo Empirical Rademacher Averages (MCERAs), a concept from statistical learning theory, to efficiently compute tight bounds on the maximum deviation of the estimates from the exact values. The MCERAs provide a sample-dependent approximation guarantee much stronger than the state-of-the-art, thanks to its use of variance-aware probabilistic tail bounds. The flexibility of the MCERAs allows us to introduce a unifying framework that can be instantiated with existing sampling-based estimators of BC, thus allowing a fair comparison between them, decoupled from the sample-complexity results with which they were originally introduced. Additionally, we prove novel sample-complexity results showing that, for all estimators, the sample size sufficient to achieve a desired approximation guarantee depends on the vertex-diameter of the graph, an easy-to-bound characteristic quantity. We also show progressive-sampling algorithms and extensions to other centrality measures, such as percolation centrality. Our extensive experimental evaluation of Bavarian shows the improvement over the state-of-the-art made possible by the MCERAs (2–4× reduction in the error bound), and it allows us to assess the different trade-offs between sample size and accuracy guarantees offered by the different estimators.
Förderung
- National Science Foundation
- DARPA/ARFL
Zitieren
APA
Cousins, C., Wohlgemuth, C., & Riondato, M. (2023). Bavarian : Betweenness Centrality Approximation with Variance-aware Rademacher Averages. ACM Transactions on Knowledge Discovery from Data, 17(6), 1-47. https://doi.org/10.1145/3577021
Vancouver
Cousins C, Wohlgemuth C, Riondato M. Bavarian : Betweenness Centrality Approximation with Variance-aware Rademacher Averages. ACM Transactions on Knowledge Discovery from Data. 2023;17(6):1-47. doi:10.1145/3577021
BibTeX
@article{Cousins2023,
author = {Cousins, Cyrus and Wohlgemuth, Chloe and Riondato, Matteo},
title = {Bavarian : Betweenness Centrality Approximation with Variance-aware Rademacher Averages},
journal = {ACM Transactions on Knowledge Discovery from Data},
year = {2023},
volume = {17},
number = {6},
pages = {1--47},
doi = {10.1145/3577021}
}
EUVIMED