Efficient Tracking of Communities on Evolving Graphs with Leiden Algorithm

Community detection, or clustering, identifies groups of nodes in a graph that are more densely connected to each other than to the rest of the network. The Leiden algorithm, which improves upon the Louvain algorithm, efficiently detects high-quality communities in large networks. Yet, given the size and dynamic nature of real-world graphs, efficient dynamic community detection algorithms capable of tracking community evolution over time are crucial. However, existing algorithms based on Leiden are inefficient and lack support for tracking evolving communities. This paper introduces parallel Naive-dynamic (ND), Delta-screening (DS), and Dynamic Frontier (DF) Leiden algorithms that efficiently track communities over time.