A Novel Evolutionary Clustering via the First-Order Varying Information for Dynamic Networks

Abstract

Temporal community detection could help us analyze and understand the meaningful substructure hidden within dynamic networks in the real world. Evolutionary clustering, as a popular framework for clustering stream data, has been denoted for mining the communities in dynamic networks. However, most of these methods ignore the varying characteristics of micro structure of the networks and lack of statistical interpretation. In this paper, we propose a powerful, interpretable and extensible evolutionary clustering framework based on nonnegative matrix factorization (NMF) for temporal community detection via combining the first-order varying information of micro structure in dynamic networks from the perspective of statistical model. Firstly, we consider the first-order varying information of nodes by constructing a temporal similarity matrix over time. Secondly, we present the framework, FVI-NMF, for detecting temporal community based on NMF combining the First-order Varying Information. Thirdly, we develop a effective algorithm to optimize the objective function of FVI-NMF and analyze its complexity. In addition, our model can discover the evolutionary pattern of temporal communities synchronously, which has a variety applications in the analysis of dynamic network. Experiments on both artificial and real dynamic networks demonstrate that our proposed framework has superior performance in comparison with state-of-art methods.

Publication
Physica A: Statistical Mechanics and its Applications