Open Collections

Clustering in Markov Chains with Subdominant Eigenvalues Close to One

Banff International Research Station for Mathematical Innovation and Discovery

Finite, discrete, time-homogeneous Markov chains are frequently used as a simple mathematical model of real-world dynamical systems. In many such applications, an analysis of clustering behaviour is desirable, and it is well-known that the eigendecomposition of the transition matrix $T$ of the chain can provide such insight. In a recent paper (see [1]), a method is presented for determining clusters from a subdominant real eigenvalue $\lambda$ of $T$ which is close to the spectral radius 1. In this talk, we extend the method to include an analysis for complex eigenvalues of $T$ which are close to 1. Since a real spectrum is not guaranteed in most applications, this is a valuable result in the area of spectral clustering in Markov chains. This is joint work with Emanuele Crisostomi, Mahsa Faizrahnemoon, Steve Kirkland, and Robert Shorten. [1] Emanuele Crisostomi, Stephen Kirkland, and Robert Shorten. A Google-like model of road network dynamics and its application to regulation and control. $\textit{International Journal of Control}$, 84(3):633--651, 2011.

Mathematics; Linear and multilinear algebra; matrix theory; Combinatorics

video/mp4

Author affiliation: University of Manitoba

2018-01-04

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/64254

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/