ABRA: Approximating Betweenness Centrality in Static and Dynamic Graphs\n with Rademacher Averages

2016/02/18 by Matteo Riondato, Eli Upfal, Riondato, Matteo +1 · 5 citations
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #G.2.2 #Graph Theory and Algorithms #H.2.8

paper · pdf · doi:10.48550/arxiv.1602.05866

openalex publication_date 2016/02/18 · openalex created_date 2022/08/30 · openalex updated_date 2026/07/28

Abstract

We present ABRA, a suite of algorithms that compute and maintain\nprobabilistically-guaranteed, high-quality, approximations of the betweenness\ncentrality of all nodes (or edges) on both static and fully dynamic graphs. Our\nalgorithms rely on random sampling and their analysis leverages on Rademacher\naverages and pseudodimension, fundamental concepts from statistical learning\ntheory. To our knowledge, this is the first application of these concepts to\nthe field of graph analysis. The results of our experimental evaluation show\nthat our approach is much faster than exact methods, and vastly outperforms, in\nboth speed and number of samples, current state-of-the-art algorithms with the\nsame quality guarantees.\n

Citations

• Decision theoretic generalizations of the PAC model for neural net and other learning applications

Cited by

• A Survey on Centrality and Importance Measures in Hypergraphs: Categorization and Empirical Insights
• Fast Percolation Centrality Approximation with Importance Sampling
• Efficient and Adaptive Estimation of Local Triadic Coefficients
• An Asymptotically Tighter Bound on Sampling for Frequent Itemsets Mining
• CLGNN: A Contrastive Learning-based GNN Model for Betweenness Centrality Prediction on Temporal Graphs

Related

• SILVAN: Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds
• KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation
• A Divide-and-Conquer Algorithm for Betweenness Centrality
• MANTRA: Temporal Betweenness Centrality Approximation through Sampling
• Refining Approximating Betweenness Centrality Based on Samplings