PageRank in Growing Scale Free Network Models

Dmitri Lebedev

LIX, Ecole Polytechnique


PageRank is one of the principle criteria according to which Google ranks Web pages. PageRank can be interpreted as a frequency of visiting a Web page by a random surfer and thus it reflects the popularity of a Web page. In the present work we find an analytical expression for the expected PageRank value in scale free network model as a function of the age of the growing network and the age of a particular node. Furthermore, we derive asymptotics that show that PageRank distribution is indeed close to a power law. The exponent of the theoretical power law matches very well the value found from measurements of the Web. Finally, our expressions give a mathematical insight for the choice of the Google constant.

[Dmitri Lebedev]
[LIX, Ecole Polytechnique]