Quick detection of nodes with large degrees

Konstantin Avrachenkov, Nelly Litvak, Marina Sokol, Don Towsley

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)
53 Downloads (Pure)

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 $\mathcal{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.
Original languageEnglish
Pages (from-to)1-19
Number of pages19
JournalInternet mathematics
Volume10
Issue number1-2
DOIs
Publication statusPublished - 5 May 2014

Keywords

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

Fingerprint Dive into the research topics of 'Quick detection of nodes with large degrees'. Together they form a unique fingerprint.

  • Cite this