Neighborhood-Based Dynamic Community Detection with Graph Transform for 0-1 Observed Networks

摘要

Dynamic complex social network is always mixed with noisy data. It is important to discover and model community structure for understanding real social network and predicting its evolution. In this paper, we propose a novel algorithm NDCD (Neighborhood-based Dynamic Community Detection with graph transform for 0-1 observed networks) to discover dynamic community structure in unweighted networks. It first calculates nodes' shared neighborhood relationship in a snapshot network and deduces the weighted directed graph; then computes both historic information and current information and deduces updated weighted undirected graphs. A greedy algorithm is designed to find the community structure snapshot at each time step. One evaluation formula is proposed to measure the community similarity. Based on this evaluation, the latent communities can be found. Experiments on both synthetic and real datasets demonstrate that our algorithm not only discovers the real community structure but also eliminates the influence of noisy data for better understanding of real network structure and its evolution.