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.
Author: | Marcus Weber, Konstantin FackeldeyORCiD |
---|---|
Document Type: | ZIB-Report |
Year of first publication: | 2015 |
Series (Serial Number): | ZIB-Report (15-35) |