PageRank on inhomogeneous random digraphs

Jiung Lee and Mariana Olvera-Cravioto

Stochastic Processes and their Applications, 2020, vol. 130, issue 4, 2312-2348

Abstract: We study the typical behavior of Google’s PageRank algorithm on inhomogeneous random digraphs, including directed versions of the Erdős–Rényi model, the Chung–Lu model, the Poissonian random graph and the generalized random graph. Specifically, we show that the rank of a randomly chosen vertex converges weakly to the attracting endogenous solution to the stochastic fixed-point equation R=D∑i=1NCiRi+Q, where (N,Q,{Ci}i≥1) is a real-valued vector with N∈N, and the {Ri} are i.i.d. copies of R, independent of (N,Q,{Ci}i≥1); =D denotes equality in distribution. This result provides further evidence of the power-law behavior of PageRank on graphs whose in-degree distribution follows a power law.

Keywords: PageRank; Ranking algorithms; Directed random graphs; Weighted branching processes; Stochastic fixed-point equations; Power laws (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304414919304120
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:130:y:2020:i:4:p:2312-2348

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spa.2019.07.002

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().