Centrality in large random networks

Description

A centrality is an algorithm that assigns an importance score to each node in a large network, such as an on-line social network or the World Wide Web. Most prominent example is the PageRank algorithm designed by Google to rank web pages. Mathematically, PageRank is a stationary distribution of a simple random walk with restart on a directed graph. A natural yet largely open question is: how the underlying graph structure affects the distribution of centrality scores? We will address this question by providing an overview of formal analysis for the PageRank distribution. One approach involves formulating the problem in terms of a stochastic fixed-point equation, which enables the analysis of PageRank on trees and on random graphs that can be coupled with a tree. Such random graphs include, e.g., the influential configuration model, where degrees of the nodes are fixed but connections are made purely at random. Another approach exploits the recent notion of local weak convergence of sparse graph sequences, and builds on the right balance between local and global properties of PageRank. We will discuss how this analysis helps to explain empirically observed phenomena and its potential extension to a large variety of more realistic network models.
The talk is based on joint work with Mariana Olvera-Cravioto, Yana Volkovich, Ninguyan Chen, Remco van der Hofstad, Alessandro Garavaglia.

Period	3 Jul 2019
Event title	20th INFORMS Applied Probability Society Conference 2019
Event type	Conference
Conference number	20
Location	Brisbane, Australia
Degree of Recognition	International