PageRank on inhomogeneous random digraphs

Abstract

We study the typical behavior of a generalized version of Google's PageRank algorithm on a large family of inhomogeneous random digraphs. This family includes as special cases directed versions of classical models such as the Erdös-Rényi model, the Chung-Lu model, the Poissonian random graph and the generalized random graph, and is suitable for modeling scale-free directed complex networks where the number of neighbors a vertex has is related to its attributes. In particular, we show that the rank of a randomly chosen node in a graph from this family converges weakly to the attracting endogenous solution to the stochastic fixed-point equation $$\mathcal{R}\stackrel{\mathcal{D}}{=}\sum _{i=1}^{\mathcal{N}}{\mathcal{C}}_i{\mathcal{R}}_i+\mathcal{Q},$$ where $(\mathcal{N},\mathcal{Q},\{{\mathcal{C}}_i{\}}_{i\ge 1})$ is a real-valued vector with $\mathcal{N}\in \{0,1,2,...\}$, the $\{{\mathcal{R}}_i\}$ are i.i.d.~copies of $\mathcal{R}$, independent of $(\mathcal{N},\mathcal{Q},\{{\mathcal{C}}_i{\}}_{i\ge 1})$, with $\{{\mathcal{C}}_i\}$ i.i.d.~and independent of $(\mathcal{N},\mathcal{Q})$; $\stackrel{\mathcal{D}}{=}$ denotes equality in distribution. This result can then be used to provide further evidence of the power-law behavior of PageRank on scale-free graphs.