EUVIMEDOpdag EUVIMED
Open access · CC BY 4.0

SILVAN : Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds

Leonardo Pellegrina, Fabio Vandin

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.

AbstractBibliografiske oplysningerCiteRelated studies

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}
}
Start for free →