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

Research output: Contribution to journalArticleAcademicpeer-review

20 Citations (Scopus)
18 Downloads (Pure)

Abstract

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
Volume4
Issue number2-3
DOIs
Publication statusPublished - 2009

Fingerprint

PageRank
Websites
Power Law
Mathematical models
Experiments
M/G/1 Queue
Regular Variation
Tauberian theorem
Busy Period
Stochastic Equations
Tail
Closed-form
Exponent
Experimental Data
Mathematical Model
Experiment

Keywords

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

Cite this

@article{f9aee9eaa32d43b59328da53d0a5548b,
title = "In-Degree and PageRank of web pages: why do they follow similar power laws?",
abstract = "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.",
keywords = "Taube-rian theorems, Power law, EWI-15650, MSC-68P10, MSC-90B15, MSC-40E05, METIS-264406, IR-67788, In-Degree, Regular variation, PageRank, Stochastic equation",
author = "Nelly Litvak and Scheinhardt, {Willem R.W.} and Y. Volkovich",
year = "2009",
doi = "10.1080/15427951.2007.10129293",
language = "English",
volume = "4",
pages = "175--198",
journal = "Internet mathematics",
issn = "1542-7951",
publisher = "Taylor & Francis",
number = "2-3",

}

In-Degree and PageRank of web pages : why do they follow similar power laws? / Litvak, Nelly; Scheinhardt, Willem R.W.; Volkovich, Y.

In: Internet mathematics, Vol. 4, No. 2-3, 2009, p. 175-198.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - In-Degree and PageRank of web pages

T2 - why do they follow similar power laws?

AU - Litvak, Nelly

AU - Scheinhardt, Willem R.W.

AU - Volkovich, Y.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - Taube-rian theorems

KW - Power law

KW - EWI-15650

KW - MSC-68P10

KW - MSC-90B15

KW - MSC-40E05

KW - METIS-264406

KW - IR-67788

KW - In-Degree

KW - Regular variation

KW - PageRank

KW - Stochastic equation

U2 - 10.1080/15427951.2007.10129293

DO - 10.1080/15427951.2007.10129293

M3 - Article

VL - 4

SP - 175

EP - 198

JO - Internet mathematics

JF - Internet mathematics

SN - 1542-7951

IS - 2-3

ER -