Clusters in Markov chains via singular vectors of Laplacian matrices

DOI10.1016/J.LAA.2022.11.015MaRDI QIDQ2680586zbMATH OpenOpenAlexFDO

Authors Sam Cole, S. J. Kirkland

Publication date 4 January 2023

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.12658

zbMATH Keywords

clusterLaplacian matrixleft singular vectorMarkov chainstochastic matrix

Mathematics Subject Classification ID

Stochastic matrices (15B51) Computational methods in Markov chains (60J22) Numerical analysis or methods applied to Markov chains (65C40)

Abstract: Suppose that $T$ is a stochastic matrix. We propose an algorithm for identifying clusters in the Markov chain associated with $T$. The algorithm is recursive in nature, and in order to identify clusters, it uses the sign pattern of a left singular vector associated with the second smallest singular value of the Laplacian matrix $I-T.$ We prove a number of results that justify the algorithm's approach, and illustrate the algorithm's performance with several numerical examples.

Recommendations

• Clustering behaviour in Markov chains with eigenvalues close to one
• An SVD approach to identifying metastable states of Markov chains
• scientific article; zbMATH DE number 7233060
• On Clusters in Markov Chains
• Clustering in block Markov chains

Cites work

• A Google-like model of road network dynamics and its application to regulation and control
• An efficient and reliable algorithm for computing the singular subspace of a matrix, associated with its smallest singular values
• An SVD approach to identifying metastable states of Markov chains
• Clustering behaviour in Markov chains with eigenvalues close to one
• Google's PageRank and beyond. The science of search engine rankings
• scientific article; zbMATH DE number 3574935 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 2177236 (Why is no real title available?)
• Identification of almost invariant aggregates in reversible nearly uncoupled Markov chains
• Iterative algorithms for computing the singular subspace of a matrix associated with its smallest singular values
• On an SVD-based algorithm for identifying meta-stable states of Markov chains
• Robust Perron cluster analysis in conformation dynamics

Cited in

(6)

• Identification of almost invariant aggregates in reversible nearly uncoupled Markov chains
• Clustering behaviour in Markov chains with eigenvalues close to one
• Clustering in block Markov chains
• Graph Clustering Via a Discrete Uncoupling Process
• Oja's algorithm for graph clustering, Markov spectral decomposition, and risk sensitive control
• An SVD approach to identifying metastable states of Markov chains

This page was built for publication: Clusters in Markov chains via singular vectors of Laplacian matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2680586)