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

Konstantin Avrachenkov (Corresponding Author), Arun Kadavankandy, Nelli Vladimirovna Litvak

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
56 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)895-916
Number of pages20
JournalJournal of statistical physics
Volume173
Issue number3-4
Early online date5 Jul 2018
DOIs
Publication statusPublished - 1 Nov 2018

Keywords

  • UT-Hybrid-D
  • Mean field
  • Concentration
  • Local graph clustering
  • Personalized PageRank

Fingerprint Dive into the research topics of 'Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering'. Together they form a unique fingerprint.

  • Cite this