Implementing the Reordered PageRank Algorithm in Giraph

Implementing the Reordered PageRank Algorithm in Giraph

Oostenbrink, J.

Van Gijzen, M.B. (mentor)
De Weerdt, M.M. (mentor)

Electrical Engineering, Mathematics and Computer Science

Applied mathematics

2015-07-03

PageRank, a method to rank web pages objectively and mechanically, models a random web surfer. The PageRank problem is most easily solved iteratively, using the power method. In this paper the reordered PageRank algorithms are discussed. These algorithms (proposed by A. N. Langville and C. D. Meyer in "A reordering for the PageRank problem") see the PageRank problem as a linear system of equations and begin by reordering the input Graph/matrix. This way only a smaller problem has to be solved. A disadvantage is that it does take a few extra steps to gain the PageRank values from the solution to this smaller problem. We've developed a suitable stopping condition for these algorithms. However, numerical experiments indicate that this stopping condition is much stricter than the stopping condition for the power method. The reordered PageRank algorithms and the power method have been implemented in Giraph, an open source version of Pregel. Pregel and Giraph are frameworks for solving large graph problems distributively in a vertex centred manner. Because of some of the bugs and features in Giraph (and the inherent complexity of the reordered PageRank algorithms), implementing the reordered PageRank algorithms is much more complicated than implementing the power method. The reordered PageRank algorithms are not faster than the power method in Giraph. Even when accounting for the difference in stopping condition the power method is much faster than the reordered PageRank algorithms.

PageRank
Reordering
Power Method
Power Iteration
Giraph

http://resolver.tudelft.nl/uuid:a41607f7-6a0c-4a0a-8895-5aa963c86d6f

Student theses

bachelor thesis

(c) 2015 Oostenbrink, J.