Geodesic
Random walk centrality and a partition of Kemeny's constant
Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 757-775
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-016-0291-9
Classification : 15B51, 60J10
Keywords: stochastic matrix; random walk centrality; Kemeny's constant 
@article{10_1007_s10587_016_0291_9,
     author = {Kirkland, Steve},
     title = {Random walk centrality and a partition of {Kemeny's} constant},
     journal = {Czechoslovak Mathematical Journal},
     pages = {757--775},
     year = {2016},
     volume = {66},
     number = {3},
     doi = {10.1007/s10587-016-0291-9},
     mrnumber = {3556866},
     zbl = {06644032},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0291-9/}
}
TY  - JOUR
AU  - Kirkland, Steve
TI  - Random walk centrality and a partition of Kemeny's constant
JO  - Czechoslovak Mathematical Journal
PY  - 2016
SP  - 757
EP  - 775
VL  - 66
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0291-9/
DO  - 10.1007/s10587-016-0291-9
LA  - en
ID  - 10_1007_s10587_016_0291_9
ER  - 
%0 Journal Article
%A Kirkland, Steve
%T Random walk centrality and a partition of Kemeny's constant
%J Czechoslovak Mathematical Journal
%D 2016
%P 757-775
%V 66
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0291-9/
%R 10.1007/s10587-016-0291-9
%G en
%F 10_1007_s10587_016_0291_9
Kirkland, Steve. Random walk centrality and a partition of Kemeny's constant. Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 757-775. doi: 10.1007/s10587-016-0291-9

[1] Campbell, S., Meyer, C. D.: Generalized Inverses of Linear Transformations. Classics in Applied Mathematics 56 SIAM, Philadelphia (2009). | MR | Zbl

[2] Chartrand, G., Lesniak, L.: Graphs and Digraphs. Chapman and Hall, Boca Raton (2005). | MR | Zbl

[3] Kirkland, S. J.: On a question concerning condition numbers for Markov chains. SIAM J. Matrix Anal. Appl. 23 (2002), 1109-1119. | DOI | MR | Zbl

[4] Kirkland, S. J., Neumann, M.: Group Inverses of M-matrices and Their Applications. CRC Press, Boca Raton (2013). | MR | Zbl

[5] Kirkland, S. J., Neumann, M., Shader, B. L.: Bounds on the subdominant eigenvalue involving group inverses with applications to graphs. Czech. Math. J. 47 (1998), 1-20. | DOI | MR | Zbl

[6] Levene, M., Loizou, G.: Kemeny's constant and the random surfer. Am. Math. Mon. 109 (2002), 741-745. | DOI | MR | Zbl

[7] Meyer, C. D.: Sensitivity of the stationary distribution of a Markov chain. SIAM J. Matrix Anal. Appl. 15 (1994), 715-728. | DOI | MR | Zbl

[8] Noh, J., Reiger, H.: Random walks on complex networks. Physical Review Letters 92 (2004), 118701, 5 pages.

[9] Seneta, E.: Non-Negative Matrices and Markov Chains. Springer Series in Statistics Springer, New York (1981). | MR | Zbl

Cité par Sources :