### 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=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.

Original language | English |
---|---|

Pages (from-to) | 237-274 |

Number of pages | 38 |

Journal | Random Structures and Algorithms |

Volume | 51 |

Issue number | 2 |

DOIs | |

Publication status | Published - 1 Sep 2017 |

### Fingerprint

### Keywords

- PageRank
- ranking algorithms
- irected conﬁguration model
- complex networks
- stochastic ﬁxed-point equations
- Weighted branching processes
- power laws

### Cite this

*Random Structures and Algorithms*,

*51*(2), 237-274. https://doi.org/10.1002/rsa.20700

}

*Random Structures and Algorithms*, vol. 51, no. 2, pp. 237-274. https://doi.org/10.1002/rsa.20700

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

Research output: Contribution to journal › Article › Academic › peer-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 conﬁguration model

KW - complex networks

KW - stochastic ﬁxed-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 -