PageRank on inhomogeneous random digraphs

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:130

Article

Lee, Jiung¹  Olvera-Cravioto, Mariana² 

[1] Univ Calif Berkeley, Dept Ind Engn & Operat Res, Berkeley, CA 94720 USA

[2] Univ N Carolina, Dept Stat & Operat Res, Chapel Hill, NC 27515 USA

关键词: PageRank;    Ranking algorithms;    Directed random graphs;    Weighted branching processes;    Stochastic fixed-point equations;    Power laws;   

DOI  :  10.1016/j.spa.2019.07.002

来源: Elsevier

【 摘 要 】

We study the typical behavior of Google's PageRank algorithm on inhomogeneous random digraphs, including directed versions of the Erdos-Renyi 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) double under bar Sigma(N)(i=1) CiRi + Q, where (N, Q, {C-i}(i >= 1)) is a real-valued vector with N epsilon N, and the {R-i} are i.i.d. copies of R, independent of (N, Q, {C-i}(i >= 1)); R (D) double under bar 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. (C) 2019 Elsevier B.V. All rights reserved.

【 授权许可】

Free