GVE-Louvain: Fast Louvain Algorithm for Community Detection in Shared Memory Setting
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909654755311616 |
|---|---|
| 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 multicore implementations of the Louvain algorithm, a high quality community detection method. On a server equipped with dual 16-core Intel Xeon Gold 6226R processors, our Louvain, which we term as GVE-Louvain, outperforms Vite, Grappolo, NetworKit Louvain, and cuGraph Louvain (running on NVIDIA A100 GPU) by 50x, 22x, 20x, and 5.8x faster respectively - achieving a processing rate of 560M edges/s on a 3.8B edge graph. In addition, GVE-Louvain improves performance at an average rate of 1.6x for every doubling of threads. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_04876 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | GVE-Louvain: Fast Louvain 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 multicore implementations of the Louvain algorithm, a high quality community detection method. On a server equipped with dual 16-core Intel Xeon Gold 6226R processors, our Louvain, which we term as GVE-Louvain, outperforms Vite, Grappolo, NetworKit Louvain, and cuGraph Louvain (running on NVIDIA A100 GPU) by 50x, 22x, 20x, and 5.8x faster respectively - achieving a processing rate of 560M edges/s on a 3.8B edge graph. In addition, GVE-Louvain improves performance at an average rate of 1.6x for every doubling of threads. |
| title | GVE-Louvain: Fast Louvain 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.04876 |