TY - GEN

T1 - PageRank and the Random Surfer Model

AU - Chebolu, Prasad

AU - Melsted, Páll

PY - 2008

Y1 - 2008

N2 - In recent years there has been considerable interest in analyzing random graph models for the Web. We consider two such models - the Random Surfer model, introduced by Blum et al. [7], and the PageRank-based selection model, proposed by Pandurangan et al. [18]. It has been observed that search engines influence the growth of the Web. The PageRank-based selection model tries to capture the effect that these search engines have on the growth of the Web by adding new links according to Pagerank. The PageRank algorithm is used in the Google search engine [1] for ranking search results. We show the equivalence of the two random graph models and carry out the analysis in the Random Surfer model, since it is easier to work with. We analyze the expected in-degree of vertices and show that it follows a powerlaw. We also analyze the expected PageRank of vertices and show that it follows the same powerlaw as the expected degree. We show that in both models the expected degree and the PageRank of the first vertex, the root of the graph, follow the same powerlaw. However, the power undergoes a phase-transition as we vary the parameter of the model. This peculiar behavior of the root has not been observed in previous analysis and simulations of the two models.

AB - In recent years there has been considerable interest in analyzing random graph models for the Web. We consider two such models - the Random Surfer model, introduced by Blum et al. [7], and the PageRank-based selection model, proposed by Pandurangan et al. [18]. It has been observed that search engines influence the growth of the Web. The PageRank-based selection model tries to capture the effect that these search engines have on the growth of the Web by adding new links according to Pagerank. The PageRank algorithm is used in the Google search engine [1] for ranking search results. We show the equivalence of the two random graph models and carry out the analysis in the Random Surfer model, since it is easier to work with. We analyze the expected in-degree of vertices and show that it follows a powerlaw. We also analyze the expected PageRank of vertices and show that it follows the same powerlaw as the expected degree. We show that in both models the expected degree and the PageRank of the first vertex, the root of the graph, follow the same powerlaw. However, the power undergoes a phase-transition as we vary the parameter of the model. This peculiar behavior of the root has not been observed in previous analysis and simulations of the two models.

UR - http://www.scopus.com/inward/record.url?scp=58449096749&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:58449096749

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1010

EP - 1018

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -