B-GRAP : Balanced GRAph Partitioning Algorithm for Large Graphs Article - Juin 2021

Adnan El Moussawi, Nacera Bennacer Seghouani, Francesca Bugiotti

Adnan El Moussawi, Nacera Bennacer Seghouani, Francesca Bugiotti, « B-GRAP : Balanced GRAph Partitioning Algorithm for Large Graphs  », Journal of Data Intelligence, juin 2021, pp. 116-135. ISSN 2577-610X

Abstract

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 (B-GRAP) algorithm, based on Label Propagation (LP) approach, to produce balanced graph partitions. B-GRAP 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. B-GRAP 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 B-GRAP using several quality measures and the computation time. The results show that B-GRAP (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.

Voir la notice complète sur HAL

Actualités