SILVAN : Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds
ACM Transactions on Knowledge Discovery from Data · 2024-04-30 · 18 (3) · 1-55
DOI: 10.1145/3628601 ↗At a glance
Journal article in ACM Transactions on Knowledge Discovery from Data, published online on 2023-12-09. Written by Leonardo Pellegrina and 1 co-authors. Cited 16 times so far (Crossref); 69 references. The full text is freely available (open access, CC BY 4.0). Funded by: Italian Ministry of University and Research, National Center for HPC, Big Data, and Quantum Computing.
Abstract (original language)
“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.
Funding
- Italian Ministry of University and Research
- National Center for HPC, Big Data, and Quantum Computing
Cite
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