Nelly Litvak (Eindhoven University of Technology)

Title: Local weak convergence and heavy tails of PageRank

Abstract: 

PageRank, introduced by Google in 1998 to rank web pages, is one of most common centrality measures in complex networks. In the empirical data, whenever a network, directed or undirected, has a power law (in-)degree distribution, PageRank follows the power law with the same exponent.  The so-called power law hypothesis conjectured that this observation holds for all networks with power-law (in-)degree distribution. While this conjecture is very intuitive, the actual results turn out to be much more nuanced. In this talk I will tell about the exploration of the power law hypothesis in random graph models. An important ingredient of the recent analysis is our result that if a sequence of random graphs converges locally weakly to a rooted random graph, then the PageRank distribution converges to that of the PageRank of the root. While the local weak convergence in itself doesn’t say anything about power laws, it does bring us towards resolving the power law hypothesis and yields many unexpected insights such as the striking difference of PageRank properties in directed versus undirected graphs.

This seminar will take place in Room S08 at the Faculty of Sciences.