Google Matrix - Spectrum and Eigenstates of G Matrix

Spectrum and Eigenstates of G Matrix

For there is only one maximal eigenvalue with the corresponding right eigenvector which has non-negative elements which can be viewed as stationary probability distribution . These probabilities ordered by their decreasing values give the PageRank vector with the RageRank used by Google search to rank webpages. Usually one has for the World Wide Web that with . The number of nodes with a given PageRank value scales as with the exponent . The left eigenvector at has constant matrix elements. With all eigenvalues move as except the maximal eigenvalue, which remains unchanged . The PageRank vector varies with but other eigenvectors with remain unchanged due to their orthogonality to the constant left vector at . The gap between and other eigenvalue is gives a rapid convergence of a random initial vector to the PageRank approximately after 50 multiplications on matrix.

At the matrix has generally many degenerate eigenvalues (see e.g. ). Examples of the eigenvalue spectrum of the Google matrix of various directed networks is shown in Fig.3 from and Fig.4 from .

The Google matrix can be also constructed for the Ulam networks generated by the Ulam method for dynamical maps. The spectral properties of such matrices are discussed in . In a number of cases the spectrum is described by the fractal Weyl law .

The Google matrix can be constructed also for other directed networks, e.g. for the procedure call network of the Linux Kernel software introduced in . In this case the spectrum of is described by the fractal Weyl law with the fractal dimension (see Fig.5 from ). Numerical analysis shows that the eigenstates of matrix are localized (see Fig.6 from ). Arnoldi iteration method allows to compute many eigenvalues and eigenvectors for matrices of rather large size .

Other examples of matrix include the Google matrix of brain and business process management, see also . Applications of Google matrix analysis to DNA sequences is described in .