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

Konstantin Avrachenkov (1) , Arun Kadavankandy (1, 2) , Nelly Litvak (3)

1 NEO - Network Engineering and Operations
2 LANEAS - Large Networks and Systems Group
3 EEMCS - Faculty of Electrical Engineering, Mathematics and Computer Science [Twente]

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.

Mots clés: Personalized PageRank; Mean Field; Concentration; Local Graph Clustering

Domaines: Apprentissage [cs.LG]; Réseaux sociaux et d'information [cs.SI]; Probabilités [math.PR]; Statistiques [math.ST]

Konstantin Avrachenkov, Arun Kadavankandy, Nelly Litvak. Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering. Journal of Statistical Physics, 2018, 173 (3-4), pp.895 - 916. ⟨10.1007/s10955-018-2099-5⟩. ⟨hal-01936016⟩