Ranking algorithms on directed configuration networks

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$,andthe${$\mathcal{R}$_i}$arei\mathrm{.}i\mathrm{.}d\mathrm{.}copiesof$$\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.