Characterization of tail dependence for in-degree and PageRank

Willem R.W. Scheinhardt; Y. Volkovich; Bert Zwart

doi:10.1007/978-3-540-95995-3_8

Characterization of tail dependence for in-degree and PageRank

Willem R.W. Scheinhardt, Y. Volkovich, Bert Zwart

Stochastic Operations Research

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

4 Citations (Scopus)

Abstract

The dependencies between power law parameters such as in-degree and PageRank, can be characterized by the so-called angular measure, a notion used in extreme value theory to describe the dependency between very large values of coordinates of a random vector. Basing on an analytical stochastic model, we argue that the angular measure for in-degree and personalized PageRank is concentrated in two points. This corresponds to the two main factors for high ranking: large in-degree and a high rank of one of the ancestors. Furthermore, we can formally establish the relative importance of these two factors.

Original language	English
Title of host publication	Algorithms and Models for the Web-Graph
Subtitle of host publication	6th International Workshop, WAW 2009, Barcelona, Spain, February 12-13, 2009. Proceedi
Editors	Konstantin Avrachenkov, Debora Donato, Nelly Litvak
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	90-103
Number of pages	14
ISBN (Electronic)	978-3-540-95995-3
ISBN (Print)	978-3-540-95994-6
DOIs	https://doi.org/10.1007/978-3-540-95995-3_8
Publication status	Published - 2009
Event	6th International Workshop on Algorithms and Models for the Web-Graph, WAW 2009 - Barcelona, Spain Duration: 12 Feb 2009 → 13 Feb 2009 Conference number: 6

Publication series

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

Workshop

Workshop	6th International Workshop on Algorithms and Models for the Web-Graph, WAW 2009
Abbreviated title	WAW
Country	Spain
City	Barcelona
Period	12/02/09 → 13/02/09

Keywords

EWI-15151
Regular variation
PageRank
METIS-263754
IR-62760
Multivariate extremes
Power law graphs

Access to Document

10.1007/978-3-540-95995-3_8

Cite this

Scheinhardt, W. R. W., Volkovich, Y., & Zwart, B. (2009). Characterization of tail dependence for in-degree and PageRank. In K. Avrachenkov, D. Donato, & N. Litvak (Eds.), Algorithms and Models for the Web-Graph: 6th International Workshop, WAW 2009, Barcelona, Spain, February 12-13, 2009. Proceedi (pp. 90-103). (Lecture Notes in Computer Science; Vol. 5427). Springer. https://doi.org/10.1007/978-3-540-95995-3_8

Scheinhardt, Willem R.W. ; Volkovich, Y. ; Zwart, Bert. / Characterization of tail dependence for in-degree and PageRank. Algorithms and Models for the Web-Graph: 6th International Workshop, WAW 2009, Barcelona, Spain, February 12-13, 2009. Proceedi. editor / Konstantin Avrachenkov ; Debora Donato ; Nelly Litvak. Berlin, Heidelberg : Springer, 2009. pp. 90-103 (Lecture Notes in Computer Science).

@inproceedings{518bc20b5dbb4118beddf540866bf432,

title = "Characterization of tail dependence for in-degree and PageRank",

abstract = "The dependencies between power law parameters such as in-degree and PageRank, can be characterized by the so-called angular measure, a notion used in extreme value theory to describe the dependency between very large values of coordinates of a random vector. Basing on an analytical stochastic model, we argue that the angular measure for in-degree and personalized PageRank is concentrated in two points. This corresponds to the two main factors for high ranking: large in-degree and a high rank of one of the ancestors. Furthermore, we can formally establish the relative importance of these two factors.",

keywords = "EWI-15151, Regular variation, PageRank, METIS-263754, IR-62760, Multivariate extremes, Power law graphs",

author = "Scheinhardt, {Willem R.W.} and Y. Volkovich and Bert Zwart",

year = "2009",

doi = "10.1007/978-3-540-95995-3_8",

language = "English",

isbn = "978-3-540-95994-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "90--103",

editor = "Konstantin Avrachenkov and Debora Donato and Nelly Litvak",

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

address = "Netherlands",

note = "6th International Workshop on Algorithms and Models for the Web-Graph, WAW 2009, WAW ; Conference date: 12-02-2009 Through 13-02-2009",

}

