Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering
This work provides theoretical insights into Personalized PageRank for local graph clustering, but it is incremental as it builds on existing methods without introducing new paradigms.
The paper analyzes a mean-field model of Personalized PageRank on random graphs with planted dense subgraphs, examining concentration regimes and optimizing the damping factor to understand its applicability and limitations for local graph clustering.
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.