In-Degree and PageRank of web pages: why do they follow similar power laws?

Nelly Litvak, Willem R.W. Scheinhardt, Y. Volkovich

Research output: Contribution to journalArticleAcademicpeer-review

31 Citations (Scopus)
135 Downloads (Pure)


PageRank is a popularity measure designed by Google to rank Web pages. Experiments confirm that PageRank values obey a power law with the same exponent as In-Degree values. This paper presents a novel mathematical model that explains this phenomenon. The relation between PageRank and In-Degree is modelled through a stochastic equation, which is inspired by the original definition of PageRank, and is analogous to the well-known distributional identity for the busy period in the $M/G/1$ queue. Further, we employ the theory of regular variation and Tauberian theorems to analytically prove that the tail distributions of PageRank and In-Degree differ only by a multiple factor, for which we derive a closed-form expression. Our analytical results are in good agreement with experimental data.
Original languageEnglish
Pages (from-to)175-198
Number of pages24
JournalInternet mathematics
Issue number2-3
Publication statusPublished - 2009


  • Taube-rian theorems
  • Power law
  • EWI-15650
  • MSC-68P10
  • MSC-90B15
  • MSC-40E05
  • METIS-264406
  • IR-67788
  • In-Degree
  • Regular variation
  • PageRank
  • Stochastic equation


Dive into the research topics of 'In-Degree and PageRank of web pages: why do they follow similar power laws?'. Together they form a unique fingerprint.

Cite this