PAGERANK'S BEHAVIOR UNDER DEGREE CORRELATIONS

• 成果类型: Article
• 署名作者: Olvera-Cravioto, Mariana
• 署名单位: University of North Carolina; University of North Carolina Chapel Hill
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/20-AAP1623
• 发表日期: 2021
• 页码: 1403-1442
• 关键词: fixed-points; smoothing transform; Random graphs; asymptotics

摘要

The focus of this work is the asymptotic analysis of the tail distribution of Google's PageRank algorithm on large scale-free directed networks. In particular, the main theorem provides the convergence, in the Kantorovich-Rubinstein metric, of the rank of a randomly chosen vertex in graphs generated via either a directed configuration model or an inhomogeneous random digraph. The theorem fully characterizes the limiting distribution by expressing it as a random sum of i.i.d. copies of the attracting endogenous solution to a branching distributional fixed-point equation. In addition, we provide the asymptotic tail behavior of the limit and use it to explain the effect that in-degree/out-degree correlations in the underlying graph can have on the qualitative performance of PageRank.