Determining factors behind the pagerank log-log plot

Yana Volkovich; Nelly Litvak; Debora Donato

doi:10.1007/978-3-540-77004-6_9

Determining factors behind the pagerank log-log plot

Yana Volkovich, Nelly Litvak, Debora Donato

Stochastic Operations Research

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

51 Downloads (Pure)

Abstract

We study the relation between PageRank and other parameters of information networks such as in-degree, out-degree, and the fraction of dangling nodes. We model this relation through a stochastic equation inspired by the original definition of PageRank. Further, we use the theory of regular variation to prove that PageRank and in-degree follow power laws with the same exponent. The difference between these two power laws is in a multiplicative constant, which depends mainly on the fraction of dangling nodes, average in-degree, the power law exponent, and the damping factor. The out-degree distribution has a minor effect, which we explicitly quantify. Finally, we propose a ranking scheme which does not depend on out-degrees.

Original language	English
Title of host publication	Algorithms and Models for the Web-Graph
Subtitle of host publication	5th International Workshop, WAW 2007, San Diego, CA, USA, December 11-12, 2007. Proceedings
Editors	Anthony Bonato, Fan R.K. Chung
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	108-123
Number of pages	16
ISBN (Electronic)	978-3-540-77004-6
ISBN (Print)	978-3-540-77003-9
DOIs	https://doi.org/10.1007/978-3-540-77004-6_9
Publication status	Published - 2007
Event	5th International Workshop on Algorithms and Models for the Web-Graph, WAW 2007 - San Diego, United States Duration: 11 Dec 2007 → 12 Dec 2007 Conference number: 5

Publication series

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

Workshop

Workshop	5th International Workshop on Algorithms and Models for the Web-Graph, WAW 2007
Abbreviated title	WAW
Country	United States
City	San Diego
Period	11/12/07 → 12/12/07

Keywords

EWI-11672
MSC-60J80
METIS-245912
MSC-90B15
IR-62095
MSC-68P10

Access to Document

10.1007/978-3-540-77004-6_9

Yolkovich07determining
open
Proof, 1.25 MB

Cite this

Volkovich, Y., Litvak, N., & Donato, D. (2007). Determining factors behind the pagerank log-log plot. In A. Bonato, & F. R. K. Chung (Eds.), Algorithms and Models for the Web-Graph: 5th International Workshop, WAW 2007, San Diego, CA, USA, December 11-12, 2007. Proceedings (pp. 108-123). (Lecture Notes in Computer Science; Vol. 4863). Springer. https://doi.org/10.1007/978-3-540-77004-6_9

@inproceedings{5a74d08568c54b2fb16420e671f5cf94,

title = "Determining factors behind the pagerank log-log plot",

abstract = "We study the relation between PageRank and other parameters of information networks such as in-degree, out-degree, and the fraction of dangling nodes. We model this relation through a stochastic equation inspired by the original definition of PageRank. Further, we use the theory of regular variation to prove that PageRank and in-degree follow power laws with the same exponent. The difference between these two power laws is in a multiplicative constant, which depends mainly on the fraction of dangling nodes, average in-degree, the power law exponent, and the damping factor. The out-degree distribution has a minor effect, which we explicitly quantify. Finally, we propose a ranking scheme which does not depend on out-degrees.",

keywords = "EWI-11672, MSC-60J80, METIS-245912, MSC-90B15, IR-62095, MSC-68P10",

author = "Yana Volkovich and Nelly Litvak and Debora Donato",

year = "2007",

doi = "10.1007/978-3-540-77004-6_9",

language = "English",

isbn = "978-3-540-77003-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "108--123",

editor = "Anthony Bonato and Chung, {Fan R.K.}",

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

address = "Netherlands",

note = "5th International Workshop on Algorithms and Models for the Web-Graph, WAW 2007, WAW ; Conference date: 11-12-2007 Through 12-12-2007",

}

Volkovich, Y, Litvak, N & Donato, D 2007, Determining factors behind the pagerank log-log plot. in A Bonato & FRK Chung (eds), Algorithms and Models for the Web-Graph: 5th International Workshop, WAW 2007, San Diego, CA, USA, December 11-12, 2007. Proceedings. Lecture Notes in Computer Science, vol. 4863, Springer, Berlin, Heidelberg, pp. 108-123, 5th International Workshop on Algorithms and Models for the Web-Graph, WAW 2007, San Diego, United States, 11/12/07. https://doi.org/10.1007/978-3-540-77004-6_9

Determining factors behind the pagerank log-log plot. / Volkovich, Yana; Litvak, Nelly; Donato, Debora.

Algorithms and Models for the Web-Graph: 5th International Workshop, WAW 2007, San Diego, CA, USA, December 11-12, 2007. Proceedings. ed. / Anthony Bonato; Fan R.K. Chung. Berlin, Heidelberg : Springer, 2007. p. 108-123 (Lecture Notes in Computer Science; Vol. 4863).

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

TY - GEN

T1 - Determining factors behind the pagerank log-log plot

AU - Volkovich, Yana

AU - Litvak, Nelly

AU - Donato, Debora

N1 - Conference code: 5

PY - 2007

Y1 - 2007

N2 - We study the relation between PageRank and other parameters of information networks such as in-degree, out-degree, and the fraction of dangling nodes. We model this relation through a stochastic equation inspired by the original definition of PageRank. Further, we use the theory of regular variation to prove that PageRank and in-degree follow power laws with the same exponent. The difference between these two power laws is in a multiplicative constant, which depends mainly on the fraction of dangling nodes, average in-degree, the power law exponent, and the damping factor. The out-degree distribution has a minor effect, which we explicitly quantify. Finally, we propose a ranking scheme which does not depend on out-degrees.

AB - We study the relation between PageRank and other parameters of information networks such as in-degree, out-degree, and the fraction of dangling nodes. We model this relation through a stochastic equation inspired by the original definition of PageRank. Further, we use the theory of regular variation to prove that PageRank and in-degree follow power laws with the same exponent. The difference between these two power laws is in a multiplicative constant, which depends mainly on the fraction of dangling nodes, average in-degree, the power law exponent, and the damping factor. The out-degree distribution has a minor effect, which we explicitly quantify. Finally, we propose a ranking scheme which does not depend on out-degrees.

KW - EWI-11672

KW - MSC-60J80

KW - METIS-245912

KW - MSC-90B15

KW - IR-62095

KW - MSC-68P10

U2 - 10.1007/978-3-540-77004-6_9

DO - 10.1007/978-3-540-77004-6_9

M3 - Conference contribution

SN - 978-3-540-77003-9

T3 - Lecture Notes in Computer Science

SP - 108

EP - 123

BT - Algorithms and Models for the Web-Graph

A2 - Bonato, Anthony

A2 - Chung, Fan R.K.

PB - Springer

CY - Berlin, Heidelberg

T2 - 5th International Workshop on Algorithms and Models for the Web-Graph, WAW 2007

Y2 - 11 December 2007 through 12 December 2007

ER -

Volkovich Y, Litvak N, Donato D. Determining factors behind the pagerank log-log plot. In Bonato A, Chung FRK, editors, Algorithms and Models for the Web-Graph: 5th International Workshop, WAW 2007, San Diego, CA, USA, December 11-12, 2007. Proceedings. Berlin, Heidelberg: Springer. 2007. p. 108-123. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-540-77004-6_9

Determining factors behind the pagerank log-log plot

Abstract

Publication series

Workshop

Keywords

Access to Document

Fingerprint

Cite this