DyPerm: Maximizing Permanence for Dynamic Community Detection

In this paper, we propose \(\mathsf {DyPerm}\), the first dynamic community detection method which optimizes a novel community scoring metric, called permanence. \(\mathsf {DyPerm}\) incrementally modifies the community structure by updating those communities where the editing of nodes and edges has been performed, keeping the rest of the network unchanged. We present strong theoretical guarantees to show how/why mere updates on the existing community structure lead to permanence maximization in dynamic networks, which in turn decreases the computational complexity drastically. Experiments on both synthetic and six real-world networks with given ground-truth community structure show that \(\mathsf {DyPerm}\) achieves (on average) 35% gain in accuracy (based on NMI) compared to the best method among four baseline methods. \(\mathsf {DyPerm}\) also turns out to be 15 times faster than its static counterpart.