References & Citations
Computer Science > Distributed, Parallel, and Cluster Computing
Title: GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting
(Submitted on 21 Dec 2023 (v1), last revised 26 Apr 2024 (this version, v6))
Abstract: Community detection is the problem of identifying natural divisions in networks. Efficient parallel algorithms for identifying such divisions is critical in a number of applications, where the size of datasets have reached significant scales. This technical report presents one of the most efficient parallel implementation of the Leiden algorithm, a high quality community detection method. On a server equipped with dual 16-core Intel Xeon Gold 6226R processors, our Leiden implementation, which we term as GVE-Leiden, outperforms the original Leiden, igraph Leiden, and NetworKit Leiden by 436x, 104x, and 8.2x respectively - achieving a processing rate of 403M edges/s on a 3.8B edge graph. Compared to GVE-Louvain, our parallel Louvain implementation, GVE-Leiden achieves a total elimination of disconnected communities, with only a 13% increase in runtime. In addition, GVE-Leiden improves performance at an average rate of 1.6x for every doubling of threads.
Submission history
From: Subhajit Sahu [view email][v1] Thu, 21 Dec 2023 15:30:53 GMT (2070kb,D)
[v2] Fri, 22 Dec 2023 12:10:37 GMT (1516kb,D)
[v3] Mon, 11 Mar 2024 17:49:14 GMT (1564kb,D)
[v4] Tue, 12 Mar 2024 14:18:43 GMT (1564kb,D)
[v5] Thu, 28 Mar 2024 10:23:23 GMT (1563kb,D)
[v6] Fri, 26 Apr 2024 08:18:03 GMT (1564kb,D)
Link back to: arXiv, form interface, contact.