Home GVE-LPA: Fast Label Propagation Algorithm (LPA) for Community Detection in the Shared Memory Setting

Publications

GVE-LPA: Fast Label Propagation Algorithm (LPA) for Community Detection in the Shared Memory Setting

Author : Dr Subhajit Sahu

Year : 2025

Publisher : Springer Science and Business Media Deutschland GmbH

Source Title : Lecture Notes in Computer Science

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, igraph LPA, and NetworKit LPA by 139×, 97000×, 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.