A Parallel Algorithm for Computing Betweenness Centrality

In this paper we present a multi-grained parallel algorithm for computing betweenness centrality, which is extensively used in large-scale network analysis. Our method is based on a novel algorithmic handling of access conflicts for a CREW PRAM algorithm. We propose a proper data-processor mapping, a novel edge-numbering strategy and a new triple array data structure recording the shortest path for eliminating conflicts to access the shared memory. The algorithm requires O(n+m) space and O((nm)/p) ( or O((nm+n²logn)/p)) time for unweighted (or weighted) graphs, and it is a work-optimal CREW PRAM algorithm. On current multi-core platforms, our algorithm outperforms the previous algorithm by 2-3 times.