LiveRank: How to Refresh Old Datasets

The Dang Huynh 1, 2 Fabien Mathieu 2, 1 Laurent Viennot 3, 1
3 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : This paper considers the problem of refreshing a dataset. More precisely , given a collection of nodes gathered at some time (Web pages, users from an online social network) along with some structure (hyperlinks, social relationships), we want to identify a significant fraction of the nodes that still exist at present time. The liveness of an old node can be tested through an online query at present time. We call LiveRank a ranking of the old pages so that active nodes are more likely to appear first. The quality of a LiveRank is measured by the number of queries necessary to identify a given fraction of the active nodes when using the LiveRank order. We study different scenarios from a static setting where the Liv-eRank is computed before any query is made, to dynamic settings where the LiveRank can be updated as queries are processed. Our results show that building on the PageRank can lead to efficient LiveRanks, for Web graphs as well as for online social networks.
Type de document :
Article dans une revue
Internet Mathematics, Taylor & Francis, 2015, 〈10.1080/15427951.2015.1098756〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger
Contributeur : Fabien Mathieu <>
Soumis le : mercredi 6 janvier 2016 - 13:38:43
Dernière modification le : jeudi 11 janvier 2018 - 06:21:34
Document(s) archivé(s) le : jeudi 7 avril 2016 - 15:59:21


Fichiers produits par l'(les) auteur(s)


Distributed under a Creative Commons Paternité 4.0 International License




The Dang Huynh, Fabien Mathieu, Laurent Viennot. LiveRank: How to Refresh Old Datasets. Internet Mathematics, Taylor & Francis, 2015, 〈10.1080/15427951.2015.1098756〉. 〈hal-01251552〉



Consultations de la notice


Téléchargements de fichiers