×

Jordan canonical form of the Google matrix: a potential contribution to the PageRank computation. (English) Zbl 1103.65051

Among other publications, this article refers to a paper of C. Brezinski, M. Redivo-Zaglia and S. Serra-Capizzano [C. R. Math., Acad. Sci. Paris 340, No. 5, 393–397 (2005; Zbl 1066.65040)]. The present paper concerns the page-rank computation of the \(n\times n\) Google matrix \(P=[p_{ij}]\), \(n\) the number of all web pages, \(p_{ij} =1/\deg(i)\) if \(\deg(i)>0\) and there exists a link (an edge in the digraph whose incidence matrix is \(P\), so that the vertices of the digraph are the web pages) and \(p_{ij}=1/n\) (a uniform random choice) for rows with \(\deg(i)=0\). The page-rank is a vector of size \(n\) which gives a measure of importance of every page in the web; it is the left eigenvector of \(P\) associated with the dominant eigenvalue 1.
Since for \(P\) the power method may converge only vary slowly or not at all, the model is changed: for a value \(c\in[0,1]\), one defines the parametric Google matrix \(P(c)=cP+(1-c)E\), \(E=ev^T\), \(e\) the vector of all 1’s, \(v_i>0\), \(\|v\|_1=1\), which is interpreted in terms of the user’s behavior. \(c=0.85\) is suggested in the literature, leading to the upper bound \(c\) for the second largest eigenvalue of \(P(c)\) and to fast convergence.
The paper describes analytically the Jordan form of \(P(c)\) for a given Jordan form of \(P\). In particular, \(\text{page-rank}(c) =\text{page-rank}+R(c)\), where \(R(c)\) is a rational vector function of \(c\). For \(c\) far away from 1, page-rank\((c)\) can be computed efficiently; hence vector extrapolation allows fast computation of page-rank\((c)\) for \(c\) close to 1.

MSC:

65F30 Other matrix algorithms (MSC2010)
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65Y20 Complexity and performance of numerical algorithms

Citations:

Zbl 1066.65040
PDFBibTeX XMLCite
Full Text: DOI