Research map / Learning theory and algorithms / Sample complexity
Random-Radius Ball Method for Estimating Closeness Centrality
Wataru Inariba, Takuya Akiba, Yuichi Yoshida
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use RRB-BS (PR) instead of HyperBall and ADS at equal accuracy | closeness centrality estimation · email-Enron | runtime: approximately 20 times faster | Improved |
| use RRB-BS instead of HyperBall and ADS | closeness centrality estimation · four smallest networks | runtime-accuracy trade-off | Improved |
| add permutation-rank technique to RRB-BS (ablation) | RRB-BS · four smallest networks | runtime-accuracy trade-off | Improved |
| add permutation-rank technique to RRB (ablation) | RRB · social networks | RMSE | Improved |
| add permutation-rank technique to RRB (ablation) | RRB · web-NotreDame | RMSE | No clear effect |
| scale graph size from 103,689 to 101,355,853 edges | RRB-BS (PR) · all 12 networks | runtime: 0.16 -> 223.64 | Mixed |
| check theoretical bound of Theorem 4 against actual error | RRB · all networks | RMSE | No clear effect |
| set k*=100 for high-centrality vertices | RRB-BS (PR) · all 12 networks | normalized RMSE: 1.72% to 5.84% | Improved |
Closest papers by meaning
- Axioms for Distance-Based Centralities (AAAI 2018 · similarity 0.84)
- Axiomatic Characterization of Game-Theoretic Network Centralities (AAAI 2017 · similarity 0.84)
- Biharmonic Distance of Graphs and its Higher-Order Variants: Theoretical Properties with Applications to Centrality and Clustering (ICML 2024 · similarity 0.83)
- Coverage Centrality Maximization in Undirected Networks (AAAI 2019 · similarity 0.83)
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.81)
- Temporal Triadic Closure: Finding Dense Substructures in Social Networks That Evolve over Time (AAAI 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
