G-PCCA: Spectral Clustering for Non-reversible Markov Chains

Please always quote using this URN: urn:nbn:de:0297-zib-55505
  • Spectral clustering methods are based on solving eigenvalue problems for the identification of clusters, e.g., the identification of metastable subsets of a Markov chain. Usually, real-valued eigenvectors are mandatory for this type of algorithms. The Perron Cluster Analysis (PCCA+) is a well-known spectral clustering method of Markov chains. It is applicable for reversible Markov chains, because reversibility implies a real-valued spectrum. We extend this spectral clustering method also to non-reversible Markov chains and give some illustrative examples. The main idea is to replace the eigenvalue problem by a real-valued Schur decomposition. By this extension, non-reversible Markov chains can be analyzed. Furthermore, the chains need not have a positive stationary distribution. And additionally to metastabilities, dominant cycles and sinks can be identified, too.

Download full text files

Export metadata

Metadaten
Author:Marcus Weber, Konstantin Fackeldey
Document Type:ZIB-Report
Year of first publication:2015
Series (Serial Number):ZIB-Report (15-35)