k-Core Organization of Complex Networks

2005/09/30 by S. N. Dorogovtsev, S. N. Dorogovt︠s︡ev, A. V. Goltsev +1 · 18 citations
Computer Science · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Computer science #Core (optical fiber) #Graph theory and applications #Opinion Dynamics and Social Influence #cond-mat.stat-mech #cs.NI #math-ph #math.MP #physics.soc-ph

paper · pdf · doi:10.1103/physrevlett.96.040601

published as Phys. Rev. Lett. 96, 040601 (2006) · 5 pages, 3 figures

openalex publication_date 2006/02/02 · arxiv created 2006/02/28 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05

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 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.

Citations

• Thermodynamic limit of the first-order phase transition in the Kuramoto model
• Community structure in social and biological networks
• Clustering in complex networks. II. Percolation properties
• Bootstrap percolation on a Bethe lattice
• Error and attack tolerance of complex networks
• Statistical mechanics of complex networks
• Evolution of networks
• Network structure and minimum degree
• A model of Internet topology using k -shell decomposition
• Uncovering the overlapping community structure of complex networks in nature and society

Cited by

• Percolation on complex networks: Theory and application
• The rank and layer distributions in random recursive trees
• Hidden transition in multiplex networks
• Sufficient conditions of endemic threshold on metapopulation networks
• The jamming transition is a k-core percolation transition
• Entropy of network ensembles
• Tricritical Point in Heterogeneousk-Core Percolation
• Network geometry
• Analytical approach to the dynamics of facilitated spin models on random networks
• Percolation of networks with directed dependency links
• Color-avoiding percolation
• Failure-recovery model with competition between failures in complex networks: a dynamical approach
• Cascades on a class of clustered random networks
• Analytical results for bond percolation andk-core sizes on clustered networks
• Phase transitions in cooperative coinfections: Simulation results for networks and lattices
• A Unified Approach to Percolation Processes on Multiplex Networks
• Deciphering the global organization of clustering in real complex networks
• History-dependent percolation on multiplex networks