Ranking algorithms on directed configuration networks

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

• Nelly Litvak (Universiteit Twente)
• Friday 15 July 2016, 09:30-10:00
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact INI IT.

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.

This talk is included in these lists:

• All CMS events
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Featured lists
• INI info aggregator
• Interested Talks
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.