Fast parallel community detection algorithm based on modularity
Authors:
- 1 October 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-4
Abstract
In recent years, detecting dense sub-graphs that are known as communities in massive graphs has been a common issue in different fields of science. It provides the facility of studying complex graphs by simplifying them through utilizing communities. Due to ceaseless increases in graph size that are used in social networks (with billions of nodes and edges), algorithm execution time is an important factor for detecting communities. To cope with this problem, a new parallel community detection algorithm is presented in this paper. The main idea behind the proposed method is to assign parallel threads for the calculation of adding qualified neighbor nodes to the community. Proposed algorithm is tested using a general PC (IntelCorei7, 4 GByte). It leads to abating the algorithm execution time from 25% to 78% compared to the fastest previous parallel algorithms.Keywords
This publication has 17 references indexed in Scilit:
- A fast parallel modularity optimization algorithm (FPMQA) for community detection in online social networkKnowledge-Based Systems, 2013
- A Template for Parallelizing the Louvain Method for Modularity Maximization2013
- Hierarchical Parallel Algorithm for Modularity-Based Community Detection Using GPUs2013
- An improved bit parallel exact maximum clique algorithmOptimization Letters, 2011
- Multilevel local search algorithms for modularity clusteringACM Journal of Experimental Algorithmics, 2011
- Community detection in graphsPhysics Reports, 2010
- Graph clusteringComputer Science Review, 2007
- Cluster analysis of networks generated through homology: automatic identification of important protein communities involved in cancer metastasisBMC Bioinformatics, 2006
- Finding community structure in very large networksPhysical Review E, 2004
- The webgraph framework I2004