Monte Carlo Methods for Top-k Personalized PageRank Lists and Name Disambiguation

Abstract : We study a problem of quick detection of top-k Personalized PageRank lists. This problem has a number of important applications such as finding local cuts in large graphs, estimation of similarity distance and name disambiguation. In particular, we apply our results to construct efficient algorithms for the person name disambiguation problem. We argue that when finding top-k Personalized PageRank lists two observations are important. Firstly, it is crucial that we detect fast the top-k most important neighbours of a node, while the exact order in the top-k list as well as the exact values of PageRank are by far not so crucial. Secondly, a little number of wrong elements in top-k lists do not really degrade the quality of top-k lists, but it can lead to significant computational saving. Based on these two key observations we propose Monte Carlo methods for fast detection of top-k Personalized PageRank lists. We provide performance evaluation of the proposed methods and supply stopping criteria. Then, we apply the methods to the person name disambiguation problem. The developed algorithm for the person name disambiguation problem has achieved the second place in the WePS 2010 competition.
Type de document :
Rapport
[Research Report] RR-7367, INRIA. 2010
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00510991
Contributeur : Konstantin Avrachenkov <>
Soumis le : lundi 23 août 2010 - 10:08:57
Dernière modification le : samedi 27 janvier 2018 - 01:31:43
Document(s) archivé(s) le : mercredi 24 novembre 2010 - 02:58:22

Fichiers

RR-7367.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00510991, version 1
  • ARXIV : 1008.3775

Collections

Citation

Konstantin Avrachenkov, Nelly Litvak, Danil Nemirovsky, Elena Smirnova, Marina Sokol. Monte Carlo Methods for Top-k Personalized PageRank Lists and Name Disambiguation. [Research Report] RR-7367, INRIA. 2010. 〈inria-00510991〉

Partager

Métriques

Consultations de la notice

353

Téléchargements de fichiers

589