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 for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons