Home Shared-Memory Parallel Dynamic Louvain Algorithm for Community Detection

Publications

Shared-Memory Parallel Dynamic Louvain Algorithm for Community Detection

Author : Dr Subhajit Sahu

Year : 2024

Publisher : Institute of Electrical and Electronics Engineers Inc.

Source Title : 2024 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2024

Document Type :

Abstract

Community detection refers to the identification of coherent partitions in networks. In this poster, we present a parallel dynamic Louvain algorithm that finds communities in rapidly evolving graphs. Given a batch update of edge deletions or insertions, our algorithm identifies an approximate set of affected vertices in the graph with minimal overhead and updates the community membership of each vertex. This process repeats until convergence. Our approach achieves a mean speedup of 7.3 ×, compared to our parallel and optimized implementation of Δ-screening combined with Louvain, a recently proposed state-of-the-art approach.