Generalized PageRank on Directed Configuration Networks

Ningyuan Chen, Nelli Litvak, Mariana Olvera-Cravioto

Research output: Contribution to journalArticleAcademicpeer-review

7 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

Fingerprint

PageRank
Configuration
Random variables
Fixed-point Equation
Precise Asymptotics
Power-law Distribution
Degree Distribution
Linear Combination
Ranking
Power Law
Random variable
Exponent
Converge
Imply
Graph in graph theory
Vertex of a graph
Model

Keywords

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

Cite this

Chen, Ningyuan ; Litvak, Nelli ; Olvera-Cravioto, Mariana. / Generalized PageRank on Directed Configuration Networks. In: Random Structures and Algorithms. 2017 ; Vol. 51, No. 2. pp. 237-274.
@article{7832703070594dd696188859fc0b7ce4,
title = "Generalized PageRank on Directed Configuration Networks",
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.",
keywords = "PageRank, ranking algorithms, irected configuration model, complex networks, stochastic fixed-point equations, Weighted branching processes, power laws",
author = "Ningyuan Chen and Nelli Litvak and Mariana Olvera-Cravioto",
year = "2017",
month = "9",
day = "1",
doi = "10.1002/rsa.20700",
language = "English",
volume = "51",
pages = "237--274",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "Wiley",
number = "2",

}

Generalized PageRank on Directed Configuration Networks. / Chen, Ningyuan; Litvak, Nelli ; Olvera-Cravioto, Mariana.

In: Random Structures and Algorithms, Vol. 51, No. 2, 01.09.2017, p. 237-274.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Generalized PageRank on Directed Configuration Networks

AU - Chen, Ningyuan

AU - Litvak, Nelli

AU - Olvera-Cravioto, Mariana

PY - 2017/9/1

Y1 - 2017/9/1

N2 - 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.

AB - 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.

KW - PageRank

KW - ranking algorithms

KW - irected configuration model

KW - complex networks

KW - stochastic fixed-point equations

KW - Weighted branching processes

KW - power laws

U2 - 10.1002/rsa.20700

DO - 10.1002/rsa.20700

M3 - Article

VL - 51

SP - 237

EP - 274

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 2

ER -