On PageRank Algorithm and Markov Chain Reduction

The PageRank is used by search engines to re∞ect the popularity and importance of a page based on its reference ranking. Since the web changes very fast, the PageRank has to be regularly updated. Such updates is an challenging task due to the huge size of the World Wide Web. Consequently, the analysis of the PageRank has become a hot topic with vast literature ranging from the original paper by Brin and Page, to the works by specialists in Markov chains, linear algebra, numerical methods, information retrieval and other flelds. In this work, we shall concentrate on the Markov chain formulation of the PageRank problem. And analyze the implications of aggregation method (Deng. K & P., 2009) in PageRank computation. Such method exploit the block structure of the web and takes the dynamics into consideration. The analysis will be based on the information theory and Perron-Frobenius theory.