Fast parallel algorithm for unfolding of communities in large graphs
Authors:
- 1 September 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Abstract
Detecting community structures in graphs is a well studied problem in graph data analytics. Unprecedented growth in graph structured data due to the development of the world wide web and social networks in the past decade emphasizes the need for fast graph data analytics techniques. In this paper we present a simple yet efficient approach to detect communities in large scale graphs by modifying the sequential Louvain algorithm for community detection. The proposed distributed memory parallel algorithm targets the costly first iteration of the initial method by parallelizing it. Experimental results on a MPI setup with 128 parallel processes shows that up to ≈5× performance improvement is achieved as compared to the sequential version while not compromising the correctness of the final result.Keywords
This publication has 17 references indexed in Scilit:
- Scalable parallel graph partitioning2013
- Engineering High-Performance Community Detection Heuristics for Massive Graphs2013
- A Template for Parallelizing the Louvain Method for Modularity Maximization2013
- Defining and evaluating network communities based on ground-truth2012
- Scalable Multi-threaded Community Detection in Social Networks2012
- Near linear time algorithm to detect community structures in large-scale networksPhysical Review E, 2007
- Modularity and community structure in networksProceedings of the National Academy of Sciences, 2006
- Parallel multilevel graph partitioning2002
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970
- Validity of the single processor approach to achieving large scale computing capabilities1967