Efficient Sparse Linear System Solution of the PageRank Problem

The research community has recently devoted an increasing amount of attention to reducing the computational time needed by Web ranking algorithms. In particular, many techniques have been proposed to speed up the well-known PageRank algorithm. This interest is driven by two dominant factors: (1) the Web Graph is simply huge and is subject to dramatic updates in terms of nodes and links, therefore the PageRank assignment tends to become obsolete very quickly; (2) many PageRank vectors need to be computed according to different choices of the personalization vectors or when adopting strategies for collusion detection. In this paper, we show how the PageRank computation in the original random surfer model can be transformed into the problem of computing the solution of a sparse linear system. The sparsity of the obtained linear system makes it possible to exploit the effectiveness of Markov chain index reordering to speed up the PageRank computation. In particular, we rearrange the system matrix according to several permutations and we apply different scalar and block iterative methods to solve smaller linear systems. We tested our approaches on Web Graphs crawled from the net. The largest one amounts to about 24 millions nodes and more than 100 million links. With this Web Graph, the cost for computing the PageRank is reduced by 58% in terms of Mflops and of 90% in terms of time with respect to the more commonly used Power method.