K-core Organization of Complex Networks

By Sergey N. Dorogovtsev, Alexander V. Goltsev, José Fernando Ferreira Mendes. Physical Review Letters, 2005

666 citations recorded by the source corpus.

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 zeta2 of the second-nearest neighbors, the emergence of a k-core is a hybrid phase transition. In contrast, if zeta2 diverges, the networks contain an infinite sequence of k-cores which are ultrarobust against random damage.

Subfields: Geometry and Topology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/ca6854ef438767e8c589fccbb891266a68a3de2a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

In Statistical and Nonlinear Physics

Citations in the corpus

Robustness and resilience of complex networks (2024, neutral): “One is the so-called k -core percolation, in which all the nodes with degree less than k are removed, iteratively 116 .”
The Kuramoto model in complex networks (2015, background): “This particular kind of phase transitions is known as hybrid phase transition and is observed in other dynamical processes, such as in k-core [241, 257] and bootstrap percolation [258] and in avalanches in interdependent networks [259] as well.”
The H-index of a network node and its relation to degree and coreness (2016, background): “The coreness of a node is measured by k -core decomposition 23 , and a larger coreness value indicates that the node is more centrally located in the network.”
Effective Community Search for Large Attributed Graphs (2016, background): “A common notion of structure cohesiveness is that the minimum degree of all the vertices that appear in the community has to be k or more [26, 25, 2, 7, 5, 18].”
Vital nodes identification in complex networks (2016, background): “[37] argued that the location of a node (whether in the central place) is more important than its degree, and they applied the k-core decomposition [38, 39] that iteratively decomposes the network according to the residual degree of the nodes.”
Recent advances in percolation theory and its applications (2015, background): “There have been introduced various modifications of the ordinary percolation to model different statistical phenomena or even at the level of mathematical curiosity in building up a modified version with a possibly discontinuous phase transition [54, 55, 56, 57].”
Critical phenomena in complex networks (2007, methodology): “Let us discuss the k-core percolation in the configuration model with degree distribution P (q) by using intuitive arguments based on the tree ansatz (Dorogovtsev et al., 2006a,b; Goltsev et al., 2006).”
SuSPect: Enhanced Prediction of Single Amino Acid Variant (SAV) Phenotype Using Network Features (2014, background): “Coreness is defined using k-core centrality [52], an iterative process in which nodes and their adjacent edges are removed from the network if their degree is less than an integer k.”
Searching for superspreaders of information in real-world social media (2014, background): “To check the effect of such ‘‘activity sampling’’ on k S , k in and PageRank, we perform sampling experiment with LJ data.”