Clustering Time-Evolving Networks Using the Spatio-Temporal Graph Laplacian

Abstract

Time-evolving graphs arise frequently when modeling complex dynamical systems such as social networks, traffic flow, and biological processes. Developing techniques to identify and analyze communities in these time-varying graph structures is an important challenge. In this work, we generalize existing spectral clustering algorithms from static to dynamic graphs using canonical correlation analysis (CCA) to capture the temporal evolution of clusters. Based on this extended canonical correlation framework, we define the spatio-temporal graph Laplacian and investigate its spectral properties. We connect these concepts to dynamical systems theory via transfer operators, and illustrate the advantages of our method on benchmark graphs by comparison with existing methods. We show that the spatio-temporal graph Laplacian allows for a clear interpretation of cluster structure evolution over time for directed and undirected graphs.

References in corpus (19)

• Temporal Networks
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Structure and tie strengths in mobile communication networks
• Quantifying social group evolution
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Diffusion dynamics on multiplex networks
• Mapping change in large networks
• The backbone of the climate network
• Community Discovery in Dynamic Networks: a Survey
• Resilience and efficiency in transportation networks
• Spectral properties of the Laplacian of multiplex networks
• Transport in time-dependent dynamical systems: Finite-time coherent sets
• An analytic framework for identifying finite-time coherent sets in time-dependent dynamical systems
• Understanding the geometry of transport: diffusion maps for Lagrangian trajectory data unravel coherent sets
• Set-based corral control in stochastic dynamical systems: Making almost invariant sets more invariant
• Kernel methods for detecting coherent structures in dynamical data
• Koopman-based spectral clustering of directed and time-evolving graphs
• Transfer operators on graphs: Spectral clustering and beyond
• Dynamical systems and complex networks: A Koopman operator perspective