### Abstract

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | Department of Applied Mathematics, University of Twente |

Number of pages | 39 |

ISBN (Print) | 1874-4850 |

State | Published - 16 Jun 2015 |

### Publication series

Name | Memorandum |
---|---|

Publisher | University of Twente, Department of Applied Mathematics |

No. | 2046 |

ISSN (Print) | 1874-4850 |

### Fingerprint

### Keywords

- PageRank
- Stochastic fixed-point equations
- Ranking algorithms
- Weighted branching processes
- Directed configuration model
- Complex networks
- IR-96268
- METIS-312642
- MSC-68P20
- MSC-60J80
- MSC-05C80
- EWI-26087
- Power laws

### Cite this

*Ranking algorithms on directed configuration networks*. (Memorandum; No. 2046). Enschede: Department of Applied Mathematics, University of Twente.

}

*Ranking algorithms on directed configuration networks*. Memorandum, no. 2046, Department of Applied Mathematics, University of Twente, Enschede.

**Ranking algorithms on directed configuration networks.** / Chen, Ningyuan; Litvak, Nelli; Olvera-Cravioto, Mariana.

Research output: Professional › Report

TY - BOOK

T1 - Ranking algorithms on directed configuration networks

AU - Chen,Ningyuan

AU - Litvak,Nelli

AU - Olvera-Cravioto,Mariana

PY - 2015/6/16

Y1 - 2015/6/16

N2 - 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 endogenous solution to a stochastic fixed point equation of the form $R \stackrel {D}{=} \sum^N _{i=1} C_iR_i + Q,$ where $(Q,N, \{C_i\})$ is a real-valued vector with $N \in \{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.

AB - 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 endogenous solution to a stochastic fixed point equation of the form $R \stackrel {D}{=} \sum^N _{i=1} C_iR_i + Q,$ where $(Q,N, \{C_i\})$ is a real-valued vector with $N \in \{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.

KW - PageRank

KW - Stochastic fixed-point equations

KW - Ranking algorithms

KW - Weighted branching processes

KW - Directed configuration model

KW - Complex networks

KW - IR-96268

KW - METIS-312642

KW - MSC-68P20

KW - MSC-60J80

KW - MSC-05C80

KW - EWI-26087

KW - Power laws

M3 - Report

SN - 1874-4850

T3 - Memorandum

BT - Ranking algorithms on directed configuration networks

PB - Department of Applied Mathematics, University of Twente

ER -