Distributively Computing Random Walk Betweenness Centrality in Linear Time

Betweenness centrality of a node represents its influence over the spread of information in the network. It is normally defined as the ratio of the number of shortest paths passing through the node among all shortest paths. However, the spread of information may not just pass through the shortest paths which is captured by a new measure of betweenness centrality based on random walks [1]. The random walk betweenness centrality of a node means how often it is traversed by a random walk between all pairs of other nodes. In this paper, we propose an O(n log n) time distributed randomized approximation algorithm for calculating each node's random walk betweenness centrality with an approximation ratio (1-ϵ) where n is the number of nodes and ϵ is an arbitrarily small constant between 0 and 1. Our distributed algorithm is designed under the widely used CONGEST model, where each edge can only transfer O(log n) bits in each round. To our best knowledge, this is the first distributed algorithm for computing the random walk betweenness centrality. Moreover, we give a non-trivial lower bound for distributively computing the exact random walk betweenness centrality under the CONGEST model, which is Ω(n\log n +D) where D is the network diameter. This means exactly computing random walk betweenness cannot be done in sublinear time.