Nelly Litvak
Talk recording
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 conjectures that this observation holds for all networks with power-law (in-)degree distribution. 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 the local weak convergence of sparse random graphs. The local weak convergence formally describes what the graph looks like locally, at a finite distance of a randomly chosen vertex. While the local weak convergence in itself doesn’t say anything about power laws, it has facilitated a major leap forward in resolving the power law hypothesis. In particular, there is an unexpected striking difference of PageRank properties in directed versus undirected networks.



