Clustering in block Markov chains
From MaRDI portal
Publication:1996780
clusteringcommunity detectionMarkov chainsasymptotic analysischange of measureinformation theorymixing times
Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Statistical aspects of information-theoretic topics (62B10) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)
Abstract: This paper considers cluster detection in Block Markov Chains (BMCs). These Markov chains are characterized by a block structure in their transition matrix. More precisely, the possible states are divided into a finite number of groups or clusters, such that states in the same cluster exhibit the same transition rates to other states. One observes a trajectory of the Markov chain, and the objective is to recover, from this observation only, the (initially unknown) clusters. In this paper we devise a clustering procedure that accurately, efficiently, and provably detects the clusters. We first derive a fundamental information-theoretical lower bound on the detection error rate satisfied under any clustering algorithm. This bound identifies the parameters of the BMC, and trajectory lengths, for which it is possible to accurately detect the clusters. We next develop two clustering algorithms that can together accurately recover the cluster structure from the shortest possible trajectories, whenever the parameters allow detection. These algorithms thus reach the fundamental detectability limit, and are optimal in that sense.
Recommendations
- On Clusters in Markov Chains
- Markov properties of cluster processes
- Clustering behaviour in Markov chains with eigenvalues close to one
- Clustering with hidden Markov model on variable blocks
- Clustering of Markov chain exceedances
- scientific article; zbMATH DE number 6263207
- scientific article; zbMATH DE number 7233060
- Clusters in Markov chains via singular vectors of Laplacian matrices
- Spectral clustering for non-reversible Markov chains
Cites work
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
- Achieving optimal misclassification proportion in stochastic block models
- Adaptive aggregation for reinforcement learning in average reward Markov decision processes
- An introduction to matrix concentration inequalities
- Asymptotically efficient adaptive allocation rules
- Community detection thresholds and the weak Ramanujan property
- Concentration inequalities for Markov chains by Marton couplings and spectral methods
- Exact Recovery in the Stochastic Block Model
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Least squares quantization in PCM
- Markov Chains
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- On the distribution of the roots of certain symmetric matrices
- Reconstruction and estimation in the planted partition model
- Reinforcement learning. An introduction
- Semicircle law for a matrix ensemble with dependent entries
- Semicircle law for generalized Curie-Weiss matrix ensembles at subcritical temperature
- Sixty years of moments for random matrices
- Spectral techniques applied to sparse random graphs
- Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph
- Spectrum of large random reversible Markov chains: two examples
Cited in
(12)- A fast permuation-based algorithm for block clustering
- Guided cluster discovery with Markov model
- Markovian loop clusters on graphs
- Learning Theory
- A low-rank spectral method for learning Markov models
- Spectral norm bounds for block Markov chain random matrices
- Clusters in Markov chains via singular vectors of Laplacian matrices
- scientific article; zbMATH DE number 7233060 (Why is no real title available?)
- scientific article; zbMATH DE number 6263207 (Why is no real title available?)
- scientific article; zbMATH DE number 3860201 (Why is no real title available?)
- On Clusters in Markov Chains
- Singular value distribution of dense random matrices with block Markovian dependence
This page was built for publication: Clustering in block Markov chains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1996780)
