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]$.
- 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.
- 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.
- 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.
- 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.
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.
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