GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911016805203968 |
|---|---|
| author | Sahu, Subhajit |
| author_facet | Sahu, Subhajit |
| contents | 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 implementations 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, NetworKit Leiden, and cuGraph Leiden (running on NVIDIA A100 GPU) by 436x, 104x, 8.2x, and 3.0x respectively - achieving a processing rate of 403M edges/s on a 3.8B edge graph. In addition, GVE-Leiden improves performance at an average rate of 1.6x for every doubling of threads. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_13936 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting Sahu, Subhajit Distributed, Parallel, and Cluster Computing Performance G.2.2; I.5.3 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 implementations 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, NetworKit Leiden, and cuGraph Leiden (running on NVIDIA A100 GPU) by 436x, 104x, 8.2x, and 3.0x respectively - achieving a processing rate of 403M edges/s on a 3.8B edge graph. In addition, GVE-Leiden improves performance at an average rate of 1.6x for every doubling of threads. |
| title | GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting |
| topic | Distributed, Parallel, and Cluster Computing Performance G.2.2; I.5.3 |
| url | https://arxiv.org/abs/2312.13936 |