[month] [year]

APDCM-2024

Research on Shared-Memory Parallel Algorithms for Community Detection in Dynamic Graphs by Subhajit Sahu working with Prof. Kishore Kottapalli;  and Prof.  Dip Sankar Banerjee, Department of Computer Science and Engineering, Indian Institute of Technology Jodhpur (IIT Jodhpur) was awarded the APDCM Outstanding Paper award at 26th Workshop on Advances in Parallel and Distributed Computational Models  (APDCM) held from27 to 30 May at San Francisco, California held in conjunction with 38th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2024).

Here is the summary of their research work: Community detection is the problem of identifying natural divisions in networks. A relevant challenge in this problem is to find communities on rapidly evolving graphs. In this paper, we present our parallel Dynamic Frontier (DF) approach. Given a batch update of edge deletions or insertions, this approach incrementally identifies an approximate set of affected vertices in the graph with minimal overhead. We apply this approach to both Louvain, a high quality, and Label Propagation Algorithm (LPA), a fast static community detection algorithm. Our approach achieves a mean speedup of 7.3× and 6.7×, when applied to Louvain and LPA respectively, compared to our parallel and optimized implementation of ∆-screening, a recently proposed state-of-the-art approach. Finally, we show how to combine Louvain and LPA with the DF approach to arrive at a hybrid algorithm. This algorithm produces high quality communities while providing a speedup of 2.0× on top of DF-based Louvain.

Conference page: https://apdcm.iss-j.org/doku.php?id=apdcm2024

May 2024