Distributed k-core Decomposition of Dynamic Graphs

Paul Jakma, Marcin Orczyk, Colin Perkins, and Marwan Fayed

Poster presented at the ACM CoNEXT Student Workshop, Nice, France, December 2012.


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.

Download: dist-k-shells-conext-sw.pdf

Opinions expressed are my own, and do not represent those of my employers or the organisations that fund my research.