Premium
Generalized PageRank on directed configuration networks
Author(s) -
Chen Ningyuan,
Litvak Nelly,
OlveraCravioto Mariana
Publication year - 2017
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20700
Subject(s) - pagerank , mathematics , random variable , distribution (mathematics) , exponent , degree distribution , limit (mathematics) , rank (graph theory) , random graph , struct , graph , combinatorics , discrete mathematics , computer science , theoretical computer science , mathematical analysis , statistics , complex network , linguistics , philosophy , programming language
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 variableR *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 NC iR i + Q , where ( Q , N , { C i } ) is a real‐valued vector withN ∈ { 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 limitR * , which when the in‐degree distribution in the directed configuration model has a power law imply a power law distribution forR *with the same exponent. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 237–274, 2017