EUVIMEDEUVIMED entdecken
Crossref

Bavarian : Betweenness Centrality Approximation with Variance-aware Rademacher Averages

Cyrus Cousins, Chloe Wohlgemuth, Matteo Riondato

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →