Generalized PageRank on directed configuration networks. Issue 2 (7th November 2016) - Chen, Ningyuan; Litvak, Nelly; Olvera‐Cravioto, Mariana
ABSTRACT: This paper studies the distribution of a family of rankings, which includes Google's PageRank, on a directed configuration model. In particular, it is shown that the distribution of the rank of a randomly chosen node in the graph converges in distribution to a finite random variable R * that can be written as a linear combination of i.i.d. copies of the attracting endogenous solution to a stochastic fixed‐point equation of the form R = D ∑ i = 1 N C i R i + Q, where ( Q, N, C i ) is a real‐valued vector with N ∈ 0, 1, 2, … , P ( | Q | > 0 ) > 0, and the R i are i.i.d. copies of R, independent of ( Q, N, C i ) . Moreover, we provide precise asymptotics for the limit R *, which when the in‐degree distribution in the directed configuration model has a power law imply a power law distribution for R * with the same exponent. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 237–274, 2017