Probabilistic relation between In-Degree and PageRank

Nelly Litvak; Werner R.W. Scheinhardt; Yana Volkovich

doi:10.1007/978-3-540-78808-9

Probabilistic relation between In-Degree and PageRank

Nelly Litvak
, Werner R.W. Scheinhardt
, Yana Volkovich

Stochastic Operations Research

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

20 Downloads (Pure)

Abstract

This paper presents a novel stochastic model that explains the relation between power laws of In-Degree and PageRank. PageRank is a popularity measure designed by Google to rank Web pages. We model the relation between PageRank and In-Degree through a stochastic equation, which is inspired by the original definition of PageRank. Using the theory of regular variation and Tauberian theorems, we prove that the tail distributions of PageRank and In-Degree differ only by a multiplicative constant, for which we derive a closed-form expression. Our analytical results are in good agreement with Web data.

Original language	English
Title of host publication	Algorithms and Models for the Web-Graph
Subtitle of host publication	Fourth International Workshop, WAW 2006, Banff, Canada, November 30 - December 1, 2006. Revised Papers
Editors	William Aiello, Andrei Broder, Jeannette Janssen, Evangelos Milios
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	72-83
Number of pages	12
ISBN (Electronic)	978-3-540-78808-9
ISBN (Print)	978-3-540-78807-2
DOIs	https://doi.org/10.1007/978-3-540-78808-9
Publication status	Published - 2008
Event	4th International Workshop on Algorithms and Models for the Web-Graph, WAW 2006 - Banff, Canada Duration: 30 Nov 2006 → 1 Dec 2006 Conference number: 4

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	4936
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	4th International Workshop on Algorithms and Models for the Web-Graph, WAW 2006
Abbreviated title	WAW
Country/Territory	Canada
City	Banff
Period	30/11/06 → 1/12/06

Keywords

EWI-14589
METIS-254986
IR-62603

Access to Document

10.1007/978-3-540-78808-9

Cite this

Litvak, N., Scheinhardt, W. R. W., & Volkovich, Y. (2008). Probabilistic relation between In-Degree and PageRank. In W. Aiello, A. Broder, J. Janssen, & E. Milios (Eds.), Algorithms and Models for the Web-Graph: Fourth International Workshop, WAW 2006, Banff, Canada, November 30 - December 1, 2006. Revised Papers (pp. 72-83). (Lecture Notes in Computer Science; Vol. 4936). Springer. https://doi.org/10.1007/978-3-540-78808-9

Litvak, Nelly ; Scheinhardt, Werner R.W. ; Volkovich, Yana. / Probabilistic relation between In-Degree and PageRank. Algorithms and Models for the Web-Graph: Fourth International Workshop, WAW 2006, Banff, Canada, November 30 - December 1, 2006. Revised Papers. editor / William Aiello ; Andrei Broder ; Jeannette Janssen ; Evangelos Milios. Berlin, Heidelberg : Springer, 2008. pp. 72-83 (Lecture Notes in Computer Science).

@inproceedings{685463e1a0d24741a2d49758052ca1f7,

title = "Probabilistic relation between In-Degree and PageRank",

abstract = "This paper presents a novel stochastic model that explains the relation between power laws of In-Degree and PageRank. PageRank is a popularity measure designed by Google to rank Web pages. We model the relation between PageRank and In-Degree through a stochastic equation, which is inspired by the original definition of PageRank. Using the theory of regular variation and Tauberian theorems, we prove that the tail distributions of PageRank and In-Degree differ only by a multiplicative constant, for which we derive a closed-form expression. Our analytical results are in good agreement with Web data.",

keywords = "EWI-14589, METIS-254986, IR-62603",

author = "Nelly Litvak and Scheinhardt, \{Werner R.W.\} and Yana Volkovich",

note = "10.1007/978-3-540-78808-9 ; 4th International Workshop on Algorithms and Models for the Web-Graph, WAW 2006, WAW ; Conference date: 30-11-2006 Through 01-12-2006",

year = "2008",

doi = "10.1007/978-3-540-78808-9",

language = "English",

isbn = "978-3-540-78807-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "72--83",

editor = "William Aiello and Andrei Broder and Jeannette Janssen and Evangelos Milios",

booktitle = "Algorithms and Models for the Web-Graph",

address = "Germany",

}

