Structural and Functional Discovery in Dynamic Networks with Non-negative Matrix Factorization

Abstract

Time series of graphs are increasingly prevalent in modern data and pose unique challenges to visual exploration and pattern extraction. This paper describes the development and application of matrix factorizations for exploration and time-varying community detection in time-evolving graph sequences. The matrix factorization model allows the user to home in on and display interesting, underlying structure and its evolution over time. The methods are scalable to weighted networks with a large number of time points or nodes, and can accommodate sudden changes to graph topology. Our techniques are demonstrated with several dynamic graph series from both synthetic and real world data, including citation and trade networks. These examples illustrate how users can steer the techniques and combine them with existing methods to discover and display meaningful patterns in sizable graphs over many time points.

16 pages, 17 figures

References in corpus (8)

• Power-law distributions in empirical data
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Resolution limit in community detection
• Spectral clustering and the high-dimensional stochastic blockmodel
• An efficient and principled method for detecting communities in networks
• Bi-cross-validation of the SVD and the nonnegative matrix factorization
• Large-scale structure of time evolving citation networks

Cited by in corpus (4)

• Joint community and anomaly tracking in dynamic networks
• Community detection in multiplex networks based on orthogonal nonnegative matrix tri-factorization
• A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging
• Analysis of multiview legislative networks with structured matrix factorization: Does Twitter influence translate to the real world?