Parallel Overlapping Community Detection Algorithm on GPU
- 7 June 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Big Data
- Vol. 9 (2) , 677-687
Abstract
Community detection is one of the most representative graph mining applications, which is often assembled as a concurrent graph partition application to explore the maximum modularity (or gained modularity) of each community. However, many branch divergence operations create significant obstacles to unleashing GPU’s high throughput and memory bandwidth, which are needed in community detection applications to divide the vertices into different communities. In this paper, we present Lugger, a GPU-based overlapping community detection algorithm that reduces GPU’s branch divergence via the customer-designed cache-aware parallel searching technique. In Lugger, we first design a cache-aware parallel searching policy using the B-Tree structure. Then, we set the B-Tree node matches with the GPU cache line to meet the coalesced memory access manner and avoid the branch divergence in warps. Moreover, we design a positive node splitting scheme to reduce the lock operation and idle threads when building the B-Tree structure. In addition, we implement a warp-centric thread assignment strategy to make sure the workloads across threads are balanced. We implement the proposed algorithm on NVIDIA GPU and evaluate the performance on eight large graphs (up to $3M$ vertices and $117M$ edges) with ground-truth communities. The experimental results show that Lugger can outperform the state-of-the-art works on scalability and detection quality.
Keywords
Funding Information
- National Key R&D Program of China (2020AAA0108501)
- National Natural Science Foundation of China (61772218)
- Key R&D Program of Hubei (2020BAA020)
This publication has 39 references indexed in Scilit:
- Overlapping community detection in networksACM Computing Surveys, 2013
- A Markov random walk under constraint for discovering overlapping communities in complex networksJournal of Statistical Mechanics: Theory and Experiment, 2011
- Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levelsJournal of Statistical Mechanics: Theory and Experiment, 2011
- Finding overlapping communities in networks by label propagationNew Journal of Physics, 2010
- A survey of B-tree locking techniquesACM Transactions on Database Systems, 2010
- Link communities reveal multiscale complexity in networksNature, 2010
- Sequential algorithm for fast clique percolationPhysical Review E, 2008
- Weighted network modulesNew Journal of Physics, 2007
- Quantifying social group evolutionNature, 2007
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005