GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting

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 436x, 104x, and 8.2x respectively - achieving a processing rate of 403 M edges/s on a 3.8 B edge graph. Compared to GVE-Louvain, our parallel Louvain implementation, GVE-Leiden achieves a total elimination of disconnected communities, with only a 13% increase in runtime. In addition, GVE-Leiden improves performance at an average rate of 1.6x for every doubling of threads.