References & Citations
Computer Science > Distributed, Parallel, and Cluster Computing
Title: An Approach for Addressing Internally-Disconnected Communities in Louvain Algorithm
(Submitted on 18 Feb 2024 (v1), last revised 29 Mar 2024 (this version, 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. In this technical report, we propose another approach to mitigate this issue. On a system with two 16-core Intel Xeon Gold 6226R processors, our new parallel algorithm GSP-Louvain, based on the Louvain algorithm, addresses this issue, and outperforms the original Leiden, igraph Leiden, and NetworKit Leiden by 341x, 83x, and 6.1x respectively - achieving a processing rate of 328M edges/s on a 3.8B edge graph. Furthermore, GSP-Louvain improves performance at a rate of 1.5x 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.