GVE-Louvain: Fast Louvain 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 Louvain, 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 Louvain, which we term as GVE-Louvain, outperforms Vite, Grappolo, and NetworKit Louvain by 50x, 22x, and 20x 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.