LD-Leiden cuts community detection time 48x on graphs with 3.3B edges

Community detection in large dynamic networks faces a fundamental tension: full reruns of algorithms like Leiden scale with the entire graph, even for tiny edge changes. A new paper from Grigoriy Bokov and colleagues introduces LD-Leiden, a local dynamic variant that only recalculates communities in regions affected by each batch of edge updates. The algorithm preserves Leiden's full move-refine-aggregate pipeline but applies three key innovations: an affected-frontier rule to identify changed neighborhoods, exact subtract-add aggregate repair to keep modularity scores correct, and conflict-filtered parallel local moves to enable safe concurrent updates.

On real-world streaming graphs and streamed static graphs with up to 214 million vertices and 3.30 billion edges, LD-Leiden achieves a 48.77x speedup over warm-started Leidenalg across 100 batches while maintaining a 0.996 final modularity ratio. Against other dynamic community detection methods (DF-Leiden and NetworKit) on the common undirected benchmark set, it runs 6.94x and 9.73x faster respectively and obtains higher final modularity. The authors also validate theoretical scaling predictions with synthetic sequences. The code is available via the paper's open-source release.