JUCS - Journal of Universal Computer Science 28(2): 160-180, doi: 10.3897/jucs.80688
A Spark Parallel Betweenness Centrality Computation and its Application to Community Detection Problems
expand article infoDaniel Gomez González, Luis Liana Díaz, Cristóbal Pareja
‡ Complutense University of Madrid, Madrid, Spain
Open Access
Abstract

The Brandes algorithm has the lowest computational complexity for computing the betweenness centrality measures of all nodes or edges in a given graph. Its numerous applications make it one of the most used algorithms in social network analysis. In this work, we provide a parallel version of the algorithm implemented in Spark. The experimental results show that the parallel algorithm scales as the number of cores increases. Finally, we provide a version of the well-known community detection Girvan-Newman algorithm, based on the Spark version of Brandes algorithm.

Keywords
Spark, MapReduce, Social Network Analysis, Centrality measure, Brandes Algorithm, distributed programming