Clustering of Time-Varying Graphs Based on Temporal Label Smoothness
Katsuki Fukumoto Koki Yamada Yuichi Tanaka Hoi-To Wai
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.