skip to content

Ranking algorithms on directed configuration networks

Presented by: 
Nelly Litvak Universiteit Twente
Friday 15th July 2016 - 09:30 to 10:00
INI Seminar Room 1
Co-authors: Ningyuan Chen (Yale School of Management), Mariana Olvera-Cravioto (Columbia University)

We study a family of rankings, which includes Google's PageRank, on a directed configuration model. We show that the the rank of a randomly chosen vertex converges in distribution to a finite random variable that can be written as a linear combination of i.i.d. copies of the attracting endogenous solution to a stochastic fixed-point equation. We provide precise asymptotics for this limiting random variable. In particular, if the in-degree distribution in the directed configuration model has a power law distribution, then the limiting distribution of the rank also follows a power law with the same exponent. Such power law behaviour of ranking is well-known from empirical studies of real-life networks. Our asymptotic result gives remarkably good approximation for the complete ranking distribution on configuration networks of moderate size and on the directed graph of English Wikipedia.

[ The video of this talk is temporarily unavailable. Please try later. ]

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons