Today, online social networks have millions of users, and continue growing up. For that reason, the graphs generated from these networks usually do not fit into a single machine's memory and the time required for its processing is very large. In particular, to compute a centrality measure like betweenness could be expensive on those graphs. To address this challenge, in this paper we present a parallel and distributed algorithm to compute betweenness. Also, we develop a heuristic to reduce the overall time, which accomplish a speedup over 80x in the best of cases.