Parallel Community Detection in Incremental Graphs

Abstract

The problem of community detection in large, expanding real-world networks presents significant challenges due to the scale and complexity of these networks. Traditional algorithms struggle to provide optimal solutions or require unviable computational resources. In this thesis, we address these challenges by exploring, designing and evaluating parallel computing strategies for community detection in incremental graphs. We provide a novel parallel implementation of the NCLiC algorithm by dividing its phases into parallel tasks using a shared memory approach. The algorithm has been extensively tested on various graphs. The results demonstrate promising performance improvements and scalability while retaining the quality of the partitions. The parallel implementation of the Leiden algorithm used for pre-clustering shows virtually no loss in modularity and obtained speedups up to a factor of 10.3. The refinement and merging phases of the parallel NCLiC algorithm obtained speedups up to 18.42 and 10.36, respectively, resulting in a total speedup of up to a factor of 6.73.