Targeted revision: A learning-based approach for incremental community detection in dynamic networks

Community detection is a fundamental task in network analysis. Applications on massive dynamic networks require more efficient solutions and lead to incremental community detection, which revises the community assignments of new or changed vertices during network updates. In this paper, we propose to use machine learning classifiers to predict the vertices that need to be inspected for community assignment revision. This learning-based targeted revision (LBTR) approach aims to improve community detection efficiency by filtering out the unchanged vertices from unnecessary processing. In this paper, we design features that can be used for efficient target classification and analyze the time complexity of our framework. We conduct experiments on two real-world datasets, which show our LBTR approach significantly reduces the computational time while keeping a high community detection quality. Furthermore, as compared with the benchmarks, we find our approach’s performance is stable on both growing networks and networks with vertex/edge removals. Experiments suggest that one should increase the target classification precision while keeping recall at a reasonable level when implementing our proposed approach. The study provides a unique perspective in incremental community detection.