Quick Detection of Nodes with Large Degrees

Konstantin Avrachenkov 1 Nelly Litvak 2 Marina Sokol 1 Don Towsley 3
1 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
2 EEMCS - Faculty of Electrical Engineering, Mathematics and Computer Science [Twente]
3 Department of Computer Science [Amherst]
Abstract : Our goal is to quickly find top $k$ lists of nodes with the largest degrees in large complex networks. 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 $\mbox{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 the 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 which requires very little knowledge about the structure of the network.
Type de document :
Communication dans un congrès
Anthony Bonato and Jeannette Janssen. WAW'12: The 9th Workshop on Algorithms and Models for the Web Graph, Jun 2012, Halifax, Canada. Springer, 7323, pp.54-65, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-30541-2_5〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00764220
Contributeur : Konstantin Avrachenkov <>
Soumis le : mercredi 12 décembre 2012 - 15:49:56
Dernière modification le : samedi 27 janvier 2018 - 01:31:43
Document(s) archivé(s) le : mercredi 13 mars 2013 - 03:55:25

Fichier

Paper8WAW12.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA

Citation

Konstantin Avrachenkov, Nelly Litvak, Marina Sokol, Don Towsley. Quick Detection of Nodes with Large Degrees. Anthony Bonato and Jeannette Janssen. WAW'12: The 9th Workshop on Algorithms and Models for the Web Graph, Jun 2012, Halifax, Canada. Springer, 7323, pp.54-65, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-30541-2_5〉. 〈hal-00764220〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

313

Téléchargements de fichiers

147

Contact


archive-ouverte@inria.fr