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.
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/hal-01936016
Contributor : Konstantin Avrachenkov <>
Submitted on : Tuesday, November 27, 2018 - 11:12:37 AM
Last modification on : Friday, March 15, 2019 - 10:28:50 AM
Long-term archiving on : Thursday, February 28, 2019 - 1:47:56 PM

File

MeanFieldPPR_arxiv.pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

107

Files downloads

117