Detecting evolving communities in dynamic networks using graph regularized evolutionary nonnegative matrix factorization

Xiaoke Ma, Dongyuan Li, Shiyin Tan and Zhihao Huang

Physica A: Statistical Mechanics and its Applications, 2019, vol. 530, issue C

Abstract: Many networks in society and nature are dynamic, and identifying evolving communities in dynamic networks sheds light on revealing the structure and function of the overall systems. Evolutionary clustering is based on the temporal smoothness framework that simultaneously maximizes the clustering accuracy at the current time step and minimizes the clustering drift between two successive time steps. However, they are criticized for the linear combination of networks at two successive time steps because the relation between networks is unnecessary linear. To address this problem, we propose the Graph regularized Evolutionary Nonnegative Matrix Factorization algorithm (GrENMF) for the dynamic community detection, where the network at the previous time step is transformed as a regularizer into the objective function. Moreover, the local topological structure in the network at the previous time step is preserved in communities at the current time step, which improves the performance of algorithm without increasing the time complexity. Furthermore, we prove the equivalence among evolutionary nonnegative matrix factorization (ENMF), spectral clustering, kernel K-means, modularity density and GrENMF, which serves as the theoretical foundation for the GrENMF algorithm. The experimental results over a number of artificial and real world dynamic networks illustrate that the proposed method is not only more accurate, but also more robust than state-of-the-art approaches.

Keywords: Dynamic networks; Community; Evolutionary clustering; Nonnegative matrix factorization; Graph regularization (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437119307459
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:530:y:2019:i:c:s0378437119307459

DOI: 10.1016/j.physa.2019.121279

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().