Litvak, N, Scheinhardt, WRW & Volkovich, Y 2008, Probabilistic relation between In-Degree and PageRank. in W Aiello, A Broder, J Janssen & E Milios (eds), Algorithms and Models for the Web-Graph: Fourth International Workshop, WAW 2006, Banff, Canada, November 30 - December 1, 2006. Revised Papers. Lecture Notes in Computer Science, vol. 4936, Springer, Berlin, Heidelberg, pp. 72-83, 4th International Workshop on Algorithms and Models for the Web-Graph, WAW 2006, Banff, Canada, 30/11/06. https://doi.org/10.1007/978-3-540-78808-9

Probabilistic relation between In-Degree and PageRank. / Litvak, Nelly; Scheinhardt, Werner R.W.; Volkovich, Yana.
Algorithms and Models for the Web-Graph: Fourth International Workshop, WAW 2006, Banff, Canada, November 30 - December 1, 2006. Revised Papers. ed. / William Aiello; Andrei Broder; Jeannette Janssen; Evangelos Milios. Berlin, Heidelberg: Springer, 2008. p. 72-83 (Lecture Notes in Computer Science; Vol. 4936).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Probabilistic relation between In-Degree and PageRank

AU - Litvak, Nelly

AU - Scheinhardt, Werner R.W.

AU - Volkovich, Yana

N1 - Conference code: 4

PY - 2008

Y1 - 2008

N2 - This paper presents a novel stochastic model that explains the relation between power laws of In-Degree and PageRank. PageRank is a popularity measure designed by Google to rank Web pages. We model the relation between PageRank and In-Degree through a stochastic equation, which is inspired by the original definition of PageRank. Using the theory of regular variation and Tauberian theorems, we prove that the tail distributions of PageRank and In-Degree differ only by a multiplicative constant, for which we derive a closed-form expression. Our analytical results are in good agreement with Web data.

AB - This paper presents a novel stochastic model that explains the relation between power laws of In-Degree and PageRank. PageRank is a popularity measure designed by Google to rank Web pages. We model the relation between PageRank and In-Degree through a stochastic equation, which is inspired by the original definition of PageRank. Using the theory of regular variation and Tauberian theorems, we prove that the tail distributions of PageRank and In-Degree differ only by a multiplicative constant, for which we derive a closed-form expression. Our analytical results are in good agreement with Web data.

KW - EWI-14589

KW - METIS-254986

KW - IR-62603

U2 - 10.1007/978-3-540-78808-9

DO - 10.1007/978-3-540-78808-9

M3 - Conference contribution

SN - 978-3-540-78807-2

T3 - Lecture Notes in Computer Science

SP - 72

EP - 83

BT - Algorithms and Models for the Web-Graph

A2 - Aiello, William

A2 - Broder, Andrei

A2 - Janssen, Jeannette

A2 - Milios, Evangelos

PB - Springer

CY - Berlin, Heidelberg

T2 - 4th International Workshop on Algorithms and Models for the Web-Graph, WAW 2006

Y2 - 30 November 2006 through 1 December 2006

ER -

Litvak N, Scheinhardt WRW, Volkovich Y. Probabilistic relation between In-Degree and PageRank. In Aiello W, Broder A, Janssen J, Milios E, editors, Algorithms and Models for the Web-Graph: Fourth International Workshop, WAW 2006, Banff, Canada, November 30 - December 1, 2006. Revised Papers. Berlin, Heidelberg: Springer. 2008. p. 72-83. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-78808-9

Probabilistic relation between In-Degree and PageRank

Abstract

Publication series

Workshop

Keywords

Access to Document

Fingerprint

Cite this