Ranking algorithms on directed configuration networks

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 ${\mathcal{R}}^{\ast }$ 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 $$\mathcal{R}\stackrel{\mathcal{D}}{=}\sum _{i=1}^{\mathcal{N}}{\mathcal{C}}_i{\mathcal{R}}_i+\mathcal{Q},$$ where $(\mathcal{Q},\mathcal{N},\{{\mathcal{C}}_i\})$ is a real-valued vector with $\mathcal{N}\in \{0,1,2,\dots \}$, $P(|\mathcal{Q}|>0)>0$, and the $\{{\mathcal{R}}_i\}$ are i.i.d. copies of $\mathcal{R}$, independent of $(\mathcal{Q},\mathcal{N},\{{\mathcal{C}}_i\})$. Moreover, we provide precise asymptotics for the limit ${\mathcal{R}}^{\ast }$, which when the in-degree distribution in the directed configuration model has a power law imply a power law distribution for ${\mathcal{R}}^{\ast }$ with the same exponent.

References in corpus (5)

• Finding Scientific Gems with Google
• Distances in random graphs with finite variance degrees
• Determining factors behind the PageRank log-log plot
• A Weighted Correlation Index for Rankings with Ties
• Coupling on weighted branching trees

Cited by in corpus (2)

• Efficient Simulation for Branching Linear Recursions
• Coupling on weighted branching trees