EUVIMEDEUVIMED entdecken
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 · 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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Infokarte | EUVIMED

Artikeldaten derzeit nicht verfügbar.

Recherche