K-Core decomposition is a very simple algorithm, originating from statistical mechanics for investigating graph properties. I found a nice paper (k-core decomposition: a tool for the visualization of large scale networks, by
José Ignacio Alvarez-Hamelin, Luca Dall'Asta, Alain Barrat, Alessandro Vespignani, NIPS 18, 2006, describing the algorithm. The algorithm proceeds as follows:
In the first round, all nodes with one or less edges are removed from the graph, and all their edges are deleted. In the second round, all nodes with two edges or less are removed from the graph and their edges deleted. Similarly, at the i-th iteration all nodes with less than i neighbors are removed from the graph. Note that removal of a node with k or fewer neighbors is done recursively. If removal (with the k links) exposes a new site with now less than k ngbrs it is removed in the current iteration as well.
The above image taken from the NIPS paper above, shows 3 iterations of the K-core algorithm. In the first iteration the blue nodes
are removed. In the second iteration the yellow nodes are removed. Finally we are left with the red nodes which are the core of this sample network.
The output of the K-cores algorithm is a single number for each node: its core assignment. The algorithm has been used by Prof. Kirkpatrick for investigating Internet topology and reported here.
Below you can find an image from the above NIPS paper which depicts application of the algorithm into France Internet domain:
Anyway, now the K-core algorithm is supported as part of the Graphlab clustering library. You are welcome to try it out on your own network!
No comments:
Post a Comment