Data Analysis and Applications 3, 3rd Edition

3Exploring The Relationship Between Ordinary PageRank, Lazy PageRank and Random Walk with Backstep PageRank for Different Graph Structures

This chapter presents a comparative review of three variants of PageRank, namely ordinary PageRank (introduced by Brin and Page as a measure of importance of a web page), lazy PageRank and random walk with backstep PageRank. We compare the variants in terms of their convergence and consistency in rank scores for different graph structures with reference to PageRank’s parameters, c (damping factor) and β (backstep parameter). In addition, we show that ordinary PageRank can be formulated from the other two variants by some proportionality relationships.

3.1. Introduction

PageRank is an algorithm for ranking web pages. It was founded by Larry Page and Sergey Brin at Stanford University [BRI 98, PAG 99]. It is the first and best known webgraph-based algorithm in the Google search engine [SUL 07]. The algorithm is simple, robust and reliable to measure the importance of web pages [KLE 99].

The idea of PageRank can be described by considering a random surfer who starts from a random page v_i. If there are no outlinks from v_i, the surfer visits any page with uniform probability, otherwise, with a uniform probability p_ij, the surfer follows one of the available outlinks and visits the next page v_j, unless he or she gets bored at this page and resorts to jumping to any web page with uniform probability [KLO 14, BOL 05]. The PageRank associated with ...