On computing PageRank via lumping the Google matrix

摘要

Computing Google’s PageRank via lumping the Google matrix was recently analyzed in [I.C.F. Ipsen, T.M. Selee, PageRank computation, with special attention to dangling nodes, SIAM J. Matrix Anal. Appl. 29 (2007) 1281–1296]. It was shown that all of the dangling nodes can be lumped into a single node and the PageRank could be obtained by applying the power method to the reduced matrix. Furthermore, the stochastic reduced matrix had the same nonzero eigenvalues as the full Google matrix and the power method applied to the reduced matrix had the same convergence rate as that of the power method applied to the full matrix. Therefore, a large amount of operations could be saved for computing the full PageRank vector.In this note, we show that the reduced matrix obtained by lumping the dangling nodes can be further reduced by lumping a class of nondangling nodes, called weakly nondangling nodes, to another single node, and the further reduced matrix is also stochastic with the same nonzero eigenvalues as the Google matrix.