Accelerating Louvain community detection algorithm on graphic processing unit
- PDF / 1,620,008 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 42 Downloads / 269 Views
Accelerating Louvain community detection algorithm on graphic processing unit Maryam Mohammadi1 · Mahmood Fazlali2 · Mehdi Hosseinzadeh3,4 Accepted: 4 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The Louvain community detection algorithm is a hierarchal clustering method categorized in the NP-hard problem. Its execution time to find communities in large graphs is, therefore, a challenge. Parallelization is an effective solution for amortizing Louvain’s execution time. In this paper, we propose an adaptive CUDA Louvain method (ACLM) algorithm that benefits from the graphic processing unit (GPU). ACLM uses the shared memory in GPU, as well as the optimal number of threads in the GPU blocks. These features minimize parallelization overhead and accelerate the calculation of modularity parameters. The proposed algorithm allocates threads to each block based on the number of required streaming multiprocessors (SMs) and warps on GPU. The implementation results show that ACLM can effectively accelerate the execution time by 77% compared to the competitive method in the large graph benchmarks. Keywords Louvain community detection · Parallel processing · Modularity · CUDA
* Mahmood Fazlali [email protected] Maryam Mohammadi [email protected] Mehdi Hosseinzadeh [email protected] 1
Department of Computer Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran
2
Department of Computer and Data Sciences, Faculty of Mathematical Sciences, Shahid Beheshti University, Tehran, Iran
3
Institute of Research and Development, Duy Tan University, Da Nang 550000, Vietnam
4
Mental Health Research Center, Psychosocial Health Research Institue, Iran University of Medical Sciences, Tehran, Iran
13
Vol.:(0123456789)
M. Mohammadi et al.
1 Introduction Community detection is an important task in analyzing and decomposing of a network (graph). The community detection in a network is characterized as the finding of clusters whose intra-edges are much denser than inter-edges [1]. Community detection in large networks is a time-consuming and computationally complex task due to the size variations and unavailability of the number of communities [2]. Modularity [3, 4] is a quality metric for the assessment of community detection algorithms. Modularity is the ratio of intra-edges of a community to the sum of inter-edges in a randomly distributed edge graph. A higher modularity value indicates a better quality for community detection. Blondel et al. [6] proposed to use a hierarchical clustering method in which the modularity (Q) is computed in each step of the algorithm. This method, which is known as Louvain in many commercial cyberspace applications, requires to perform an optimization on an NP-Hard problem to find the modularity [5]. To solve the computational complexity, several fast heuristic methods have been proposed for community detection in large-scale graphs. Parallelization is a suitable technique to reduce the algorithm’s exec
Data Loading...
