PageRank in scale-free random graphs

Ningyuan Chen, Nelly Litvak, Mariana Olvera-Cravioto

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)
6 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 languageEnglish
Title of host publicationAlgorithms and Models for the Web Graph
EditorsAnthony Bonata, Fan Chung, Paweł Pralat
Place of PublicationCham, Switzerland
PublisherSpringer
Pages120-131
Number of pages12
ISBN (Electronic)978-3-319-13123-8
ISBN (Print)978-3-319-13123-8
DOIs
Publication statusPublished - 17 Dec 2014
Event11th International Workshop Algorithms and Models for the Web Graph, WAW 2014 - Beijing, China
Duration: 17 Dec 201418 Dec 2014
Conference number: 11

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
Volume8882
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop11th International Workshop Algorithms and Models for the Web Graph, WAW 2014
Abbreviated titleWAW
CountryChina
CityBeijing
Period17/12/1418/12/14

    Fingerprint

Keywords

  • EWI-25534
  • METIS-309799
  • IR-93645

Cite this

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 (pp. 120-131). (Lecture Notes in Computer Science; Vol. 8882). Cham, Switzerland: Springer. https://doi.org/10.1007/978-3-319-13123-8_10