Clusters in Markov chains via singular vectors of Laplacian matrices

被引：0
|
作者：
Cole, Sam [1 ]
Kirkland, Steve [2 ]
机构：
[1] NielsenIQ, Chicago, IL 60606 USA
[2] Univ Manitoba, Dept Math, Winnipeg, MB, Canada
来源：
LINEAR ALGEBRA AND ITS APPLICATIONS | 2023年 / 660卷
基金：
加拿大自然科学与工程研究理事会;
关键词：
Markov chain; Stochastic matrix; Cluster; Left singular vector; Laplacian matrix; Contents; ALGORITHM; SUBSPACE; STATES;
D O I：
10.1016/j.laa.2022.11.015
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Suppose that T is a stochastic matrix. We propose an algo-rithm 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 vec-tor associated with the second smallest singular value of the Laplacian matrix I-T. We prove a number of results that jus-tify the algorithm's approach, and illustrate the algorithm's performance with several numerical examples.(c) 2022 Elsevier Inc. All rights reserved.
引用
收藏
页码：1 / 39
页数：39
相关论文
共 39 条
  • [1] Transition matrices for well-conditioned Markov chains
    Kirkland, S. J.
    Neumann, Michael
    Xu, Jianhong
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 424 (01) : 118 - 131
  • [2] A note on circulant transition matrices in Markov chains
    Chou, Wun-Seng
    Du, Bau-Sen
    Shiue, J. -S.
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 429 (07) : 1699 - 1704
  • [3] The computation of key properties of Markov chains via perturbations
    Hunter, Jeffrey J.
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2016, 511 : 176 - 202
  • [4] On transition matrices of Markov chains corresponding to Hamiltonian cycles
    Konstantin Avrachenkov
    Ali Eshragh
    Jerzy A. Filar
    Annals of Operations Research, 2016, 243 : 19 - 35
  • [5] On transition matrices of Markov chains corresponding to Hamiltonian cycles
    Avrachenkov, Konstantin
    Eshragh, Ali
    Filar, Jerzy A.
    ANNALS OF OPERATIONS RESEARCH, 2016, 243 (1-2) : 19 - 35
  • [6] An approach to construct the singular monotone functions by using Markov chains
    Liu, W
    TAIWANESE JOURNAL OF MATHEMATICS, 1998, 2 (03): : 361 - 368
  • [7] Computing densities for Markov chains via simulation
    Henderson, SG
    Glynn, PW
    MATHEMATICS OF OPERATIONS RESEARCH, 2001, 26 (02) : 375 - 400
  • [8] Distributed Averaging Via Lifted Markov Chains
    Jung, Kyomin
    Shah, Devavrat
    Shin, Jinwoo
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2010, 56 (01) : 634 - 647
  • [9] On monotonically proceeding structures and stepwise increasing transition matrices of Markov chains
    Guerry, Marie-Anne
    Carette, Philippe
    COMMUNICATIONS IN STATISTICS-THEORY AND METHODS, 2022, 51 (01) : 51 - 67
  • [10] FROM THE BERNOULLI FACTORY TO A DICE ENTERPRISE VIA PERFECT SAMPLING OF MARKOV CHAINS
    Morina, Giulio
    Latuszynski, Krzysztof
    Nayar, Piotr
    Wendland, Alex
    ANNALS OF APPLIED PROBABILITY, 2022, 32 (01): : 327 - 359
1234