Generalized PageRank on Directed Configuration Networks

Ningyuan Chen, Nelli Litvak, Mariana Olvera-Cravioto

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)
1 Downloads (Pure)

Abstract

Note: formula is not displayed correctly.

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 astochastic fixed-point equation of the form

R=DΣi=1N CiRi+ Q ,

where (Q,N, {Ci}) is a real-valued vector with N ∈ {0, 1, 2, . . . }, P(|Q| > 0) > 0, and the {Ri} are i.i.d. copies of R, independent of (Q,N, {Ci}). 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.

Original languageEnglish
Pages (from-to)237-274
Number of pages38
JournalRandom Structures and Algorithms
Volume51
Issue number2
DOIs
Publication statusPublished - 1 Sep 2017

Keywords

  • PageRank
  • ranking algorithms
  • irected configuration model
  • complex networks
  • stochastic fixed-point equations
  • Weighted branching processes
  • power laws

Fingerprint Dive into the research topics of 'Generalized PageRank on Directed Configuration Networks'. Together they form a unique fingerprint.

  • Cite this