Quick Detection of Nodes with Large Degrees

Konstantin Avrachenkov; Nelly Litvak; Marina Sokol; Don Towsley

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)

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.

a – University of Massachusetts Amherst
1: MAESTRO (INRIA Sophia Antipolis)
INRIA – Université Montpellier II - Sciences et techniques
2: Faculty of Electrical Engineering, Mathematics and Computer Science [Twente] (EEMCS)
University of Twente
3: Department of Computer Science [Amherst]
University of Massachusetts

Collaboration : University of Massachusetts Amherst

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

See detailed view

Associated documents

PDF :

PS :

arXiv: 1202.3261

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Research reports</head>
<biblStruct type="report" xml:id="hal-00670278"><monogr>
<author><persName><forename>Konstantin</forename><surname>Avrachenkov</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">MAESTRO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Montpellier II - Sciences et techniques</orgName>
</affiliation>
</author>
<author><persName><forename>Nelly</forename><surname>Litvak</surname></persName>
<affiliation>
<orgName type="laboratory">EEMCS</orgName>
<orgName type="team">Faculty of Electrical Engineering, Mathematics and Computer Science [Twente]</orgName>
<country>NL</country>
<orgName type="institution">University of Twente</orgName>
</affiliation>
</author>
<author><persName><forename>Marina</forename><surname>Sokol</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">MAESTRO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Montpellier II - Sciences et techniques</orgName>
</affiliation>
</author>
<author><persName><forename>Don</forename><surname>Towsley</surname></persName>
<affiliation>
<orgName type="team">Department of Computer Science [Amherst]</orgName>
<country>US</country>
<orgName type="institution">University of Massachusetts</orgName>
</affiliation>
</author>
<title type="main" level="m">Quick Detection of Nodes with Large Degrees</title><title type="main" level="m">Quick Detection of Nodes with Large Degrees</title><imprint><biblScope type="publicationDate">2012-02-15</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/hal-00670278</idno><idno type="HALFile">http://hal.inria.fr/hal-00670278/PDF/RR-7881.pdf</idno></biblStruct>
</listBibl>
</listBibl>