Earlier this year I gave at the talk at the March 4th, 2011 meeting of SCONE (Scottish Networking Event), on “Distributed k-shell graph decomposition”. The talk is on the k-core or k-shell of a graph, given in papers such as Seidman’s “Network Structure and Minimum Degree”, and it presents a new, efficient, distributed, algorithm for computing the maximal k-core membership of each node.
Paul Jakma said
Short paper published by CoNext 2012, with an overview of proof, and describing an extension to allow the algorithm to work on dynamic graphs.