Quick detection of nodes with large degrees

Konstatin Avrachenkov, Nelly Litvak, Marina Sokol, Don Towsley

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
38 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

Fingerprint

Complex networks
Complex Networks
Random walk
Vertex of a graph
Average Complexity
Stopping Criterion
Adjacency
Deterministic Algorithm
Numerical Experiment
Experiments

Keywords

  • Random walk
  • Detection of nodes with the largest degrees
  • METIS-306037
  • Stopping criteria
  • EWI-25090
  • Top $k$ list
  • Complex networks
  • IR-91970

Cite this

Avrachenkov, Konstatin ; Litvak, Nelly ; Sokol, Marina ; Towsley, Don. / Quick detection of nodes with large degrees. In: Internet mathematics. 2014 ; Vol. 10, No. 1-2. pp. 1-19.
@article{6a332671d7824be296e18a12090a1cb6,
title = "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 $\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.",
keywords = "Random walk, Detection of nodes with the largest degrees, METIS-306037, Stopping criteria, EWI-25090, Top $k$ list, Complex networks, IR-91970",
author = "Konstatin Avrachenkov and Nelly Litvak and Marina Sokol and Don Towsley",
note = "eemcs-eprint-25090",
year = "2014",
month = "5",
day = "5",
doi = "10.1080/15427951.2013.798601",
language = "English",
volume = "10",
pages = "1--19",
journal = "Internet mathematics",
issn = "1542-7951",
publisher = "Taylor & Francis",
number = "1-2",

}

Quick detection of nodes with large degrees. / Avrachenkov, Konstatin; Litvak, Nelly; Sokol, Marina; Towsley, Don.

In: Internet mathematics, Vol. 10, No. 1-2, 05.05.2014, p. 1-19.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Quick detection of nodes with large degrees

AU - Avrachenkov, Konstatin

AU - Litvak, Nelly

AU - Sokol, Marina

AU - Towsley, Don

N1 - eemcs-eprint-25090

PY - 2014/5/5

Y1 - 2014/5/5

N2 - 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.

AB - 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.

KW - Random walk

KW - Detection of nodes with the largest degrees

KW - METIS-306037

KW - Stopping criteria

KW - EWI-25090

KW - Top $k$ list

KW - Complex networks

KW - IR-91970

U2 - 10.1080/15427951.2013.798601

DO - 10.1080/15427951.2013.798601

M3 - Article

VL - 10

SP - 1

EP - 19

JO - Internet mathematics

JF - Internet mathematics

SN - 1542-7951

IS - 1-2

ER -