Random Surfer with Back Step

Article type: Research Article

Authors: Sydow, Marcin

Affiliations: Polish-Japanese Institute of Information Technology, Koszykowa 86, 02-008 Warsaw, Poland. E-mail: msyd@pjwstk.edu.pl

Abstract: The World Wide Web with its billions of hyperlinked documents is a huge and important resource of information. There is a necessity of filtering this information. Link analysis of the Web graph turned out to be a powerful tool for automatically identifying authoritative documents. One of the best examples is the PageRank algorithm used in Google [1] to rank search results. In this paper we extend the model underlying the PageRank algorithm by incorporating "back button" usage modeling in order to make the model less simplistic. We explain the existence and uniqueness of the ranking induced by the extended model. We also develop and implement an efficient approximation method for computing the novel ranking and present succesful experimental results made on 80- and 50- million page samples of the real Web.

Keywords: Web Information Retrieval, Link Analysis, PageRank, Back Button Modeling

Journal: Fundamenta Informaticae, vol. 68, no. 4, pp. 379-398, 2005