$ν$-LPA: Fast GPU-based Label Propagation Algorithm (LPA) for Community Detection
Author:
Preprint
Abstract
Community detection is the problem of identifying natural divisions in networks. Efficient parallel algorithms for identifying such divisions are critical in a number of applications. This report presents an optimized implementation of the Label Propagation Algorithm (LPA) for community detection, featuring an asynchronous LPA with a Pick-Less (PL) method every 4 iterations to handle community swaps, ideal for SIMT hardware like GPUs. It also introduces a novel per-vertex hashtable with hybrid quadratic-double probing for collision resolution. On an NVIDIA A100 GPU, our implementation, $\nu$-LPA, outperforms FLPA, NetworKit LPA, and GVE-LPA by 364x, 62x, and 2.6x, respectively, on a server with dual 16-core Intel Xeon Gold 6226R processors - processing 3.0B edges/s on a 2.2B edge graph - and achieves 4.7% higher modularity than FLPA, but 6.1% and 2.2% lower than NetworKit LPA and GVE-LPA.Keywords
All Related Versions
This publication has 33 references indexed in Scilit:
- GVE-LPA: Fast Label Propagation Algorithm (LPA) for Community Detection in the Shared Memory Setting2025
- Large-scale community detection based on core node and layer-by-layer label propagationInformation Sciences, 2023
- PLDLS: A novel parallel label diffusion and label Selection-based community detection algorithm based on Spark in social networksExpert Systems with Applications, 2021
- DHLP 1&2: Giraph based distributed label propagation algorithms on heterogeneous drug-related networksExpert Systems with Applications, 2020
- A coarsening method for bipartite networks via weight-constrained label propagationKnowledge-Based Systems, 2020
- A three-stage algorithm on community detection in social networksKnowledge-Based Systems, 2020
- PSPLPA: Probability and similarity based parallel label propagation algorithm on sparkPhysica A: Statistical Mechanics and its Applications, 2018
- A spreading activation-based label propagation algorithm for overlapping community detection in dynamic social networksData & Knowledge Engineering, 2018
- A scalable method for link prediction in large real world networksJournal of Parallel and Distributed Computing, 2017
- Label propagation algorithm for community detection based on node importance and label influencePhysics Letters A, 2017