K-core

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, 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 [James Moody and Douglas R. White. 2003 "Social Cohesion and Embeddedness: A hierarchical conception of social groups." American Sociological Review 68(1):1-25.] 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. .

Coreness

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

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 : [http://www.jsbi.org/journal/GIW03/GIW03P158.pdf"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 : [http://www.nd.edu/~swuchty/Download/coresProteomics.pdf "Peeling the Yeast protein network", Wuchty and Almaas] .

An example of the second type of applications is given by [http://www.dia.uniroma3.it/~patrigna/papers/files/ASGraphDynamicAnalysis.pdf "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 [http://vlado.fmf.uni-lj.si/pub/networks/pajek/ Pajek] , which analyses the adjacency matrix of k-cores;and [http://xavier.informatics.indiana.edu/lanet-vi/ LaNet-vi] , which represents in two dimensions the k-core decomposition of a graph.

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: [http://citeseer.ist.psu.edu/context/542937/0] , [http://citeseer.ist.psu.edu/context/661153/0] )
* S. B. Seidman, "Network structure and minimum degree," Social Networks 5:269-287.
* [http://mathcs.emory.edu/~tomasz/papers/core.ps Size and Connectivity of the k-core of a Random Graph] . Łuczak, Tomasz.
* [http://arxiv.org/abs/cs.DS/0202039 Generalized Cores] . V. Batagelj, M. Zaversnik.
* [http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=PLEEE8000073000005056101000001&idtype=cvips&gifs=yes k-Core Organization of Complex Networks] . Dorogovtsev, Goltsev, Mendes

Footnotes