Koopman-Based Spectral Clustering of Directed and Time-Evolving Graphs

Stefan Klus*, Nataša Djurdjevac Conrad

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
22 Downloads (Pure)

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.

Original languageEnglish
Article number8
JournalJournal of Nonlinear Science
Volume33
Issue number1
Early online date7 Nov 2022
DOIs
Publication statusPublished - Feb 2023

Keywords

  • Coherent sets
  • Spectral clustering
  • Transfer operators

ASJC Scopus subject areas

  • Modelling and Simulation
  • Engineering(all)
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Koopman-Based Spectral Clustering of Directed and Time-Evolving Graphs'. Together they form a unique fingerprint.

Cite this