Quick detection of nodes with large degrees

Konstantin Avrachenkov, Nelly Litvak, Marina Sokol, Don Towsley

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 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.
Original languageEnglish
Title of host publicationAlgorithms and Models for the Web Graph
Subtitle of host publication9th International Workshop, WAW 2012, Halifax, NS, Canada, June 22-23, 2012. Proceedings
EditorsAnthony Bonato, Jeannette Janssen
Place of PublicationBerlin, Germany
PublisherSpringer
Pages54-65
Number of pages12
ISBN (Electronic)978-3-642-30541-2
ISBN (Print)978-3-642-30540-5
DOIs
Publication statusPublished - 2012
Event9th International Workshop on Algorithms and Models for the Web Graph, WAW 2012 - Halifax, Canada
Duration: 22 Jun 201223 Jun 2012
Conference number: 9

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume7323
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Workshop on Algorithms and Models for the Web Graph, WAW 2012
Abbreviated titleWAW
CountryCanada
CityHalifax
Period22/06/1223/06/12

    Fingerprint

Keywords

  • Detection of nodes with the largest degrees
  • Random walk
  • Top k list
  • Complex networks
  • Stopping criteria

Cite this

Avrachenkov, K., Litvak, N., Sokol, M., & Towsley, D. (2012). Quick detection of nodes with large degrees. In A. Bonato, & J. Janssen (Eds.), Algorithms and Models for the Web Graph: 9th International Workshop, WAW 2012, Halifax, NS, Canada, June 22-23, 2012. Proceedings (pp. 54-65). (Lecture Notes in Computer Science; Vol. 7323). Berlin, Germany: Springer. https://doi.org/10.1007/978-3-642-30541-2_5