K-core

From Wikipedia, the free encyclopedia

K-cores in graph theory were introduced by Seidman in 1983 and by Bollobas in 1984 as a method of (destructively) simplifying graph topology to aid in analysis and visualization. They have been more recently defined as the following by Batagelj et al: given a graph $G = {V, E}$ with vertices set $V$ and edges set $E$ , the k-core is computed by pruning all the vertices (with their respective edges) with degree less than $k$ . That means that if a vertex $u$ has degree $d u$ , and it has $n$ neighbors with degree less than $k$ , then $u$ 's degree becomes $d u - n$ , and it will be also pruned if $k > d u - n$ .

This operation can be useful to filter or to study some properties of the graphs. For instance, when you compute the 2-core of graph $G$ , you are cutting all the vertices which are in a tree part of graph. (A tree is a graph with no loops).

Note that, in the $k$ -core of a graph $G$ , there exists at least $k$ paths between any two pairs of vertices of $G$ .

[edit] Coreness

A vertex $u$ has coreness $c$ if it belongs to the $c$ -core but not to $(c + 1)$ -core.

[edit] Applications

The k-core decomposition can be used to

1) Study the properties of each k-core 2) Filter the information 3) Visualization

Biology was one of the first fields where the $k$ -core decomposition was applied. An example is the prediction of the protein functions : "Prediction of Protein Functions Based on K-Cores of Protein-Protein Interaction Networks and Amino AcidSequences", Md. Altaf-Ul-Amin, K. Nishikata, T. Koma, T. Miyasato, Y. Shinbo, Md. Arifuzzaman, C. Wada, M. Maeda, T. Oshima, H. Mori and S. Kanaya.

Another interesting work on the same area concerns the study of the centrality of protein function : "Peeling the Yeast protein network", Wuchty and Almaas.

An example of the second type of applications is given by "Dynamic Analysis of the Autonomous System Graph", Gaertler and M. Patrignani: the elimination of nodes with low degree allows to obtain a more useful graph.

Finally, some examples of the third application are the free tools Pajek, which analyses the adjacency matrix of k-cores;and LaNet-vi, which represents in two dimensions the k-core decomposition of a graph.

[edit] References

B. Bollobas, The evolution of sparse graphs, in Graph Theory and Combinatorics, Proc. Cambridge Combinatorial Conf. in honor of Paul Erdos, Academic Press, 1984, 35-57. (References: [1], [2])
S. B. Seidman, Network structure and minimum degree, Social Networks 5:269-287.
Size and Connectivity of the k-core of a Random Graph. Łuczak, Tomasz.
Generalized Cores. V. Batagelj, M. Zaversnik.
k-Core Organization of Complex Networks. Dorogovtsev, Goltsev, J. F. F. Mendes