Betweenness centrality is a metric to measure therelative importance of vertices within a graph. The computationof betweenness centrality is based on shortest paths whichrequires O(n+m) space and O(mn) and O(nm+n2 log n) timeon unweighted and weighted graphs, respectively. It is timeconsumingto deal with large-scale graphs, which motivatesus resort to distributed computing and parallel algorithms.In this paper, we design a vertex-based parallel algorithmfollowing the shortest path approach (SPBC