| HAL-Inria | Publications, software ... of Inria's scientists |
Journal articles
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 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.
https://hal.inria.fr/hal-01092304
Contributor : Konstantin Avrachenkov <>
Submitted on : Monday, December 8, 2014 - 3:08:54 PM
Last modification on : Thursday, September 24, 2020 - 10:22:03 AM
Contributor : Konstantin Avrachenkov <>
Submitted on : Monday, December 8, 2014 - 3:08:54 PM
Last modification on : Thursday, September 24, 2020 - 10:22:03 AM
Links full text
