Dynamic Community Detection Algorithm Based on Incremental Identification

Abstract

Dynamic community detection algorithms try to solve problems that identify communities of dynamic network which consists of a series of network snapshots. To address this issue, here we propose a new dynamic community detection algorithm based on incremental identification according to a vertex-based metric called permanence. We incrementally analyze the community ownership of partial vertices, so as to avoid the reassignment of all the vertices in the network to their respective communities. In addition, we propose a new metrics called evolution strength to measure the error probably caused by incrementally assigning the community ownership or the abrupt change of network structure. The experiment results show that our proposed algorithm is able to identify the community structure in a network with a higher efficiency. Meanwhile, due to the lack of dynamic network data with ground-truth structure and limitation of existing synthetic methods, we propose a novel method for generating synthetic data of dynamic network with ground-truth structure, which defines evolution events and evolution rate of events, so as to get more realistic synthetic data.