Abstract
Community detection is the problem of identifying natural divisions in networks. Efficient parallel algorithms for this purpose are crucial in various applications, particularly as datasets grow to substantial scales. This paper presents an optimized parallel implementation of the Label Propagation Algorithm (LPA), a high speed community detection method, for shared memory multicore systems. On a server equipped with dual 16-core Intel Xeon Gold 6226R processors, our LPA, which we term as GVE-LPA, outperforms FLPA and NetworKit LPA by 139× and 40× respectively — achieving a processing rate of 1.4B edges/s on a 3.8B edge graph. In addition, GVE-LPA scales at a rate of 1.7× every doubling of threads. To address the issue of internally-disconnected communities with GVE-LPA, we split the obtained communities with a parallel BFS-based approach. The resulting implementation, which we refer to as GSL-LPA, continues to outperform the above mentioned state-of-the-art implementations, which scaling at a rate of 1.6× for every doubling of threads.