Distributed k-core Decomposition of Dynamic Graphs
13 December 2012
/ routing
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. In this poster, 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.