Scheinhardt, WRW, Volkovich, Y & Zwart, B 2009, Characterization of tail dependence for in-degree and PageRank. in K Avrachenkov, D Donato & N Litvak (eds), Algorithms and Models for the Web-Graph: 6th International Workshop, WAW 2009, Barcelona, Spain, February 12-13, 2009. Proceedi. Lecture Notes in Computer Science, vol. 5427, Springer, Berlin, Heidelberg, pp. 90-103, 6th International Workshop on Algorithms and Models for the Web-Graph, WAW 2009, Barcelona, Spain, 12/02/09. https://doi.org/10.1007/978-3-540-95995-3_8

Characterization of tail dependence for in-degree and PageRank. / Scheinhardt, Willem R.W.; Volkovich, Y.; Zwart, Bert.

Algorithms and Models for the Web-Graph: 6th International Workshop, WAW 2009, Barcelona, Spain, February 12-13, 2009. Proceedi. ed. / Konstantin Avrachenkov; Debora Donato; Nelly Litvak. Berlin, Heidelberg : Springer, 2009. p. 90-103 (Lecture Notes in Computer Science; Vol. 5427).

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

TY - GEN

T1 - Characterization of tail dependence for in-degree and PageRank

AU - Scheinhardt, Willem R.W.

AU - Volkovich, Y.

AU - Zwart, Bert

N1 - Conference code: 6

PY - 2009

Y1 - 2009

N2 - The dependencies between power law parameters such as in-degree and PageRank, can be characterized by the so-called angular measure, a notion used in extreme value theory to describe the dependency between very large values of coordinates of a random vector. Basing on an analytical stochastic model, we argue that the angular measure for in-degree and personalized PageRank is concentrated in two points. This corresponds to the two main factors for high ranking: large in-degree and a high rank of one of the ancestors. Furthermore, we can formally establish the relative importance of these two factors.

AB - The dependencies between power law parameters such as in-degree and PageRank, can be characterized by the so-called angular measure, a notion used in extreme value theory to describe the dependency between very large values of coordinates of a random vector. Basing on an analytical stochastic model, we argue that the angular measure for in-degree and personalized PageRank is concentrated in two points. This corresponds to the two main factors for high ranking: large in-degree and a high rank of one of the ancestors. Furthermore, we can formally establish the relative importance of these two factors.

KW - EWI-15151

KW - Regular variation

KW - PageRank

KW - METIS-263754

KW - IR-62760

KW - Multivariate extremes

KW - Power law graphs

U2 - 10.1007/978-3-540-95995-3_8

DO - 10.1007/978-3-540-95995-3_8

M3 - Conference contribution

SN - 978-3-540-95994-6

T3 - Lecture Notes in Computer Science

SP - 90

EP - 103

BT - Algorithms and Models for the Web-Graph

A2 - Avrachenkov, Konstantin

A2 - Donato, Debora

A2 - Litvak, Nelly

PB - Springer

CY - Berlin, Heidelberg

T2 - 6th International Workshop on Algorithms and Models for the Web-Graph, WAW 2009

Y2 - 12 February 2009 through 13 February 2009

ER -

Scheinhardt WRW, Volkovich Y, Zwart B. Characterization of tail dependence for in-degree and PageRank. In Avrachenkov K, Donato D, Litvak N, editors, Algorithms and Models for the Web-Graph: 6th International Workshop, WAW 2009, Barcelona, Spain, February 12-13, 2009. Proceedi. Berlin, Heidelberg: Springer. 2009. p. 90-103. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-540-95995-3_8

Characterization of tail dependence for in-degree and PageRank

Abstract

Publication series

Workshop

Keywords

Access to Document

Fingerprint

Cite this