References & Citations
Computer Science > Distributed, Parallel, and Cluster Computing
Title: Addressing Internally-Disconnected Communities in Leiden and Louvain Community Detection Algorithms
(Submitted on 18 Feb 2024 (this version), latest version 29 Mar 2024 (v4))
Abstract: Community detection is the problem of identifying densely connected clusters of nodes within a network. The Louvain algorithm is a widely used method for this task, but it can produce communities that are internally disconnected. To address this, the Leiden algorithm was introduced. However, our analysis and empirical observations indicate that the Leiden algorithm still identifies disconnected communities, albeit to a lesser extent. To mitigate this issue, we propose two new parallel algorithms: GSP-Leiden and GSP-Louvain, based on the Leiden and Louvain algorithms, respectively. On a system with two 16-core Intel Xeon Gold 6226R processors, we demonstrate that GSP-Leiden/GSP-Louvain not only address this issue, but also outperform the original Leiden, igraph Leiden, and NetworKit Leiden by 373x/473x, 86x/186x, and 7.2x/17.2x respectively - achieving a processing rate of 352M/652M edges/s on a 3.8B edge graph. Furthermore, GSP-Leiden/GSP-Louvain improve performance at a rate of 1.6x/1.7x for every doubling of threads.
Submission history
From: Subhajit Sahu [view email][v1] Sun, 18 Feb 2024 04:35:27 GMT (1909kb,D)
[v2] Tue, 20 Feb 2024 14:16:21 GMT (1909kb,D)
[v3] Thu, 28 Mar 2024 13:05:14 GMT (1894kb,D)
[v4] Fri, 29 Mar 2024 03:00:12 GMT (1894kb,D)
Link back to: arXiv, form interface, contact.