PCCMerge: a parallel method based on merging partial connected components in large graphs

Graphs are fundamental data structures used in a wide range of fields, from social networks to bioinformatics. Their flexibility and ability to model complex data make them an indispensable tool for solving a wide range of problems. However, the use of graphs poses challenges, in particular the management of large amounts of data, which complicates and increases the analysis load in terms of computational power, memory and storage. This paper addresses the computation of a connected components, which are often used to understand the connectivity structure of a graph. This paper proposes a novel parallel approach to perform this computation. It takes advantage of a cluster computing engine and a graph processing library running locally on each node of the cluster. We also present an incremental approach to computing these components. We demonstrate the efficiency of our approach in a real biological use case, where our approach can be up to 4x faster than the label propagation algorithm implemented on a state-of-the-art cluster computing engine. This performance gain is mainly due to a reduction in the amount of data shuffling.