Quick detection of nodes with large degrees

Konstantin Avrachenkov; Nelly Litvak; Marina Sokol; Don Towsley

doi:10.1007/978-3-642-30541-2_5

Quick detection of nodes with large degrees

Konstantin Avrachenkov, Nelly Litvak, Marina Sokol, Don Towsley

Stochastic Operations Research

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	English
Title of host publication	Algorithms and Models for the Web Graph
Subtitle of host publication	9th International Workshop, WAW 2012, Halifax, NS, Canada, June 22-23, 2012. Proceedings
Editors	Anthony Bonato, Jeannette Janssen
Place of Publication	Berlin, Germany
Publisher	Springer
Pages	54-65
Number of pages	12
ISBN (Electronic)	978-3-642-30541-2
ISBN (Print)	978-3-642-30540-5
DOIs	https://doi.org/10.1007/978-3-642-30541-2_5
Publication status	Published - 2012
Event	9th International Workshop on Algorithms and Models for the Web Graph, WAW 2012 - Halifax, Canada Duration: 22 Jun 2012 → 23 Jun 2012 Conference number: 9

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	7323
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Workshop on Algorithms and Models for the Web Graph, WAW 2012
Abbreviated title	WAW
Country/Territory	Canada
City	Halifax
Period	22/06/12 → 23/06/12

Keywords

Detection of nodes with the largest degrees
Random walk
Top k list
Complex networks
Stopping criteria

Access to Document

10.1007/978-3-642-30541-2_5

Cite this

Avrachenkov, K., Litvak, N., Sokol, M., & Towsley, D. (2012). Quick detection of nodes with large degrees. In A. Bonato, & J. Janssen (Eds.), Algorithms and Models for the Web Graph: 9th International Workshop, WAW 2012, Halifax, NS, Canada, June 22-23, 2012. Proceedings (pp. 54-65). (Lecture Notes in Computer Science; Vol. 7323). Springer. https://doi.org/10.1007/978-3-642-30541-2_5

@inproceedings{8f453dc3068241f99344b84108bf3076,

title = "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 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.",

keywords = "Detection of nodes with the largest degrees, Random walk, Top k list, Complex networks, Stopping criteria",

author = "Konstantin Avrachenkov and Nelly Litvak and Marina Sokol and Don Towsley",

year = "2012",

doi = "10.1007/978-3-642-30541-2_5",

language = "English",

isbn = "978-3-642-30540-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "54--65",

editor = "Anthony Bonato and Jeannette Janssen",

booktitle = "Algorithms and Models for the Web Graph",

note = "9th International Workshop on Algorithms and Models for the Web Graph, WAW 2012, WAW ; Conference date: 22-06-2012 Through 23-06-2012",

}

Avrachenkov, K, Litvak, N, Sokol, M & Towsley, D 2012, Quick detection of nodes with large degrees. in A Bonato & J Janssen (eds), Algorithms and Models for the Web Graph: 9th International Workshop, WAW 2012, Halifax, NS, Canada, June 22-23, 2012. Proceedings. Lecture Notes in Computer Science, vol. 7323, Springer, Berlin, Germany, pp. 54-65, 9th International Workshop on Algorithms and Models for the Web Graph, WAW 2012, Halifax, Canada, 22/06/12. https://doi.org/10.1007/978-3-642-30541-2_5

Quick detection of nodes with large degrees. / Avrachenkov, Konstantin; Litvak, Nelly; Sokol, Marina et al.

Algorithms and Models for the Web Graph: 9th International Workshop, WAW 2012, Halifax, NS, Canada, June 22-23, 2012. Proceedings. ed. / Anthony Bonato; Jeannette Janssen. Berlin, Germany : Springer, 2012. p. 54-65 (Lecture Notes in Computer Science; Vol. 7323).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Quick detection of nodes with large degrees

AU - Avrachenkov, Konstantin

AU - Litvak, Nelly

AU - Sokol, Marina

AU - Towsley, Don

N1 - Conference code: 9

PY - 2012

Y1 - 2012

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

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

KW - Detection of nodes with the largest degrees

KW - Random walk

KW - Top k list

KW - Complex networks

KW - Stopping criteria

U2 - 10.1007/978-3-642-30541-2_5

DO - 10.1007/978-3-642-30541-2_5

M3 - Conference contribution

SN - 978-3-642-30540-5

T3 - Lecture Notes in Computer Science

SP - 54

EP - 65

BT - Algorithms and Models for the Web Graph

A2 - Bonato, Anthony

A2 - Janssen, Jeannette

PB - Springer

CY - Berlin, Germany

T2 - 9th International Workshop on Algorithms and Models for the Web Graph, WAW 2012

Y2 - 22 June 2012 through 23 June 2012

ER -

Quick detection of nodes with large degrees

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this