Clustering time-evolving networks using the spatiotemporal graph Laplacian

Area of Science:

• Graph theory
• Dynamical systems
• Network science

Background:

• Time-evolving graphs are crucial for modeling dynamic systems like social networks and traffic.
• Analyzing community structures in these dynamic graphs presents a significant challenge.
• Existing spectral clustering methods are primarily designed for static graphs.

Purpose of the Study:

• To generalize spectral clustering algorithms for dynamic graphs.
• To develop a framework for capturing the temporal evolution of clusters.
• To introduce and analyze the spectral properties of a spatiotemporal graph Laplacian.

Main Methods:

• Generalized spectral clustering using canonical correlation analysis.
• Defined and investigated the spectral properties of the spatiotemporal graph Laplacian.
• Connected concepts to dynamical systems theory via transfer operators.

Main Results:

• The proposed method effectively captures temporal cluster evolution.
• Demonstrated advantages over existing methods on benchmark graphs.
• The spatiotemporal graph Laplacian provides clear interpretations of cluster dynamics.

Conclusions:

• The spatiotemporal graph Laplacian is a powerful tool for analyzing time-evolving graph communities.
• This approach offers a robust method for understanding dynamic network structures.
• The framework is applicable to both directed and undirected graphs.