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

28 Citations (Scopus)
67 Downloads (Pure)

Abstract

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
PublisherSpringer
Pages50-61
Number of pages12
ISBN (Print)978-3-642-21286-4
DOIs
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
PublisherSpringer
Volume6732
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th International Workshop on Algorithms and Models for the Web Graph, WAW 2011
Abbreviated titleWAW
CountryUnited States
CityAtlanta
Period27/05/1129/05/11

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

  • Cite this

    Avrachenkov, K., Litvak, N., Nemirovsky, D., Smirnova, E., & Sokol, M. (2011). Quick detection of top-k personalized PageRank lists. In A. Frieze, P. Horn, & P. Pralat (Eds.), Algorithms and Models for the Web Graph: 8th International Workshop, WAW 2011, Atlanta, GA, USA, May 27-29, 2011. Proceedings (pp. 50-61). (Lecture Notes in Computer Science; Vol. 6732). Berlin, Germany: Springer. https://doi.org/10.1007/978-3-642-21286-4_5