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

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.
Report is based on a joint work with Konstantin Avrachenkov and Arun Kadavankandy.