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 du, and it has n neighbors with degree less than k, then u's degree becomes du − n, and it will be also pruned if k > du − 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, there is a refinement (possibly empty) of the k-core of a graph G, for which there exists at least k paths between any two pairs of vertices of G. This concept is called structural cohesion in sociology[1] and vertex-connectivity in graph theory, and is equivalent via the Menger theorem to a k-component, a maximal graph that cannot be disconnected by fewer than k nodes. .

Contents

[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

[edit] Footnotes

  1. ^ James Moody and Douglas R. White. 2003 Social Cohesion and Embeddedness: A hierarchical conception of social groups. American Sociological Review 68(1):1-25.