Transfer operators on graphs: Spectral clustering and beyond

Stefan Klus*, Maia Trower

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Downloads (Pure)

Abstract

Graphs and networks play an important role in modeling and analyzing complex interconnected systems such as transportation networks, integrated circuits, power grids, citation graphs, and biological and artificial neural networks. Graph clustering algorithms can be used to detect groups of strongly connected vertices and to derive coarse-grained models. We define transfer operators such as the Koopman operator and the Perron-Frobenius operator on graphs, study their spectral properties, introduce Galerkin projections of these operators, and illustrate how reduced representations can be estimated from data. In particular, we show that spectral clustering of undirected graphs can be interpreted in terms of eigenfunctions of the Koopman operator and propose novel clustering algorithms for directed graphs based on generalized transfer operators. We demonstrate the efficacy of the resulting algorithms on several benchmark problems and provide different interpretations of clusters.

Original languageEnglish
Article number015014
JournalJournal of Physics: Complexity
Volume5
Issue number1
Early online date23 Feb 2024
DOIs
Publication statusPublished - Mar 2024

Keywords

  • directed graphs
  • Galerkin approximation
  • spectral clustering
  • transfer operator theory

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computer Networks and Communications
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Transfer operators on graphs: Spectral clustering and beyond'. Together they form a unique fingerprint.

Cite this