Ranking algorithms on directed configuration networks

الأصل · EN

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 endogenous solution to a stochastic fixed point equation of the form R D= ∑ᵢ₌₁ⁿ Cᵢ Rᵢ + Q, where (Q, N, { Cᵢ}) is a real-valued vector with N ∈ {0,1,2,}, P(|Q| > 0) > 0, and the {Rᵢ} are i.i.d. copies of R, independent of (Q, N, { Cᵢ}). 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.