427
Distributively Computing Random Walk Betweenness Centrality in Linear Time
Qiang-Sheng Hua, Ming Ai, Hai Jin, Dongxiao Yu and Xuanhua Shi
Huazhong University of Science and Technology, Huazhong University of Science and Technology, Huazhong University of Science and Technology, Huazhong University of Science and Technology, Huazhong University of Science and Technology

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 nodes 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 CON GEST 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 CON GEST 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.