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.
- Taube-rian theorems
- Power law
- Regular variation
- Stochastic equation
Litvak, N., Scheinhardt, W. R. W., & Volkovich, Y. (2009). In-Degree and PageRank of web pages: why do they follow similar power laws? Internet mathematics, 4(2-3), 175-198. https://doi.org/10.1080/15427951.2007.10129293