LD-Leiden: Local Parallel Community Detection in Large Dynamic Networks
For practitioners needing high-quality community detection on large dynamic networks, LD-Leiden offers a fast, scalable solution that maintains Leiden's pipeline and modularity quality.
LD-Leiden is a local dynamic community detection method that updates modularity partitions after edge batches by repairing only affected regions, achieving 48.77x speedup over warm-started Leidenalg on graphs up to 3.30B edges while preserving 0.996 final modularity ratio.
Dynamic community detection must update high-quality modularity partitions after edge batches, yet full Leiden reruns make small changes scale with the whole snapshot. Existing dynamic methods reduce work but often alter Leiden refinement, keep limited hierarchy state, or restrict graph support. This paper presents LD-Leiden, a local dynamic Leiden method for weighted directed and undirected graphs that preserves the move-refine-aggregate pipeline and updates only repaired affected regions. Its novelty is the combination of an affected-frontier rule after statistic repair, exact subtract-add aggregate repair, and conflict-filtered parallel local moves; together these mechanisms bound update cost by the visited frontier rather than the full graph. On real streams and streamed static graphs with up to 214M vertices and 3.30B edges, LD-Leiden is 48.77x faster than warm-started Leidenalg in 100-batch runs while preserving a 0.996 final modularity ratio. On the common undirected benchmark set, it is 6.94x faster than DF-Leiden and 9.73x faster than NetworKit while obtaining higher final modularity; synthetic sequences support the predicted local edge-volume scaling.