PageRank in scale-free random graphs

Ningyuan Chen, Nelly Litvak, Mariana Olvera-Cravioto

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

5 Citations (Scopus)
6 Downloads (Pure)


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
Number of pages12
ISBN (Electronic)978-3-319-13123-8
ISBN (Print)978-3-319-13123-8
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
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Workshop11th International Workshop Algorithms and Models for the Web Graph, WAW 2014
Abbreviated titleWAW


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

Fingerprint Dive into the research topics of 'PageRank in scale-free random graphs'. Together they form a unique fingerprint.

Cite this