  In this paper, we propose DyPerm, the first dynamic community detection
method which optimizes a novel community scoring metric, called permanence.
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 leads 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
DyPerm achieves (on average) 35% gain in accuracy (based on NMI) compared to
the best method among four baseline methods. DyPerm also turns out to be 15
times faster than its static counterpart.
