Scalable Community Detection with the Louvain Algorithm
Citations Over TimeTop 10% of 2015 papers
Abstract
In this paper we present and evaluate a parallel community detection algorithm derived from the state-of-the-art Louvain modularity maximization method. Our algorithm adopts a novel graph mapping and data representation, and relies on can efficient communication runtime, specifically designed for fine-grained applications executed on large-scale supercomputers. We have been able to parallelize graphs with up to 138 billion edges on 8, 192 Blue Gene/Q nodes and 1, 024 P7-IH nodes. Leveraging the convergence properties of our algorithm and the efficient implementation, we can analyze communities of large scale graphs in just a few seconds. To the best of our knowledge, this is the first parallel implementation of the Louvain algorithm that scales to these large data and processor configurations.
Related Papers
- → Parallel Algorithms for Approximate String Matching with k Mismatches on CUDA(2012)20 cited
- → Pipelined data parallel algorithms---concept and modeling(1988)15 cited
- → A scalability metric for algorithm-machine on NOW and MPP(2000)2 cited
- → A fast algorithm for parallel computation of multibody dynamics on MIMD parallel architectures(1993)7 cited
- An N-body Tree Algorithm for the Cray T3D(1996)