Computing Publications

Publications Home » PageRank: Three Distributed Algorithms

PageRank: Three Distributed Algorithms

Douglas de Jager

Master's Thesis
Imperial College London
September, 2004

This paper shows for the first time that there are multiple PageRank definitions, and that more is required to justify PageRank than is offered in the literature. Adopting a formal approach, this paper provides a justification of PageRank. It also shows that the irreducibility restriction on the PageRank transition matrix is unnecessary. This is important because it gives the personalisation vector more intuitive force.

Noting the difficulties in calculating PageRank centrally, the paper then shows, via the Chazan-Miranker theorem, that distributed calculation algorithms are possible; and, it presents three such novel algorithms. The first of these takes documents / pages as being of principal interest; the second and third, in an attempt to reduce communication overheads, focus attention on nodes/webservers. Empirical test results are shown. These confirm reduced message numbers for algorithms 2 and 3. They also show that more investigation is required into suitable thresholds within asynchronous environs.

PDF of full publication (4.1 megabytes)
(need help viewing PDF files?)
BibTEX file for the publication
Conditions for downloading publications from this site. built & maintained by Ashok Argent-Katwala.