some notes on k-core decomposition 06-22-2015d1010

2015-06-22

some notes on k-core decomposition 06-22-2015d1010

k-core decomposition
-An interesting way to describe the topology of real networks in terms of subgraphs is by using the k-core decomposition. The k-core is obtained by removing from the network all vertices with degree smaller than k. After such a removal, some vertices in the resulting network may have degree less than k; such vertices are removed and the network is analyzed again. When no further removal is possible, the non-empty resulting subgraph is called k-core of the original network 182. An important application of such a concept is in network visualization 183
--ref 182: S.N. Dorogovtsev, A.V. Goltsev and J.F.F. Mendes, Phys. Rev. Lett. 96 40601 (2006).
---k-Core Organization of Complex Networks
-Recent studies about the properties and applications of k-core decomposition in real networks have been performed 184, 185. Important statistical properties of k-core are discussed by Dorogvtesev et al. 182 and investigations about topology of the Internet using k-core decomposition are presented by Carmi et al. 186. Moreover, protein interaction networks are analyzed in terms of k-cores by Wuchty and Almaas 187. The k-core approach has also been applied in order to predict the function of proteins 188.
--ref 184: S.N. Dorogovtsev, J.F.F. Mendes, A.M. Povolotsky and A.N. Samukhin, Phys. Rev.

Lett. 95 195701 (2005).

---k-core percolation and k-core organization of complex networks
--ref 185: A.V. Goltsev, S.N. Dorogovtsev and J.F.F. Mendes, Phys. Rev. E 73 056101 (2006).
---k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
----article behind paywall
--ref 186: S. Carmi, S. Havlin, S. Kirkpatrick, Y. Shavitt and E. Shir, cs.NI/0607080 (2006).
---MEDUSA - New Model of Internet Topology Using k-shell Decomposition
--ref 187: S. Wuchty and E. Almaas, Proteomics 5 444 (2005).
---Peeling the yeast protein network
--ref 188: M. Altaf-Ul-Amin, K. Nishikata, T. Koma, T. Miyasato, Y. Shinbo, M. Arifuzzaman,

C. Wada, M. Maeda, T. Oshima, H. Mori and S. Kanaya, Genome Inform. 14 498
(2003).

---Prediction of Protein Functions Based on K-Cores of Protein-Protein Interaction Networks and Amino Acid Sequences