Ranking algorithms on directed configuration networks

Ningyuan Chen, Nelli Litvak, Mariana Olvera-Cravioto

Research output: Book/ReportReportOther research output

6 Downloads (Pure)

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
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages39
Publication statusPublished - 16 Jun 2015

Publication series

NameMemorandum of the Department of Applied Mathematics
No.2046
ISSN (Print)1874-4850

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 of the Department of Applied Mathematics; No. 2046). Enschede: University of Twente, Department of Applied Mathematics.