A note on certain ergodicity coeflcients

Francesco Tudisco

Special Matrices (2015)

  • Volume: 3, Issue: 1, page 175-185, electronic only
  • ISSN: 2300-7451

Abstract

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

How to cite

top

Francesco Tudisco. "A note on certain ergodicity coeflcients." Special Matrices 3.1 (2015): 175-185, electronic only. <http://eudml.org/doc/271790>.

@article{FrancescoTudisco2015,
abstract = {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.},
author = {Francesco Tudisco},
journal = {Special Matrices},
keywords = {Ergodicity coefficients; Eigenvalues; Nonnegative matrices; Linear systems; Pagerank; ergodicity coefficients; eigenvalues; nonnegative matrices; linear systems; -matrix linear system},
language = {eng},
number = {1},
pages = {175-185, electronic only},
title = {A note on certain ergodicity coeflcients},
url = {http://eudml.org/doc/271790},
volume = {3},
year = {2015},
}

TY - JOUR
AU - Francesco Tudisco
TI - A note on certain ergodicity coeflcients
JO - Special Matrices
PY - 2015
VL - 3
IS - 1
SP - 175
EP - 185, electronic only
AB - 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.
LA - eng
KW - Ergodicity coefficients; Eigenvalues; Nonnegative matrices; Linear systems; Pagerank; ergodicity coefficients; eigenvalues; nonnegative matrices; linear systems; -matrix linear system
UR - http://eudml.org/doc/271790
ER -

References

top
  1. [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 Zbl1182.65007
  2. [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. Zbl1066.65040
  3. [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. [4] G. M. Del Corso, A. Gulli, and F. Romani. Fast PageRank computation via a sparse linear System. Internet Math., 2:259–281, 2005. Zbl1109.68330
  5. [5] D. Gleich, L. Zhukov, and P. Berkhin. Fast parallel PageRank: A linear system Approach. Yahoo! Res. techincal Rep., 2004. 
  6. [6] G. H. Golub and C. Greif. An Arnoldi-type algorithm for computing PageRank. BIT, 46:759–771, 2006. [Crossref] Zbl1105.65034
  7. [7] D. Hartfiel. Coeflcients of ergodicity for imprimitive matrices. Commun. Statist. - Stochastic Models, 15:81–88, 1999. Zbl0924.15021
  8. [8] D. Hartfiel and U. G. Rothblum. Convergence of inhomogeneus products of matrices and coeflcients of ergodicity. Linear Algebra Appl., 277:1–9, 1998. Zbl0934.15033
  9. [9] T. Haveliwala and S. Kamvar. The Second Eigenvalue of the Google Matrix. Stanford Univ. Tech. Rep., 2003. Zbl1091.68044
  10. [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] Zbl0627.65035
  11. [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] Zbl1108.65030
  12. [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] Zbl1156.65038
  13. [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] Zbl1223.15043
  14. [14] C. R. Johnson. Row stochastic matrices similar to doubly stochastic matrices. Linear Multilinear Algebra, 10:113–130, 1981. [WoS][Crossref] Zbl0455.15019
  15. [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. [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. Zbl1104.68042
  17. [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. Zbl0871.15021
  18. [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. [19] E. Seneta. On the historical development of the theory of finite inhomogeneus Markov chains. Proc. Cambridge Philos. Soc,, 74:507–513, 1973. Zbl0271.60074
  20. [20] E. Seneta. Coeflcients of ergodicity: Structure and applications. Adv. in Appl. Probab., 11:576–590, 1979. [Crossref] Zbl0406.60060
  21. [21] E. Seneta. Explicit forms for ergodicity coeflcients and spectrum localization. Linear Algebra Appl., 60:187–197, 1984. [Crossref] Zbl0594.15007
  22. [22] E. Seneta. Markov and the creation of Markov chains. Markov Anniversary Meeting. 2006. 
  23. [23] E. Seneta. Non-Negative Matrices and Markov Chains. Springer-Verlag, revised edition, 2006. [WoS] Zbl1099.60004
  24. [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] Zbl1103.65051
  25. [25] F. Tudisco, V. Cardinali, and C. Di Fiore. On complex power nonnegative matrices. Linear Algebra Appl., 471:449–468, 2015. Zbl1310.15065
  26. [26] F. Tudisco and C. Di Fiore. A preconditioning approach to the pagerank computation problem. Linear Algebra Appl., 435(9):2222–2246, 2011. [WoS] Zbl1222.65035

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.