IncNSA: Detecting communities incrementally from time-evolving networks based on node similarity

Abstract

Many real-world systems can be abstracted as networks. As those systems always change dynamically in nature, the corresponding networks also evolve over time in general, and detecting communities from such time-evolving networks has become a critical task. In this paper, we propose an incremental detection method, which can stably detect high-quality community structures from time-evolving networks. When the network evolves from the previous snapshot to the current one, the proposed method only considers the community affiliations of partial nodes efficiently, which are either newborn nodes or some active nodes from the previous snapshot. Thus, the first phase of our method is determining active nodes that should be reassigned due to the change of their community affiliations in the evolution. Then, we construct subgraphs for these nodes to obtain the preliminary communities in the second phase. Finally, the final result can be obtained through optimizing the primary communities in the third phase. To test its performance, extensive experiments are conducted on both some synthetic networks and some real-world dynamic networks, the results show that our method can detect satisfactory community structure from each of snapshot graphs efficiently and steadily, and outperforms the competitors significantly.