Shared-Memory Parallel Dynamic Louvain Algorithm for Community Detection

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.