Spectral Clustering for Non-Reversible Markov Chains

  • 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 also extend this spectral clustering method 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 do not need to have a positive stationary distribution. In addition to metastabilities, dominant cycles and sinks can also be identified. This novel method is called GenPCCA (i.e., generalized PCCA), since it includes the case of non-reversible processes. We also apply the method to real-world eye-tracking data.
Metadaten
Author:Konstantin Fackeldey, Alexander Sikorski, Marcus Weber
Document Type:Article
Parent Title (English):Computational and Applied Mathematics
Volume:37
Issue:5
First Page:6376
Last Page:6391
Tag:GenPCCA; Markov chain; Non-reversible; Schur decomposition; Spectral clustering
Year of first publication:2018
Preprint:urn:nbn:de:0297-zib-70218
DOI:https://doi.org/https://doi.org/10.1007/s40314-018-0697-0