School Seminars and Colloquia

On the asymptotic behavior of the Google PageRank distribution

ORSUM Seminar

by Assistant Professor Nelly Litvak


Institution: University of Twente, The Netherlands
Date: Fri 9th March 2007
Time: 1:00 PM
Location: Room 213, Richard Berry Building, The University of Melbourne

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: mfackrel@ms.unimelb.edu.au