Home GVE-LPA and GSL-LPA: High-speed and internally-connected label propagation on multicore systems

Publications

GVE-LPA and GSL-LPA: High-speed and internally-connected label propagation on multicore systems

Author : Dr Subhajit Sahu

Year : 2026

Publisher : Elsevier B.V.

Source Title : Future Generation Computer Systems

Document Type :

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.