Quick detection of nodes with large degrees

DOI10.1007/978-3-642-30541-2_5MaRDI QIDQ2900585zbMATH OpenOpenAlexFDO

Authors Nelly Litvak, Marina Sokol, Don Towsley, Konstantin Avrachenkov

Publication date 23 July 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.3261

Mathematics Subject Classification ID

Vertex degrees (05C07) Graph algorithms (graph-theoretic aspects) (05C85) Network protocols (68M12) Graph theory (including graph drawing) in computer science (68R10)

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

Recommendations

• Quick detection of nodes with large degrees
• A fast algorithm to find all high-degree vertices in graphs with a power-law degree sequence
• A fast algorithm to find all high degree vertices in graphs with a power law degree sequence
• Quick detection of top-k personalized PageRank lists
• Fast Low-Cost Estimation of Network Properties Using Random Walks

Cited in

(4)

• I/O-efficient calculation of H-group closeness centrality over disk-resident graphs
• Quick detection of nodes with large degrees
• A fast algorithm to find all high-degree vertices in graphs with a power-law degree sequence
• Fast Low-Cost Estimation of Network Properties Using Random Walks

This page was built for publication: Quick detection of nodes with large degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2900585)