We analytically describe the architecture of randomly damaged uncorrelated networks as a set of successively enclosed substructures—k-cores. The k-core is the largest subgraph where vertices have at least k interconnections. We find the structure of k-cores, their sizes, and their birthpoints—the bootstrap percolation thresholds. We show that in networks with a finite mean number z2 of the second-nearest neighbors, the emergence of a k-core is a hybrid phase transition. In contrast, if z2 diverges, the networks contain an infinite sequence of k-cores which are ultrarobust against random damage.
%0 Journal Article
%1 Dorogovtsev2006KCore
%A Dorogovtsev, S. N.
%A Goltsev, A. V.
%A Mendes, J. F. F.
%D 2006
%I American Physical Society
%J Physical Review Letters
%K phase\_transitions percolation critical-phenomena networks k-core
%N 4
%P 040601+
%R 10.1103/physrevlett.96.040601
%T \$k\$-Core Organization of Complex Networks
%U http://dx.doi.org/10.1103/physrevlett.96.040601
%V 96
%X We analytically describe the architecture of randomly damaged uncorrelated networks as a set of successively enclosed substructures—k-cores. The k-core is the largest subgraph where vertices have at least k interconnections. We find the structure of k-cores, their sizes, and their birthpoints—the bootstrap percolation thresholds. We show that in networks with a finite mean number z2 of the second-nearest neighbors, the emergence of a k-core is a hybrid phase transition. In contrast, if z2 diverges, the networks contain an infinite sequence of k-cores which are ultrarobust against random damage.
@article{Dorogovtsev2006KCore,
abstract = {{We analytically describe the architecture of randomly damaged uncorrelated networks as a set of successively enclosed substructures—k-cores. The k-core is the largest subgraph where vertices have at least k interconnections. We find the structure of k-cores, their sizes, and their birthpoints—the bootstrap percolation thresholds. We show that in networks with a finite mean number z2 of the second-nearest neighbors, the emergence of a k-core is a hybrid phase transition. In contrast, if z2 diverges, the networks contain an infinite sequence of k-cores which are ultrarobust against random damage.}},
added-at = {2019-06-10T14:53:09.000+0200},
author = {Dorogovtsev, S. N. and Goltsev, A. V. and Mendes, J. F. F.},
biburl = {https://www.bibsonomy.org/bibtex/27382589ef011deae3f5e18ec568bf4e0/nonancourt},
citeulike-article-id = {1263642},
citeulike-linkout-0 = {http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal\&id=PRLTAO000096000004040601000001\&idtype=cvips\&gifs=yes},
citeulike-linkout-1 = {http://link.aps.org/abstract/PRL/v96/e040601},
citeulike-linkout-2 = {http://dx.doi.org/10.1103/physrevlett.96.040601},
citeulike-linkout-3 = {http://link.aps.org/abstract/PRL/v96/i4/e040601},
citeulike-linkout-4 = {http://link.aps.org/pdf/PRL/v96/i4/e040601},
doi = {10.1103/physrevlett.96.040601},
interhash = {5cfc560065a5d2be9c0dfa194826218f},
intrahash = {7382589ef011deae3f5e18ec568bf4e0},
journal = {Physical Review Letters},
keywords = {phase\_transitions percolation critical-phenomena networks k-core},
month = feb,
number = 4,
pages = {040601+},
posted-at = {2008-12-01 18:33:51},
priority = {4},
publisher = {American Physical Society},
timestamp = {2019-08-01T16:09:09.000+0200},
title = {{\$k\$-Core Organization of Complex Networks}},
url = {http://dx.doi.org/10.1103/physrevlett.96.040601},
volume = 96,
year = 2006
}