An Approach for Addressing Internally-Disconnected Communities in Louvain Algorithm
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912065610842112 |
|---|---|
| author | Sahu, Subhajit |
| author_facet | Sahu, Subhajit |
| contents | Community detection is the problem of identifying densely connected clusters within a network. While the Louvain algorithm is commonly used for this task, it can produce internally-disconnected communities. To address this, the Leiden algorithm was introduced. This technical report introduces GSP-Louvain, a parallel algorithm based on Louvain, which mitigates this issue. Running on a system with two 16-core Intel Xeon Gold 6226R processors, GSP-Louvain outperforms Leiden, NetworKit Leiden, and cuGraph Leiden by 391x, 6.9x, and 2.6x respectively, processing 410M edges per second on a 3.8B edge graph. Furthermore, GSP-Louvain improves performance at a rate of 1.5x for every doubling of threads. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_11454 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Approach for Addressing Internally-Disconnected Communities in Louvain Algorithm Sahu, Subhajit Distributed, Parallel, and Cluster Computing Social and Information Networks G.2.2; I.5.3 Community detection is the problem of identifying densely connected clusters within a network. While the Louvain algorithm is commonly used for this task, it can produce internally-disconnected communities. To address this, the Leiden algorithm was introduced. This technical report introduces GSP-Louvain, a parallel algorithm based on Louvain, which mitigates this issue. Running on a system with two 16-core Intel Xeon Gold 6226R processors, GSP-Louvain outperforms Leiden, NetworKit Leiden, and cuGraph Leiden by 391x, 6.9x, and 2.6x respectively, processing 410M edges per second on a 3.8B edge graph. Furthermore, GSP-Louvain improves performance at a rate of 1.5x for every doubling of threads. |
| title | An Approach for Addressing Internally-Disconnected Communities in Louvain Algorithm |
| topic | Distributed, Parallel, and Cluster Computing Social and Information Networks G.2.2; I.5.3 |
| url | https://arxiv.org/abs/2402.11454 |