Clustering of Time-Varying Graphs Based on Temporal Label Smoothness
This work addresses clustering for dynamic data like social networks, but it is incremental as it builds on spectral clustering with a smoothness constraint.
The authors tackled the problem of node clustering in time-varying graphs by assuming smooth label changes over time, and they validated their method on synthetic and real-world datasets.
We propose a node clustering method for time-varying graphs based on the assumption that the cluster labels are changed smoothly over time. Clustering is one of the fundamental tasks in many science and engineering fields including signal processing, machine learning, and data mining. Although most existing studies focus on the clustering of nodes in static graphs, we often encounter time-varying graphs for time-series data, e.g., social networks, brain functional connectivity, and point clouds. In this paper, we formulate a node clustering of time-varying graphs as an optimization problem based on spectral clustering, with a smoothness constraint of the node labels. We solve the problem with a primal-dual splitting algorithm. Experiments on synthetic and real-world time-varying graphs are performed to validate the effectiveness of the proposed approach.