In-degree and pageRank of web pages: Why do they follow similar power laws?

Research output: Book/ReportReportProfessional

17 Downloads (Pure)

Abstract

The PageRank is a popularity measure designed by Google to rank Web pages. Experiments confirm that the PageRank obeys a 'power law' with the same exponent as the In-Degree. This paper presents a novel mathematical model that explains this phenomenon. The relation between the PageRank and In-Degree is modelled through a stochastic equation, which is inspired by the original definition of the PageRank, and is analogous to the well-known distributional identity for the busy period in the M/G/l queue. Further, we employ the theory of regular variation and Tauberian theorems to analytically prove that the tail behavior of the PageRank and the In-Degree differ only by a multiplicative factor, for which we derive a closed-form expression. Our analytical results are in good agreement with experimental data.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages20
Publication statusPublished - May 2006

Publication series

NameApplied Mathematics Memoranda
PublisherDepartment of Applied Mathematics, University of Twente
No.1807
ISSN (Print)0169-2690

Keywords

  • IR-66196
  • METIS-238082
  • MSC-40E05
  • MSC-90B15
  • MSC-68P10
  • EWI-6125

Cite this