Random-Radius Ball Method for Estimating Closeness Centrality

Wataru Inariba, Takuya Akiba, Yuichi Yoshida

Introduction

In the field of network analysis, identifying the most "central" or influential nodes is a fundamental task. Closeness centrality is a widely used metric that measures how "near" a node is to all other nodes in a network. While Bavelas’ original definition is popular, it is limited to connected graphs. Harmonic centrality, which sums the inverse of distances, addresses this limitation but presents a significant computational challenge. For a graph with $n$ vertices and $m$ edges, calculating exact harmonic centrality requires $O(nm)$ time, which is prohibitive for modern massive networks with millions of nodes.

Existing approximation methods like HyperBall are fast but often complex to implement and lack rigorous theoretical error guarantees. All-Distances Sketches (ADS) provide such guarantees but are memory-intensive. This paper introduces the Random-Radius Ball (RRB) method, a remarkably simple randomized algorithm that is fast, memory-efficient, and mathematically sound.

Methodology: The Random-Radius Ball (RRB) Algorithm

The core innovation of the RRB method is its use of a random "broadcast" mechanism. Instead of calculating the distance from every node to every other node, each node $u$ is assigned a random "rank" $r_u$ sampled from the interval $[0, 1]$.

  1. Algorithm Execution: For each vertex, the algorithm determines a radius $\tau$ based on a distance-decay function (e.g., $1/distance$). A Breadth-First Search (BFS) is performed from $u$ up to depth $\tau$, and a counter is incremented for every reachable node.
  2. Unbiased Estimation: The authors demonstrate that the final counter value, when scaled by a parameter $t$, serves as an unbiased estimator of the node's centrality.
  3. RRB-BS (Bootstrapping): To eliminate the need for manual parameter tuning, the authors developed a "doubling strategy." The algorithm starts with a small $t$ and iteratively doubles it until a specific confidence threshold is met, effectively balancing runtime and precision.
  4. Permutation Rank (PR): An optimized variant, RRB (PR), uses a random shuffle of fixed values for ranks instead of independent sampling, which empirically reduces error variance.

Experimental Evaluation

The RRB method was evaluated on 12 diverse real-world datasets from the SNAP collection and the Laboratory for Web Algorithms. These included social networks (e.g., Wiki-Vote, email-Enron, soc-Pokec), web graphs (e.g., web-Google, web-NotreDame), and communication networks (e.g., dblp-2011, com-youtube). The largest dataset, enwiki-2013, contained over 100 million edges.

Key Results and Discussion

The RRB method demonstrates superior performance in both speed and accuracy compared to industry standards.

Trade-off between runtime and accuracy across different datasets.

Performance Benchmarks

In head-to-head comparisons, RRB-BS consistently outperformed HyperBall and ADS. On the email-Enron network, RRB-BS achieved comparable accuracy to its competitors while running approximately 20 times faster. Furthermore, the algorithm exhibited exceptional scalability, processing the enwiki-2013 dataset (4M nodes, 100M edges) in just four minutes on a single-threaded process.

Theoretical Alignment

A significant advantage of RRB is its solid mathematical foundation. Experimental results closely match the theoretical root-mean-square error (RMSE) curves, providing researchers with reliable confidence in the estimated centrality values.

RMSE vs. Centrality compared to theoretical bounds.

Implementation Simplicity

One of the most striking findings is the algorithm's simplicity. RRB can be implemented in roughly 30 lines of code using standard BFS libraries, avoiding the complex data structures required by methods like HyperBall. Additionally, it is highly space-efficient, requiring only $O(n \log n)$ additional memory beyond the graph itself.

Conclusion and Future Work

The Random-Radius Ball method provides a powerful new tool for large-scale network analysis. While it is particularly effective for identifying high-centrality nodes, achieving high relative accuracy for low-centrality nodes requires more computation. Future research could explore the application of RRB to weighted graphs using Dijkstra’s algorithm and further investigate how different graph topologies (e.g., social vs. web) influence the effectiveness of optimizations like the permutation-rank variant.

Summary updated

Abstract

In the analysis of real-world complex networks, identifying important vertices is one of the most fundamental operations. A variety of centrality measures have been proposed and extensively studied in various research areas. Many of distance-based centrality measures embrace some issues in treating disconnected networks, which are resolved by the recently emerged harmonic centrality. This paper focuses on a family of centrality measures including the harmonic centrality and its variants, and addresses their computational difficulty on very large graphs by presenting a new estimation algorithm named the random-radius ball (RRB) method. The RRB method is easy to implement, and a theoretical analysis, which includes the time complexity and error bounds, is also provided. The effectiveness of the RRB method over existing algorithms is demonstrated through experiments on real-world networks.
BibTeX
@inproceedings{inariba2017random,
  author = {Wataru Inariba and Takuya Akiba and Yuichi Yoshida},
  title = {{Random-Radius Ball Method for Estimating Closeness Centrality}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10498},
}
Figure