Quick Detection of Nodes with Large Degrees

Abstract : Our goal is to find top-k lists of nodes with the largest degrees in large complex networks quickly. If the adjacency list of the network is known (not often the case in complex networks), a deterministic algorithm to find the top-k list of nodes with the largest degrees requires an average complexity of O(n), where n is the number of nodes in the network. Even this modest complexity can be very high for large complex networks. We propose to use a random-walk-based method. We show theoretically and by numerical experiments that for large networks, the random-walk method finds good-quality top lists of nodes with high probability and with computational savings of orders of magnitude. We also propose stopping criteria for the random-walk method that requires very little knowledge about the structure of the network.
Type de document :
Article dans une revue
Internet Mathematics, Taylor & Francis, 2014, 10 (1-2), pp.1-19. 〈http://www.tandfonline.com/toc/uinm20/10/1-2#.VIWw8_mG98E〉. 〈10.1080/15427951.2013.798601〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01092304
Contributeur : Konstantin Avrachenkov <>
Soumis le : lundi 8 décembre 2014 - 15:08:54
Dernière modification le : samedi 27 janvier 2018 - 01:31:44

Lien texte intégral

Identifiants

Collections

Citation

Konstantin Avrachenkov, Nelly Litvak, Marina Sokol, Don Towsley. Quick Detection of Nodes with Large Degrees. Internet Mathematics, Taylor & Francis, 2014, 10 (1-2), pp.1-19. 〈http://www.tandfonline.com/toc/uinm20/10/1-2#.VIWw8_mG98E〉. 〈10.1080/15427951.2013.798601〉. 〈hal-01092304〉

Partager

Métriques

Consultations de la notice

204