Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering

Speaker: Nelly Litvak (University of Twente and Eindhoven University of Technology, The Netherlands)

Abstract:

We analyse a mean-field model of Personalized PageRank on the Erdös-Rényi random graph containing a denser planted Erdös-Rényi subgraph. We investigate the regimes where the values of Personalized PageRank concentrate around the mean-field model. We also study the optimization of the damping factor, the only parameter in Personalized PageRank. Our theoretical results help to understand the applicability of Personalized PageRank and its limitations for local graph clustering.

This is a joint work with Konstantin Avrachenkov and Arun Kadavankandy.