BGRAP: Balanced GRAph Partitioning Algorithm for Large Graphs

The definition of effective strategies for graph partitioning is a major challenge in distributed environments since an effective graph partitioning allows to considerably improve the performance of large graph data analytics computations. In this paper, we propose a multi-objective and scalable Balanced GRAph Partitioning (\algo) algorithm, based on Label Propagation (LP) approach, to produce balanced graph partitions. \algo defines a new efficient initialization procedure and different objective functions to deal with either vertex or edge balance constraints while considering edge direction in graphs. \algo is implemented of top of the open source distributed graph processing system Giraph. The experiments are performed on various graphs with different structures and sizes (going up to 50.6M vertices and 1.9B edges) while varying the number of partitions. We evaluate \algo using several quality measures and the computation time. The results show that \algo (i) provides a good balance while reducing the cuts between the different computed partitions (ii) reduces the global computation time, compared to LP-based algorithms.