On the asymptotic behavior of the Google PageRank distribution
by Assistant Professor Nelly Litvak
Abstract: PageRank is a popularity measure introduced by Google for Web ranking. It is well-known that PageRank exhibits a heavy-tailed behavior, which is similar to the distribution of in-degree (the number of incoming
links on a page). In this work, we provide a probabilistic analysis for
the relation between PageRank and other parameters of information networks such as in-degree, out-degree (the number of outgoing links on
a page), and the fraction of dangling nodes (the nodes with out-degree zero). We interrelate PageRank and the networks parameters through a
stochastic equation inspired by the original definition of PageRank.
Further, we use the theory of regular variation to prove that the tail behavior of PageRank and in-degree differ only by a multiple coefficient, which depends mainly on the fraction of dangling nodes and average in-degree. The out-degree distribution has a minor effect, which we explicitly quantify. Our theoretical predictions show a good
agreement with experimental data on three different samples of the Web.
For More Information: Mark Fackrell: firstname.lastname@example.org