A Starting Point for Dynamic Community Detection with Leiden Algorithm

Real-world graphs often evolve over time, making community or cluster detection a crucial task. In this technical report, we extend three dynamic approaches - Naive-dynamic (ND), Delta-screening (DS), and Dynamic Frontier (DF) - to our multicore implementation of the Leiden algorithm, known for its high-quality community detection. Our experiments, conducted on a server with a 64-core AMD EPYC-7742 processor, show that ND, DS, and DF Leiden achieve average speedups of 1.37x, 1.47x, and 1.98x on large graphs with random batch updates, compared to the Static Leiden algorithm - while scaling at a rate of 1.6x for every doubling of threads. To our knowledge, this is the first attempt to apply dynamic approaches to the Leiden algorithm. We hope these early results pave the way for further development of dynamic approaches for evolving graphs.