Skip to Main content Skip to Navigation
Conference papers

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 the top $k$ list of nodes with the largest degrees 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-00764220
Contributor : Konstantin Avrachenkov <>
Submitted on : Wednesday, December 12, 2012 - 3:49:56 PM
Last modification on : Thursday, September 24, 2020 - 10:22:03 AM
Long-term archiving on: : Wednesday, March 13, 2013 - 3:55:25 AM

File

Paper8WAW12.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Konstantin Avrachenkov, Nelly Litvak, Marina Sokol, Don Towsley. Quick Detection of Nodes with Large Degrees. WAW'12: The 9th Workshop on Algorithms and Models for the Web Graph, Jun 2012, Halifax, Canada. pp.54-65, ⟨10.1007/978-3-642-30541-2_5⟩. ⟨hal-00764220⟩

Share

Metrics

Record views

383

Files downloads

473