Quick detection of top-k personalized PageRank lists

Konstantin Avrachenkov, Nelly Litvak, Danil Nemirovsky, Elena Smirnova, Marina Sokol

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

33 Citations (Scopus)
139 Downloads (Pure)


We study a problem of quick detection of top-k Personalized PageRank (PPR) lists. This problem has a number of important applications such as finding local cuts in large graphs, estimation of similarity distance and person name disambiguation. We argue that two observations are important when finding top-k PPR lists. Firstly, it is crucial that we detect fast the top-k most important neighbors of a node, while the exact order in the top-k list and the exact values of PPR are by far not so crucial. Secondly, by allowing a small number of “wrong” elements in top-k lists, we achieve great computational savings, in fact, without degrading the quality of the results. Based on these ideas, we propose Monte Carlo methods for quick detection of top-k PPR lists. We demonstrate the effectiveness of these methods on the Web and Wikipedia graphs, provide performance evaluation and supply stopping criteria.
Original languageEnglish
Title of host publicationAlgorithms and Models for the Web Graph
Subtitle of host publication8th International Workshop, WAW 2011, Atlanta, GA, USA, May 27-29, 2011. Proceedings
EditorsAlan Frieze, Paul Horn, Pawel Pralat
Place of PublicationBerlin, Germany
Number of pages12
ISBN (Print)978-3-642-21286-4
Publication statusPublished - 2011
Event8th International Workshop on Algorithms and Models for the Web Graph, WAW 2011 - Atlanta, United States
Duration: 27 May 201129 May 2011
Conference number: 8

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th International Workshop on Algorithms and Models for the Web Graph, WAW 2011
Abbreviated titleWAW
Country/TerritoryUnited States


Dive into the research topics of 'Quick detection of top-k personalized PageRank lists'. Together they form a unique fingerprint.

Cite this