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 journal › Article › Academic › peer-review

3 Citations (Scopus)
37 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

Fingerprint

Graph Clustering
PageRank
Mean Field
damping
optimization
Mean-field Model
Random Graphs
Subgraph
Damping
Optimization

Keywords

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

Cite this

Avrachenkov, Konstantin ; Kadavankandy, Arun ; Litvak, Nelli Vladimirovna. / Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering. In: Journal of statistical physics. 2018 ; Vol. 173, No. 3-4. pp. 895-916.
@article{1bc8e654aaf04b8080f73c62609b7fcc,
title = "Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering",
abstract = "We analyse a mean-field model of Personalized PageRank (PPR) on the Erdős–R{\'e}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.",
keywords = "UT-Hybrid-D, Mean field, Concentration, Local graph clustering, Personalized PageRank",
author = "Konstantin Avrachenkov and Arun Kadavankandy and Litvak, {Nelli Vladimirovna}",
note = "Springer deal",
year = "2018",
month = "11",
day = "1",
doi = "10.1007/s10955-018-2099-5",
language = "English",
volume = "173",
pages = "895--916",
journal = "Journal of statistical physics",
issn = "0022-4715",
publisher = "Springer",
number = "3-4",

}

Avrachenkov, K, Kadavankandy, A & Litvak, NV 2018, 'Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering' Journal of statistical physics, vol. 173, no. 3-4, pp. 895-916. https://doi.org/10.1007/s10955-018-2099-5

Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering. / Avrachenkov, Konstantin (Corresponding Author); Kadavankandy, Arun; Litvak, Nelli Vladimirovna.

In: Journal of statistical physics, Vol. 173, No. 3-4, 01.11.2018, p. 895-916.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

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

AU - Avrachenkov, Konstantin

AU - Kadavankandy, Arun

AU - Litvak, Nelli Vladimirovna

N1 - Springer deal

PY - 2018/11/1

Y1 - 2018/11/1

N2 - 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.

AB - 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.

KW - UT-Hybrid-D

KW - Mean field

KW - Concentration

KW - Local graph clustering

KW - Personalized PageRank

U2 - 10.1007/s10955-018-2099-5

DO - 10.1007/s10955-018-2099-5

M3 - Article

VL - 173

SP - 895

EP - 916

JO - Journal of statistical physics

JF - Journal of statistical physics

SN - 0022-4715

IS - 3-4

ER -

Avrachenkov K, Kadavankandy A, Litvak NV. Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering. Journal of statistical physics. 2018 Nov 1;173(3-4):895-916. https://doi.org/10.1007/s10955-018-2099-5

Access to Document