We investigate two ergodicity coefficients ɸ ∥∥ and τn−1, originally introduced to bound the subdominant eigenvalues of nonnegative matrices. The former has been generalized to complex matrices in recent years and several properties for such generalized version have been shown so far.We provide a further result concerning the limit of its powers. Then we propose a generalization of the second coefficient τ n−1 and we show that, under mild conditions, it can be used to recast the eigenvector problem Ax = x as a particular M-matrix linear system, whose coefficient matrix can be defined in terms of the entries of A. Such property turns out to generalize the two known equivalent formulations of the Pagerank centrality of a graph.
@article{bwmeta1.element.doi-10_1515_spma-2015-0016,
author = {Francesco Tudisco},
title = {A note on certain ergodicity coeflcients},
journal = {Special Matrices},
volume = {3},
year = {2015},
zbl = {1321.65057},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_1515_spma-2015-0016}
}
Francesco Tudisco. A note on certain ergodicity coeflcients. Special Matrices, Tome 3 (2015) . http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_1515_spma-2015-0016/
[1] C. Brezinski and M. Redivo-Zaglia. Extrapolation and minimization procedures for Pagerank vector. Dagstuhl Seminar Proceedings 07071: Web Information Retrieval and Linear Algebra Algorithms, 2007 | Zbl 1182.65007
[2] C. Brezinski, M. Redivo-Zaglia, and S. Serra-Capizzano. Extrapolation methods for PageRank computations. A C. R. Acad. Sci. Paris, Ser. I 340, pages 393–397, 2005. | Zbl 1066.65040
[3] S. Brin and L. Page. The anatomy of a Large-Scale Hypertextual Web Search Engine. Proc. 7th Int. Conf. World Wide Web, Brisbane, Aust., pages 107–117, 1998.
[4] G. M. Del Corso, A. Gulli, and F. Romani. Fast PageRank computation via a sparse linear System. Internet Math., 2:259–281, 2005. | Zbl 1109.68330
[5] D. Gleich, L. Zhukov, and P. Berkhin. Fast parallel PageRank: A linear system Approach. Yahoo! Res. techincal Rep., 2004.
[6] G. H. Golub and C. Greif. An Arnoldi-type algorithm for computing PageRank. BIT, 46:759–771, 2006. [Crossref] | Zbl 1105.65034
[7] D. Hartfiel. Coeflcients of ergodicity for imprimitive matrices. Commun. Statist. - Stochastic Models, 15:81–88, 1999. | Zbl 0924.15021
[8] D. Hartfiel and U. G. Rothblum. Convergence of inhomogeneus products of matrices and coeflcients of ergodicity. Linear Algebra Appl., 277:1–9, 1998. | Zbl 0934.15033
[9] T. Haveliwala and S. Kamvar. The Second Eigenvalue of the Google Matrix. Stanford Univ. Tech. Rep., 2003. | Zbl 1091.68044
[10] M. Haviv, Y. Ritov, and U. G. Rothblum. Iterative Methods for Approximating the Subdominant Modulus of an Eigenvalue of a Nonnegative Matrix. Linear Algebra Appl., 87:61–75, 1987. [Crossref] | Zbl 0627.65035
[11] I. C. F. Ipsen and S. Kirkland. Convergence analysis of a Pagerank updating algorithm by Langville and Meyer. SIAM J.Matrix Anal. Appl., 27:952–967, 2006. [Crossref] | Zbl 1108.65030
[12] I. C. F. Ipsen and T. M. Selee. Pagerank computation, with special attention to dangling nodes. SIAM J. Matrix Anal. Appl., 29:1281–1296, 2007. [Crossref][WoS] | Zbl 1156.65038
[13] I. C. F. Ipsen and T. M. Selee. Ergodicity coeflcients defined by vector norms. SIAM J. Matrix Anal. Appl., 32(1):153–200, 2011. [Crossref] | Zbl 1223.15043
[14] C. R. Johnson. Row stochastic matrices similar to doubly stochastic matrices. Linear Multilinear Algebra, 10:113–130, 1981. [WoS][Crossref] | Zbl 0455.15019
[15] S. Kamvar, T. Haveliwala, C. Manning, and G. Golub. Extrapolation methods for accelerating Pagerank computations. ACM 1-58113-680-3/03/0005, 2003.
[16] A. N. Langville and C. D. Meyer. Google’s PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, 41 William Street, Princeton NewYersey, 08540, 2006. | Zbl 1104.68042
[17] A Rhodius. On the maximum of ergodicity coeflcients, the Dobrushin ergodicity coeflcient, and products of stochastic matrices. Linear Algebra Appl., 253:141–154, 1997. | Zbl 0871.15021
[18] U. G. Rothblumand C. P. Tan. Upper Bounds on theMaximumModulus of Subdominant Eigenvalues of NonnegativeMatrices. Linear Algebra Appl., 66:45–86, 1985. [Crossref]
[19] E. Seneta. On the historical development of the theory of finite inhomogeneus Markov chains. Proc. Cambridge Philos. Soc,, 74:507–513, 1973. | Zbl 0271.60074
[20] E. Seneta. Coeflcients of ergodicity: Structure and applications. Adv. in Appl. Probab., 11:576–590, 1979. [Crossref] | Zbl 0406.60060
[21] E. Seneta. Explicit forms for ergodicity coeflcients and spectrum localization. Linear Algebra Appl., 60:187–197, 1984. [Crossref] | Zbl 0594.15007
[22] E. Seneta. Markov and the creation of Markov chains. Markov Anniversary Meeting. 2006.
[23] E. Seneta. Non-Negative Matrices and Markov Chains. Springer-Verlag, revised edition, 2006. [WoS] | Zbl 1099.60004
[24] S. Serra-Capizzano. Jordan canonical form of the Googlematrix: a potential contribution to the Pagerank computation. SIAM J. Matrix Anal. Appl., 27(2):305–312, 2005. [Crossref] | Zbl 1103.65051
[25] F. Tudisco, V. Cardinali, and C. Di Fiore. On complex power nonnegative matrices. Linear Algebra Appl., 471:449–468, 2015. | Zbl 1310.15065
[26] F. Tudisco and C. Di Fiore. A preconditioning approach to the pagerank computation problem. Linear Algebra Appl., 435(9):2222–2246, 2011. [WoS] | Zbl 1222.65035