# Random walk centrality and a partition of Kemeny's constant

Czechoslovak Mathematical Journal (2016)

- Volume: 66, Issue: 3, page 757-775
- ISSN: 0011-4642

## Access Full Article

top## Abstract

top## How to cite

topKirkland, Stephen J.. "Random walk centrality and a partition of Kemeny's constant." Czechoslovak Mathematical Journal 66.3 (2016): 757-775. <http://eudml.org/doc/286840>.

@article{Kirkland2016,

abstract = {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.},

author = {Kirkland, Stephen J.},

journal = {Czechoslovak Mathematical Journal},

keywords = {stochastic matrix; random walk centrality; Kemeny's constant},

language = {eng},

number = {3},

pages = {757-775},

publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},

title = {Random walk centrality and a partition of Kemeny's constant},

url = {http://eudml.org/doc/286840},

volume = {66},

year = {2016},

}

TY - JOUR

AU - Kirkland, Stephen J.

TI - Random walk centrality and a partition of Kemeny's constant

JO - Czechoslovak Mathematical Journal

PY - 2016

PB - Institute of Mathematics, Academy of Sciences of the Czech Republic

VL - 66

IS - 3

SP - 757

EP - 775

AB - 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.

LA - eng

KW - stochastic matrix; random walk centrality; Kemeny's constant

UR - http://eudml.org/doc/286840

ER -

## References

top- Campbell, S., Meyer, C. D., Generalized Inverses of Linear Transformations, Classics in Applied Mathematics 56 SIAM, Philadelphia (2009). (2009) Zbl1158.15301MR3396208
- Chartrand, G., Lesniak, L., Graphs and Digraphs, Chapman and Hall, Boca Raton (2005). (2005) Zbl1057.05001MR2107429
- Kirkland, S. J., 10.1137/S0895479801390947, SIAM J. Matrix Anal. Appl. 23 (2002), 1109-1119. (2002) Zbl1013.15005MR1920936DOI10.1137/S0895479801390947
- Kirkland, S. J., Neumann, M., Group Inverses of M-matrices and Their Applications, CRC Press, Boca Raton (2013). (2013) Zbl1267.15004MR3185162
- Kirkland, S. J., Neumann, M., Shader, B. L., 10.1023/A:1022455208972, Czech. Math. J. 47 (1998), 1-20. (1998) Zbl0931.15012MR1614056DOI10.1023/A:1022455208972
- Levene, M., Loizou, G., 10.2307/3072398, Am. Math. Mon. 109 (2002), 741-745. (2002) Zbl1023.60061MR1927624DOI10.2307/3072398
- Meyer, C. D., 10.1137/S0895479892228900, SIAM J. Matrix Anal. Appl. 15 (1994), 715-728. (1994) Zbl0809.65143MR1282690DOI10.1137/S0895479892228900
- Noh, J., Reiger, H., Random walks on complex networks, Physical Review Letters 92 (2004), 118701, 5 pages. (2004)
- Seneta, E., Non-Negative Matrices and Markov Chains, Springer Series in Statistics Springer, New York (1981). (1981) Zbl0471.60001MR2209438

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.