Updating pagerank with iterative aggregation
The SIAD method is expressed as the power method preconditioned by a partial LU factorization.
This leads to a simple derivation of the asymptotic convergence rate of the SIAD method.
It is designed, in particular, to speed up the determination of Page Rank, which is used by the search engine Google in the ranking of web pages.
In this paper the convergence, in exact arithmetic, of the SIAD method is analyzed.
Due to the scale of the web, Google only updates its famous Page Rank vector on a monthly basis. Drastically speeding the Page Rank computation can lead to fresher, more accurate rankings of the webpages retrieved by search engines.We compare the theoretical rates of convergence of the original Page Rank algorithm to that of the new reordered Page Rank algorithm, showing that the new algorithm can do no worse than the original algorithm.We present results of an experimental comparison on five datasets, which demonstrate that the reordered Page Rank algorithm can provide a speedup as much as a factor of 6. The Page Rank updating algorithm proposed by Langville and Meyer is a special case of an iterative aggregation/disaggregation (SIAD) method for computing stationary distributions of very large Markov chains.It is known that the power method applied to the Google matrix always converges, and we show that the asymptotic convergence rate of the SIAD method is at least as good as that of the power method.Furthermore, by exploiting the hyperlink structure of the web it can be shown that the asymptotic convergence rate of the SIAD method applied to the Google matrix can be made strictly faster than that of the power method.