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

Abstract

We analyse a mean-field model of Personalized PageRank on the Erdos-Renyi random graph containing a denser planted Erdos-Renyi subgraph. We investigate the regimes where the values of Personalized PageRank concentrate around the mean-field value. 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.

arXiv comment22 pages, 6 figures

References in corpus (7)

• Multiplex PageRank
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Block Models and Personalized PageRank
• Phase transitions in semisupervised clustering of sparse networks
• Community Detection with and without Prior Information
• Semidefinite Programs for Exact Recovery of a Hidden Community
• Recovering a Hidden Community Beyond the Kesten-Stigum Threshold in $O(|E|{\log }^{\ast }|V|)$ Time

Cited by in corpus (3)

• Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection
• Extremes of Sums and Maxima with Application to Random Networks
• Almost exact recovery in noisy semi-supervised learning