hal-00670278, version 1

Quick Detection of Nodes with Large Degrees

Konstantin Avrachenkov (, ) ¹, Nelly Litvak () ², Marina Sokol () ¹, Don Towsley () ^a, 3

N° RR-7881 (2012)

• a –  University of Massachusetts Amherst
• 1:  MAESTRO (INRIA Sophia Antipolis)
• 
  INRIA – Université Montpellier II - Sciences et techniques France
• 2:  Faculty of Electrical Engineering, Mathematics and Computer Science [Twente] (EEMCS)
• http://www.utwente.nl/education/eemcs
  University of Twente University of Twente Faculty of EEMCS Postbus 217 7500 AE Enschede Netherlands
• 3:  Department of Computer Science [Amherst]
• http://www.cs.umass.edu/
  University of Massachusetts Computer Science Building 140 Governors Drive University of Massachusetts Amherst, MA 01003-9264 United States

Bibliographic reference

• Type of document: Research reports
• Domain: Computer Science/Networking and Telecommunication
• Title: Quick Detection of Nodes with Large Degrees
• 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 a node with the largest degree 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.
• Full text language: English
• Report type: Research Report
• Publication date: 2012-02-15
• Keywords: Complex networks – detection of nodes with the largest degrees – top k list – random walk – stopping criteria
• Internal note: RR-7881
• Collaboration(s): University of Massachusetts Amherst

Attached file list to this document: 

TEX

logo-inria.eps(378.1 KB)

logo-inria.png(275.1 KB)

pa1bigMaxHit_a0.eps(9.6 KB)

pa1bigMaxHit_a2.eps(9.6 KB)

PA1bigNumEl.eps(39.7 KB)

PA1bigNumEla0.eps(31.3 KB)

pagei.eps(5.5 MB)

pagei.png(26.9 KB)

RR-7881.aux(4.9 KB)

RR-7881.out(396 B)

RR-7881.pdf(362.9 KB)

RR-7881.ps(15.6 MB)

RR-7881.tex(39.1 KB)

RR.dtx(71 KB)

RR.ins(2.1 KB)

RR.pdf(532.6 KB)

RR.sty(15.3 KB)

rrpage1.eps(2.8 MB)

rrpage1.png(47.6 KB)

Uk2002NumEl.eps(36.9 KB)

Uk2002NumEl001.eps(38.1 KB)

PDF

RR-7881.pdf(312.6 KB)

PS

RR-7881.ps(15.7 MB)

• hal-00670278, version 1
• http://hal.inria.fr/hal-00670278
• oai:hal.inria.fr:hal-00670278
• From: Konstantin Avrachenkov <>
• Submitted on: Wednesday, 15 February 2012 10:05:05
• Updated on: Wednesday, 15 February 2012 11:22:27