Distributed Algorithms for Random Walk Interpolated Betweenness Centralities

Abstract

Betweenness centrality quantifies a node's influence on information spread. While classical shortest-path metrics ignore path redundancy, random walk betweenness centrality considers all possible routes but over-emphasizes circuitous ones. To bridge these extremes, interpolated measures offer a tunable continuum between efficiency and randomness. In this paper, we propose a unified distributed framework for calculating interpolated betweenness centrality under the CONGEST model, where nodes have local knowledge and limited $O(\log n)$ bandwidth. Our framework accommodates different interpolation logics, such as path pruning and target biasing. By leveraging a parallelized randomized sampling mechanism to provide approximate estimations, our algorithm achieves a round complexity of $O(n \log n)$. Experimental results demonstrate the algorithm's scalability in distributed large-scale networks, showing that a satisfactory approximation ratio can be achieved given a sufficiently large sample size.