Random walk centrality and a partition of Kemeny’s constant

Autor: Stephen J. Kirkland
Rok vydání: 2016
Předmět:
Zdroj: Czechoslovak Mathematical Journal. 66:757-775
ISSN: 1572-9141
0011-4642
DOI: 10.1007/s10587-016-0291-9
Popis: We consider an accessibility index for the states of a discrete-time, ergodic, homogeneous Markov chain on a finite state space; this index is naturally associated with the random walk centrality introduced by Noh and Reiger (2004) for a random walk on a connected graph. We observe that the vector of accessibility indices provides a partition of Kemeny’s constant for the Markov chain. We provide three characterizations of this accessibility index: one in terms of the first return time to the state in question, and two in terms of the transition matrix associated with the Markov chain. Several bounds are provided on the accessibility index in terms of the eigenvalues of the transition matrix and the stationary vector, and the bounds are shown to be tight. The behaviour of the accessibility index under perturbation of the transition matrix is investigated, and examples exhibiting some counter-intuitive behaviour are presented. Finally, we characterize the situation in which the accessibility indices for all states coincide.
Databáze: OpenAIRE
Externí odkaz: