Parallelizing Louvain Algorithm: Distributed Memory Challenges
Authors:
- Naw Safrin SattarNSNaw Safrin Sattar
- Shaikh ArifuzzamanSAShaikh Arifuzzaman
- 1 August 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 695-701
Abstract
Louvain algorithm is a well-known and efficient method for detecting communities or clusters in social and information networks (graphs). The emergence of large network data necessitates parallelization of this algorithms for high performance computing platforms. There exist several shared-memory based parallel algorithms for Louvain method. However, those algorithms do not scale to a large number of cores and large networks. Distributed memory systems are widely available nowadays, which offer a large number of processing nodes. However, the existing only MPI (message passing interface) based distributed-memory parallel implementation of Louvain algorithm has shown scalability to only 16 processors. In this paper, we implement both shared- and distributed-memory based parallel algorithms and identify issues that hinder scalability. In our shared-memory based algorithm using OpenMP, we get 4-fold speedup for several real-world networks. However, this speedup is limited only by the physical cores available to our system. We then design a distributed-memory based parallel algorithms using message passing interface. Our results demonstrate an scalability to a moderate number of processors. We also provide an empirical analysis that shows how communication overhead poses the most crucial threat for deisgning scalable parallel Louvain algorithm in a distributed-memory setting.Keywords
This publication has 12 references indexed in Scilit:
- Fast parallel community detection algorithm based on modularity2015
- A fast parallel algorithm for counting triangles in graphs using dynamic load balancing2015
- A Space-Efficient Parallel Algorithm for Counting Exact Triangles in Massive Networks2015
- Engineering Parallel Algorithms for Community Detection in Massive NetworksIEEE Transactions on Parallel and Distributed Systems, 2015
- Fast parallel algorithm for unfolding of communities in large graphs2014
- Community detection algorithms: a comparative analysis: invited presentation, extended abstract2009
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Near linear time algorithm to detect community structures in large-scale networksPhysical Review E, 2007
- Finding community structure in very large networksPhysical Review E, 2004
- Community structure in social and biological networksProceedings of the National Academy of Sciences of the United States of America, 2002