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

Konstantin Avrachenkov; Arun Kadavankandy; Nelli Vladimirovna Litvak

doi:10.1007/s10955-018-2099-5

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

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

Stochastic Operations Research

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

5 Citations (Scopus)

83 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 language	English
Pages (from-to)	895-916
Number of pages	20
Journal	Journal of statistical physics
Volume	173
Issue number	3-4
Early online date	5 Jul 2018
DOIs	https://doi.org/10.1007/s10955-018-2099-5
Publication status	Published - 1 Nov 2018

Keywords

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

Access to Document

10.1007/s10955-018-2099-5

2018-JSP_Avrachenkov_et_al2018Submitted version, 501 KB
2018-XAvrachenkovKandavankandyLitvak_s10955-018-2099-5Final published version, 833 KBLicence: Taverne

Cite this

@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{\H o}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 = nov,

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",

}

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 -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this