Ranking algorithms on directed configuration networks

Ningyuan Chen, Nelli Litvak, Mariana Olvera-Cravioto

Abstract

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.
Original languageUndefined
Place of PublicationEnschede
PublisherDepartment of Applied Mathematics, University of Twente
Number of pages39
ISBN (Print)1874-4850
StatePublished - 16 Jun 2015

Publication series

NameMemorandum
PublisherUniversity of Twente, Department of Applied Mathematics
No.2046
ISSN (Print)1874-4850

Fingerprint

Configuration
Model
Fixed-point equation
Precise asymptotics
PageRank
Power-law distribution
Degree distribution
Stochastic equations
Linear combination
Ranking
Power law
Random variable
Exponent
Rank of a matrix
Converge
Imply
Graph in graph theory
Vertex of a graph

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

Chen, N., Litvak, N., & Olvera-Cravioto, M. (2015). Ranking algorithms on directed configuration networks. (Memorandum; No. 2046). Enschede: Department of Applied Mathematics, University of Twente.

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

Enschede : Department of Applied Mathematics, University of Twente, 2015. 39 p. (Memorandum; No. 2046).

Research output: ProfessionalReport

@book{17b45eec1df0465991fed8319873bec2,
title = "Ranking algorithms on directed configuration networks",
abstract = "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.",
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",
author = "Ningyuan Chen and Nelli Litvak and Mariana Olvera-Cravioto",
year = "2015",
month = "6",
isbn = "1874-4850",
series = "Memorandum",
publisher = "Department of Applied Mathematics, University of Twente",
number = "2046",

}

Chen, N, Litvak, N & Olvera-Cravioto, M 2015, 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.

Enschede : Department of Applied Mathematics, University of Twente, 2015. 39 p. (Memorandum; No. 2046).

Research output: ProfessionalReport

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 -

Chen N, Litvak N, Olvera-Cravioto M. Ranking algorithms on directed configuration networks. Enschede: Department of Applied Mathematics, University of Twente, 2015. 39 p. (Memorandum; 2046).