Koopman-based spectral clustering of directed and time-evolving graphs
arXiv:2204.02951 · doi:10.1007/s00332-022-09863-0
Abstract
While spectral clustering algorithms for undirected graphs are well established and have been successfully applied to unsupervised machine learning problems ranging from image segmentation and genome sequencing to signal processing and social network analysis, clustering directed graphs remains notoriously difficult. Two of the main challenges are that the eigenvalues and eigenvectors of graph Laplacians associated with directed graphs are in general complex-valued and that there is no universally accepted definition of clusters in directed graphs. We first exploit relationships between the graph Laplacian and transfer operators and in particular between clusters in undirected graphs and metastable sets in stochastic dynamical systems and then use a generalization of the notion of metastability to derive clustering algorithms for directed and time-evolving graphs. The resulting clusters can be interpreted as coherent sets, which play an important role in the analysis of transport and mixing processes in fluid flows.
References in corpus (20)
- The structure and dynamics of multilayer networks
- Structure and tie strengths in mobile communication networks
- A Data-Driven Approximation of the Koopman Operator: Extending Dynamic Mode Decomposition
- Applied Koopmanism
- Random walks and diffusion on networks
- Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys
- Clustering and Community Detection in Directed Networks: A Survey
- Extended dynamic mode decomposition with dictionary learning: a data-driven adaptive spectral decomposition of the Koopman operator
- Data-driven model reduction and transfer operator approximation
- On the numerical approximation of the Perron-Frobenius and Koopman operator
- An analytic framework for identifying finite-time coherent sets in time-dependent dynamical systems
- Eigendecompositions of Transfer Operators in Reproducing Kernel Hilbert Spaces
- Understanding the geometry of transport: diffusion maps for Lagrangian trajectory data unravel coherent sets
- Sparse eigenbasis approximation: multiple feature extraction across spatiotemporal scales with application to coherent set identification
- Optimal data-driven estimation of generalized Markov state models for non-equilibrium dynamics
- A kernel-based approach to molecular conformation analysis
- Kernel methods for detecting coherent structures in dynamical data
- Koopman analysis of quantum systems
- Random walk on temporal networks with lasting edges
- A Dynamic Mode Decomposition Approach for Decentralized Spectral Clustering of Graphs