Quick detection of nodes with large degrees

Avrachenkov, K. and Litvak, N. and Sokol, M. and Towsley, D. (2012) Quick detection of nodes with large degrees. In: 9th International Workshop on Algorithms and Models for the Web Graph, WAW 2012, 22-23 June 2012, Halifax, NS, Canada.

PDF
Restricted to UT campus only: Request a copy
303Kb

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 $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. $\tilde{O}(n^2)$
Item Type:	Conference or Workshop Item
Copyright:	© 2012 Springer
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Stochastic Operations Research (SOR)
Link to this item:	http://purl.utwente.nl/publications/82137
Official URL:	http://dx.doi.org/10.1007/978-3-642-30541-2_5
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page