Distributed k-core decomposition of dynamic graphs

Paul Jakma; Marcin Orczyk; Colin Perkins; Marwan Fayed

doi:10.1145/2413247.2413272

Distributed k-core decomposition of dynamic graphs

Paul Jakma^*, Marcin Orczyk, Colin Perkins, Marwan Fayed

^*Corresponding author for this work

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The k-core decomposition can be used to reveal structure in a graph. It is straight-forward to implement using a centralised algorithm with complete knowledge of the graph, but no distributed k-core decomposition algorithm has been published. We present a continuous, distributed, k-core decomposition algorithm for dynamic graphs, outline a proof of correctness, and give initial performance results. We briefly describe an application of this distributed k-core algorithm to landmark selection for compact routing.

Original language	English
Title of host publication	CoNEXT Student 2012 - Proceedings of the ACM Conference on the 2012 CoNEXT Student Workshop
Pages	39-40
Number of pages	2
DOIs	https://doi.org/10.1145/2413247.2413272
Publication status	Published - 1 Dec 2012
Event	2012 ACM CoNEXT Student Workshop, CoNEXT Student 2012 - Nice, France Duration: 10 Dec 2012 → 10 Dec 2012

Conference

Conference	2012 ACM CoNEXT Student Workshop, CoNEXT Student 2012
Country/Territory	France
City	Nice
Period	10/12/12 → 10/12/12

Keywords

Distributed algorithm
Graph decomposition

Access to Document

10.1145/2413247.2413272

Cite this

@inproceedings{819d773e6dec463eaaf6579c3c2510ea,

title = "Distributed k-core decomposition of dynamic graphs",

abstract = "The k-core decomposition can be used to reveal structure in a graph. It is straight-forward to implement using a centralised algorithm with complete knowledge of the graph, but no distributed k-core decomposition algorithm has been published. We present a continuous, distributed, k-core decomposition algorithm for dynamic graphs, outline a proof of correctness, and give initial performance results. We briefly describe an application of this distributed k-core algorithm to landmark selection for compact routing.",

keywords = "Distributed algorithm, Graph decomposition",

author = "Paul Jakma and Marcin Orczyk and Colin Perkins and Marwan Fayed",

year = "2012",

month = dec,

day = "1",

doi = "10.1145/2413247.2413272",

language = "English",

isbn = "9781450317757",

pages = "39--40",

booktitle = "CoNEXT Student 2012 - Proceedings of the ACM Conference on the 2012 CoNEXT Student Workshop",

note = "2012 ACM CoNEXT Student Workshop, CoNEXT Student 2012 ; Conference date: 10-12-2012 Through 10-12-2012",

}

TY - GEN

T1 - Distributed k-core decomposition of dynamic graphs

AU - Jakma, Paul

AU - Orczyk, Marcin

AU - Perkins, Colin

AU - Fayed, Marwan

PY - 2012/12/1

Y1 - 2012/12/1

N2 - The k-core decomposition can be used to reveal structure in a graph. It is straight-forward to implement using a centralised algorithm with complete knowledge of the graph, but no distributed k-core decomposition algorithm has been published. We present a continuous, distributed, k-core decomposition algorithm for dynamic graphs, outline a proof of correctness, and give initial performance results. We briefly describe an application of this distributed k-core algorithm to landmark selection for compact routing.

AB - The k-core decomposition can be used to reveal structure in a graph. It is straight-forward to implement using a centralised algorithm with complete knowledge of the graph, but no distributed k-core decomposition algorithm has been published. We present a continuous, distributed, k-core decomposition algorithm for dynamic graphs, outline a proof of correctness, and give initial performance results. We briefly describe an application of this distributed k-core algorithm to landmark selection for compact routing.

KW - Distributed algorithm

KW - Graph decomposition

UR - http://www.scopus.com/inward/record.url?scp=84872003325&partnerID=8YFLogxK

U2 - 10.1145/2413247.2413272

DO - 10.1145/2413247.2413272

M3 - Conference contribution

AN - SCOPUS:84872003325

SN - 9781450317757

SP - 39

EP - 40

BT - CoNEXT Student 2012 - Proceedings of the ACM Conference on the 2012 CoNEXT Student Workshop

T2 - 2012 ACM CoNEXT Student Workshop, CoNEXT Student 2012

Y2 - 10 December 2012 through 10 December 2012

ER -

Distributed k-core decomposition of dynamic graphs

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this