SILVAN : Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds
ACM Transactions on Knowledge Discovery from Data · 30.04.2024 · 18 (3) · 1-55
DOI: 10.1145/3628601 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Knowledge Discovery from Data, online erschienen am 09.12.2023. Verfasst von Leonardo Pellegrina und 1 weiteren Autor:innen. Die Arbeit wurde bisher 16-mal zitiert (Crossref) und nennt 69 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Italian Ministry of University and Research, National Center for HPC, Big Data, and Quantum Computing.
Abstract (Originalsprache)
“Sim Sala Bim!” —Silvan, https://en.wikipedia.org/wiki/Silvan_(illusionist) Betweenness centrality is a popular centrality measure with applications in several domains and whose exact computation is impractical for modern-sized networks. We present SILVAN , a novel, efficient algorithm to compute, with high probability, accurate estimates of the betweenness centrality of all nodes of a graph and a high-quality approximation of the top- k betweenness centralities. SILVAN follows a progressive sampling approach and builds on novel bounds based on Monte Carlo Empirical Rademacher Averages, a powerful and flexible tool from statistical learning theory. SILVAN relies on a novel estimation scheme providing non-uniform bounds on the deviation of the estimates of the betweenness centrality of all the nodes from their true values and a refined characterisation of the number of samples required to obtain a high-quality approximation. Our extensive experimental evaluation shows that SILVAN extracts high-quality approximations while outperforming, in terms of number of samples and accuracy, the state-of-the-art approximation algorithm with comparable quality guarantees.
Förderung
- Italian Ministry of University and Research
- National Center for HPC, Big Data, and Quantum Computing
Zitieren
APA
Pellegrina, L., & Vandin, F. (2024). SILVAN : Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds. ACM Transactions on Knowledge Discovery from Data, 18(3), 1-55. https://doi.org/10.1145/3628601
Vancouver
Pellegrina L, Vandin F. SILVAN : Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds. ACM Transactions on Knowledge Discovery from Data. 2024;18(3):1-55. doi:10.1145/3628601
BibTeX
@article{Pellegrina2024,
author = {Pellegrina, Leonardo and Vandin, Fabio},
title = {SILVAN : Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds},
journal = {ACM Transactions on Knowledge Discovery from Data},
year = {2024},
volume = {18},
number = {3},
pages = {1--55},
doi = {10.1145/3628601}
}
EUVIMED