Progression Analysis of Community Strengths in Dynamic Networks

Community formation analysis of dynamic networks has been a hot topic in data mining which has attracted much attention. Recently, there are many studies which focus on discovering communities successively from each snapshot by considering both current and historical information. However, the detected communities are isolated at a certain snapshot, because these approaches ignore important historical or successive information. Different from previous studies which focus on community detection in dynamic networks, we define a new problem of tracking the progression of the community strength - a novel measure that reflects the community robustness and coherence throughout the entire observation period. The proposed community strength analysis provides significant insights into entity properties and relationships in a wide variety of applications. To tackle this problem, we propose a novel two-stage framework: we first identify communities via non-negative matrix factorization, and then calculate the strength of each detected community corresponding to each specific snapshot by solving an optimization problem. Experimental results show that the proposed approach is highly effective in discovering the progression of community strengths and detecting interesting communities.