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

arXiv: https://arxiv.org/abs/2106.03462 · HTML: https://mlsanity.com/paper/2106.03462/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2021.

## Built on by (most cited first, 3 of 3)

- [ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks](https://mlsanity.com/paper/2203.00653/) (2022)
- [Degree-Mass Message Passing for Betweenness Ranking in Directed and Undirected Networks](https://mlsanity.com/paper/2602.09716/) (2026)
- [CLGNN: A Contrastive Learning-based GNN Model for Betweenness Centrality Prediction on Temporal Graphs](https://mlsanity.com/paper/2506.14122/) (2025)

## Abstract (arXiv)

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.