Generalized PageRank on directed configuration networks

Ningyuan Chen, Nelly Litvak, Mariana Olvera‐Cravioto

Random Structures and Algorithms · 2016 · 38 citations · 51 references

DOIFull text

Open access

Concepts

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 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 where is a real-valued vector with , and the are i.i.d. copies of , independent of . Moreover, we provide precise asymptotics for the limit , which when the in-degree distribution in the directed configuration model has a power law imply a power law distribution for with the same exponent. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 237–274, 2017

References

51