We analyse a mean-field model of Personalized PageRank (PPR) on the Erdős–Rényi (ER) random graph containing a denser planted ER subgraph. We investigate the regimes where the values of PPR concentrate around the mean-field value. We also study the optimization of the damping factor, the only parameter in PPR. Our theoretical results help to understand the applicability of PPR and its limitations for local graph clustering.
- Mean field
- Local graph clustering
- Personalized PageRank
Avrachenkov, K., Kadavankandy, A., & Litvak, N. V. (2018). Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering. Journal of statistical physics, 173(3-4), 895-916. https://doi.org/10.1007/s10955-018-2099-5