PageRank in scale-free random graphs

Ningyuan Chen; Nelly Litvak; Mariana Olvera-Cravioto

doi:10.1007/978-3-319-13123-8_10

PageRank in scale-free random graphs

Ningyuan Chen, Nelly Litvak, Mariana Olvera-Cravioto

Stochastic Operations Research

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

9 Citations (Scopus)

7 Downloads (Pure)

Abstract

We analyze the distribution of PageRank on a directed configuration model and show that as the size of the graph grows to infinity, the PageRank of a randomly chosen node can be closely approximated by the PageRank of the root node of an appropriately constructed tree. This tree approximation is in turn related to the solution of a linear stochastic fixed-point equation that has been thoroughly studied in the recent literature.

Original language	English
Title of host publication	Algorithms and Models for the Web Graph
Editors	Anthony Bonata, Fan Chung, Paweł Pralat
Place of Publication	Cham, Switzerland
Publisher	Springer
Pages	120-131
Number of pages	12
ISBN (Electronic)	978-3-319-13123-8
ISBN (Print)	978-3-319-13123-8
DOIs	https://doi.org/10.1007/978-3-319-13123-8_10
Publication status	Published - 17 Dec 2014
Event	11th International Workshop Algorithms and Models for the Web Graph, WAW 2014 - Beijing, China Duration: 17 Dec 2014 → 18 Dec 2014 Conference number: 11

Publication series

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

Workshop

Workshop	11th International Workshop Algorithms and Models for the Web Graph, WAW 2014
Abbreviated title	WAW
Country/Territory	China
City	Beijing
Period	17/12/14 → 18/12/14

Keywords

EWI-25534
METIS-309799
IR-93645

Access to Document

10.1007/978-3-319-13123-8_10

Cite this

@inproceedings{f9125bde1a8947c9a88e8819540c1487,

title = "PageRank in scale-free random graphs",

abstract = "We analyze the distribution of PageRank on a directed configuration model and show that as the size of the graph grows to infinity, the PageRank of a randomly chosen node can be closely approximated by the PageRank of the root node of an appropriately constructed tree. This tree approximation is in turn related to the solution of a linear stochastic fixed-point equation that has been thoroughly studied in the recent literature.",

keywords = "EWI-25534, METIS-309799, IR-93645",

author = "Ningyuan Chen and Nelly Litvak and Mariana Olvera-Cravioto",

note = "eemcs-eprint-25534 ; 11th International Workshop Algorithms and Models for the Web Graph, WAW 2014, WAW ; Conference date: 17-12-2014 Through 18-12-2014",

year = "2014",

month = dec,

day = "17",

doi = "10.1007/978-3-319-13123-8_10",

language = "English",

isbn = "978-3-319-13123-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "120--131",

editor = "Anthony Bonata and Fan Chung and Pawe{\l} Pralat",

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

}

Chen, N, Litvak, N & Olvera-Cravioto, M 2014, PageRank in scale-free random graphs. in A Bonata, F Chung & P Pralat (eds), Algorithms and Models for the Web Graph. Lecture Notes in Computer Science, vol. 8882, Springer, Cham, Switzerland, pp. 120-131, 11th International Workshop Algorithms and Models for the Web Graph, WAW 2014, Beijing, China, 17/12/14. https://doi.org/10.1007/978-3-319-13123-8_10

PageRank in scale-free random graphs. / Chen, Ningyuan; Litvak, Nelly; Olvera-Cravioto, Mariana.

Algorithms and Models for the Web Graph. ed. / Anthony Bonata; Fan Chung; Paweł Pralat. Cham, Switzerland : Springer, 2014. p. 120-131 (Lecture Notes in Computer Science; Vol. 8882).

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

TY - GEN

T1 - PageRank in scale-free random graphs

AU - Chen, Ningyuan

AU - Litvak, Nelly

AU - Olvera-Cravioto, Mariana

N1 - Conference code: 11

PY - 2014/12/17

Y1 - 2014/12/17

N2 - We analyze the distribution of PageRank on a directed configuration model and show that as the size of the graph grows to infinity, the PageRank of a randomly chosen node can be closely approximated by the PageRank of the root node of an appropriately constructed tree. This tree approximation is in turn related to the solution of a linear stochastic fixed-point equation that has been thoroughly studied in the recent literature.

AB - We analyze the distribution of PageRank on a directed configuration model and show that as the size of the graph grows to infinity, the PageRank of a randomly chosen node can be closely approximated by the PageRank of the root node of an appropriately constructed tree. This tree approximation is in turn related to the solution of a linear stochastic fixed-point equation that has been thoroughly studied in the recent literature.

KW - EWI-25534

KW - METIS-309799

KW - IR-93645

U2 - 10.1007/978-3-319-13123-8_10

DO - 10.1007/978-3-319-13123-8_10

M3 - Conference contribution

SN - 978-3-319-13123-8

T3 - Lecture Notes in Computer Science

SP - 120

EP - 131

BT - Algorithms and Models for the Web Graph

A2 - Bonata, Anthony

A2 - Chung, Fan

A2 - Pralat, Paweł

PB - Springer

CY - Cham, Switzerland

T2 - 11th International Workshop Algorithms and Models for the Web Graph, WAW 2014

Y2 - 17 December 2014 through 18 December 2014

ER -

PageRank in scale-free random graphs

Abstract

Publication series

Workshop

Keywords

Access to Document

Fingerprint

Cite this