A note on certain ergodicity coeflcients

• Autorzy: Francesco Tudisco
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Ergodicity coefficients; Eigenvalues; Nonnegative matrices; Linear systems; Pagerank

Kategorie tematyczne

• 65F15: Eigenvalues, eigenvectors
• 15A18: Eigenvalues, singular values, and eigenvectors
• 93C05: Linear systems

• Wydawca: De Gruyter Open
• Czasopismo: Special Matrices
• Rocznik: 2015
• Tom: 3
• Numer: 1

Daty

otrzymano

2015-04-22

zaakceptowano

2015-07-22

online

2015-08-03

Twórcy

autor

Francesco Tudisco

• Department of Mathematics and Computer Science, Saarland University, Saarbrücken, Germany

Bibliografia

• [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
• [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.
• [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.
• [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]
• [7] D. Hartfiel. Coeflcients of ergodicity for imprimitive matrices. Commun. Statist. - Stochastic Models, 15:81–88, 1999.
• [8] D. Hartfiel and U. G. Rothblum. Convergence of inhomogeneus products of matrices and coeflcients of ergodicity. Linear Algebra Appl., 277:1–9, 1998.
• [9] T. Haveliwala and S. Kamvar. The Second Eigenvalue of the Google Matrix. Stanford Univ. Tech. Rep., 2003.
• [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]
• [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]
• [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]
• [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]
• [14] C. R. Johnson. Row stochastic matrices similar to doubly stochastic matrices. Linear Multilinear Algebra, 10:113–130, 1981. [WoS][Crossref]
• [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.
• [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.
• [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.
• [20] E. Seneta. Coeflcients of ergodicity: Structure and applications. Adv. in Appl. Probab., 11:576–590, 1979. [Crossref]
• [21] E. Seneta. Explicit forms for ergodicity coeflcients and spectrum localization. Linear Algebra Appl., 60:187–197, 1984. [Crossref]
• [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]
• [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]
• [25] F. Tudisco, V. Cardinali, and C. Di Fiore. On complex power nonnegative matrices. Linear Algebra Appl., 471:449–468, 2015.
• [26] F. Tudisco and C. Di Fiore. A preconditioning approach to the pagerank computation problem. Linear Algebra Appl., 435(9):2222–2246, 2011. [WoS]

Identyfikatory

DOI

10.1515/spma-2015-0016