The PageRank model of minimal irreducible adjustment and its lumping method (Q2511361)

PageRank, used by the Google search engine, is a successful and well-publicized link-based ranking system to retrieve pages related to a user's query. With the massive size of the web, the list of pages must be manageable. The PageRank score, used to rank the pages, is determined by computing the stationary solution of the Markov chain with a matrix that represents the link structure of the web. In this paper, a minimal irreducible adjustment of PageRank is proposed. The main work is to give a new PageRank model with an adjustment method that can save the link structure between pages. To accelerate the computation, the authors attempt to deal with dangling nodes and nondangling nodes separately by the minimization PageRank model. An effective blocking and lumping algorithm is used for speeding up the process of obtaining a unique solution. Only the PageRank vector of a small random matrix and back substitution calculation are needed to calculate the PageRank vector. The work is inspired by \textit{I. C. F. Ipsen} and \textit{T. M. Selee} [SIAM J. Matrix Anal. Appl. 29, No. 4, 1281--1296 (2008; Zbl 1156.65038)].