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 one of the most efficient parallel implementation 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, and NetworKit Leiden by 436x, 104x, and 8.2x respectively - achieving a processing rate of 403M edges/s on a 3.8B 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.