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 an optimized parallel implementation of Leiden, a high quality community detection method, for shared memory multicore systems. 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, and NetworKit Leiden by 373x, 86x, and 7.2x respectively - achieving a processing rate of 352M edges/s on a 3.8B edge graph. Compared to GVE-Louvain, our parallel Louvain implementation, GVE-Leiden achieves an 11x reduction in disconnected communities, with only a 36% increase in runtime. In addition, GVE-Leiden improves performance at an average rate of 1.6x for every doubling of threads.
翻译:暂无翻译