University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Ranking algorithms on directed configuration networks

Ranking algorithms on directed configuration networks

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact info@newton.ac.uk.

SNAW01 - Graph limits and statistics

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.

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2021 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity