Generalized PageRank on directed configuration networks. Issue 2 (7th November 2016)

• Record Type: Journal Article
• Authors: Chen, Ningyuan; Litvak, Nelly; Olvera‐Cravioto, Mariana
• Is Part Of: Random structures & algorithms. Volume 51:Issue 2(2017)
• Page Start: 237
• Page End: 274
• Publication Date: 2016-11-07
• Subjects: PageRank -- ranking algorithms -- directed configuration model -- complex networks -- stochastic fixed‐point equations -- weighted branching processes -- power laws; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20700
• Languages: English
• ISSNs: 1042-9832

Abstract

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 R * 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 R = D ∑ i = 1 N C i R i + Q, where ( Q, N, { C i } ) is a real‐valued vector with N ∈ { 0, 1, 2, … }, P ( | Q | > 0 ) > 0, and the { R i } are i.i.d. copies of R, independent of ( Q, N, { C i } ) . 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. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 237–274, 2017