K-core Organization of Complex Networks

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.

• Publication year

  2005

• Venue

  Physical Review Letters

• Publication date

  2005-09-05

• Fields of study

  Mathematics, Physics, Computer Science, Medicine

• Identifiers
  DOI 10.1103/PhysRevLett.96.040601arXiv cond-mat/0509102PMID 16486798
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Understanding the mind of a worm: hierarchical network structure underlying nervous system function in C. elegans.

  2008cited by this paper
• Critical phenomena in complex networks

  2007cited by this paper
• Nested subgraphs of complex networks

  2007cited by this paper
• Percolation and epidemic thresholds in clustered networks.

  2006cited by this paper
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects

  2006cited by this paper
• k-core percolation in four dimensions.

  2006cited by this paper
• A model of Internet topology using k-shell decomposition

  2006cited by this paper
• k-core architecture and k-core percolation on complex networks

  2006cited by this paper
• Clustering in complex networks. II. Percolation properties.

  2006cited by this paper
• Evolutionary cores of domain co-occurrence networks

  2005cited by this paper
• K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases

  2005cited by this paper
• Uncovering the overlapping community structure of complex networks in nature and society

  2005cited by this paper
• Clique percolation in random networks.

  2005cited by this paper
• The k-Core and Branching Processes

  2005cited by this paper
• Thermodynamic limit of the first-order phase transition in the Kuramoto model.

  2005cited by this paper
• The onset of jamming as the sudden emergence of an infinite k-core cluster

  2004cited by this paper
• Clustering in complex networks

  2004cited by this paper
• Rigidity percolation in a field.

  2003cited by this paper
• Percolation critical exponents in scale-free networks.

  2002cited by this paper
• Community structure in social and biological networks

  2001cited by this paper
• Statistical mechanics of complex networks

  2001cited by this paper
• Evolution of networks

  2001cited by this paper
• Network robustness and fragility: percolation on random graphs.

  2000cited by this paper
• Random graphs with arbitrary degree distributions and their applications.

  2000cited by this paper
• Error and attack tolerance of complex networks

  2000cited by this paper
• Resilience of the internet to random breakdowns

  2000cited by this paper
• Sudden Emergence of a Giantk-Core in a Random Graph

  1996cited by this paper
• Metastability effects in bootstrap percolation

  1988cited by this paper
• Network structure and minimum degree

  1983cited by this paper
• Bootstrap percolation transitions on real lattices

  1981cited by this paper
• Bootstrap percolation on a Bethe lattice

  1979cited by this paper
• TORINO Repository ISTITUZIONALE

  year unknowncited by this paper

• Recent Progress on Hybrid Percolation Transitions

  2026cites this paper
• A fast algorithm for estimating the maximum <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si27.svg" display="inline" id="d1e559"> <mml:mi>k</mml:mi> </mml:math> -core number in random graphs with giv

  2026cites this paper
• Graphs are maximally expressive for higher-order interactions

  2026cites this paper
• Early warning signals for phase transitions in networks

  2026cites this paper
• Network dismantling with community-based edge percolation

  2026cites this paper
• Human mobility in epidemic modeling

  2026cites this paper
• Tracing carbon flow to unravel carbon lock-in in China through a supernetwork-based perspective for targeted decarbonization

  2026cites this paper
• The Global Food Trade Network as a Complex Adaptive System: A Review of Structure, Evolution, and Resilience

  2026cites this paper
• A similarity laplacian energy perspective on critical node identification in complex networks

  2026cites this paper
• Improved bipartite plots of ecological networks using the k-core decomposition with the BipartGraph application

  2026cites this paper
• Exploring Unknown Social Networks for Discovering Hidden Nodes

  2025cites this paper
• Hypergraph-based modeling of cascading failures with probabilistic node-to-group interactions

  2025cites this paper
• K-core-guided adaptive learning and policy optimization for targeted influence maximization in complex networks

  2025cites this paper
• Identification of critical nodes by fusing propagation probabilities and entropy in binary networks

  2025cites this paper
• Prefer2SD: A Human-in-the-Loop Approach to Balancing Similarity and Diversity in In-Game Friend Recommendations

  2025cites this paper
• Rules, agents and order

  2025cites this paper
• Cascading failures in networks of networks linked by directional and bidirectional hyperlinks.

  2025cites this paper
• TPP: A temporal-enhanced propagation probability model for identifying influential nodes in complex networks

  2025cites this paper
• Balancing Graph Processing Workloads in Heterogeneous CPU-PIM Systems

  2025cites this paper
• Physical Realizations of Interdependent Networks: Analogy to Percolation

  2025cites this paper
• Pivots or Partisans? Proposal-Making Strategy and Status Quo Selection in Congress

  2025cites this paper
• How robust are financial connectedness networks? A network attack assessment

  2025cites this paper
• Unraveling the impact of interaction types on phase separation of intrinsically disordered protein chains.

  2025cites this paper
• A learning-based influence maximization framework for complex networks via K-core hierarchies and reinforcement learning

  2025cites this paper
• Discontinuous transition in explosive percolation via local suppression

  2025cites this paper
• Protection of multilayer network systems from targeted group attacks

  2025cites this paper
• Discontinuous percolation via suppression of neighboring clusters in a network.

  2025cites this paper
• Neighbor-induced damage percolation.

  2025cites this paper
• Bootstrap percolation on hypergraph.

  2025cites this paper
• Exploring the Medication Patterns and Core Prescription Mechanisms of Xiang Jun in Treating Diabetic Nephropathy Based on Data Mining Combined with Network Pharmacology Techniques

  2025cites this paper
• Impacts of bridging nodes on the epidemic activation mechanisms

  2025cites this paper
• Thermodynamic analysis of diverse percolation transitions

  2025cites this paper
• A complex network perspective on brain disease

  2025cites this paper
• Growth-induced percolation on complex networks

  2025cites this paper
• Recovery centrality of system resilience based on network structure and dynamics

  2025cites this paper
• Network Analysis on the Symmetric Coordination in a Reinforcement-Learning-Based Minority Game

  2025cites this paper
• Impact of infectious sources on the vaccination dilemma in networked population

  2025cites this paper
• No-exclaves percolation on random networks

  2024cites this paper
• Shortest-Path Percolation on Random Networks.

  2024cites this paper
• Percolation behavior analysis on n-layer edge-coupled interdependent networks

  2024cites this paper
• Nature of hypergraph k-core percolation problems.

  2024cites this paper
• Local suppression by link rewiring reveals discontinuous percolation transitions

  2024cites this paper
• Deviation Propagation Network for Key Quality Factors Identification of Complex Assembly Systems

  2024cites this paper
• GNN-Based Persistent K-core Community Search in Temporal Graphs

  2024cites this paper
• Network Higher-Order Structure Dismantling

  2024cites this paper
• Accuracy of discrete- and continuous-time mean-field theories for epidemic processes on complex networks.

  2024cites this paper
• Entropy-induced phase transitions in a hidden Potts model.

  2024cites this paper
• Consequences of non-Markovian healing processes on epidemic models with recurrent infections on networks

  2024cites this paper
• Structural robustness of networks with degree-degree correlations between second-nearest neighbors

  2024cites this paper
• GLC: A dual-perspective approach for identifying influential nodes in complex networks

  2024cites this paper
• <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e907" altimg="si11.svg"><mml:mi>H</mml:mi></mml:math>-sequences and 2-step coreness in graphs

  2024cites this paper
• Impaired brain ability of older adults to transit and persist to latent states with well-organized structures at wakeful rest

  2024cites this paper
• H-core decomposition for directed networks and its application

  2024cites this paper
• Robustness analysis of multi-dependency networks: k-core percolation and deliberate attacks

  2024cites this paper
• Robustness and resilience of complex networks

  2024cites this paper
• Transaction graph based key node identification for blockchain regulation

  2024cites this paper
• Restoration seed and plant material supply chains are complex social networks

  2024cites this paper
• Explosive percolation in finite dimensions

  2024cites this paper
• Encoding Individual Activation and Collective Diffusion Capability for Influence Maximization

  2024cites this paper
• Higher-order triadic percolation on random hypergraphs.

  2024cites this paper
• A neural diffusion model for identifying influential nodes in complex networks

  2024cites this paper
• Cascading failures in bipartite networks with directional support links.

  2024cites this paper
• Research on proactive defense and dynamic repair of complex networks considering cascading effects

  2024cites this paper
• Inferring failure coupling strength in complex networks through generative models

  2024cites this paper
• Identifying influential nodes in complex networks via Transformer

  2024cites this paper
• K-core attack, equilibrium K-core, and kinetically constrained spin system

  2024cites this paper
• Targeted <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e3069" altimg="si27.svg"><mml:mi>k</mml:mi></mml:math>-node collapse problem: Towards understanding the robustness of local <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e3074"

  2024cites this paper
• Emergence of Loops in Spatial Networks With Self-Organized Growth

  2024cites this paper
• Structural and flow approaches to complex network systems lesions scale analysis

  2024cites this paper
• Deep Reinforcement Learning for Network Dismantling: A K-Core Based Approach

  2024cites this paper
• Deep Structural Knowledge Exploitation and Synergy for Estimating Node Importance Value on Heterogeneous Information Networks

  2024cites this paper
• Learning to rank influential nodes in complex networks via convolutional neural networks

  2024cites this paper
• Synergistic integration of fragmented transportation networks: When do networks (not) synergize?

  2024cites this paper
• Catastrophic cascade of failures in interdependent hypergraphs.

  2024cites this paper
• EDA-Graph: Graph Signal Processing of Electrodermal Activity for Emotional States Detection

  2024cites this paper
• Unveiling Influence in Networks: A Novel Centrality Metric and Comparative Analysis through Graph-Based Models

  2024cites this paper
• Extended-range percolation in complex networks.

  2023cites this paper
• Identifying influential nodes based on resistance distance

  2023cites this paper
• Finding spatial and temporal features of delay propagation via multi-layer networks

  2023cites this paper
• Graph-based Village Level Poverty Identification

  2023influential citation
• Mixed Order Phase Transitions

  2023cites this paper
• Critical avalanches of susceptible-infected-susceptible dynamics in finite networks.

  2023cites this paper
• The configuration and evolution of Korean automotive supply network: an empirical study based on k-core network analysis

  2023cites this paper
• Effect of random node reinforcement on K -core structure of complex networks

  2023influential citation
• <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si178.svg" display="inline" id="d1e3412"><mml:mrow><mml:mo>(</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>q</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math>-core decomposition of hypergraphs

  2023cites this paper
• Fast Butterfly-Core Community Search For Large Labeled Graphs

  2023cites this paper
• Subnetwork Mining Based on Structure Entropy for Analyzing Depression Disease

  2023cites this paper
• Generalized network dismantling via a novel spectral partition algorithm

  2023cites this paper
• Distributed Approaches to Butterfly Analysis on Large Dynamic Bipartite Graphs

  2023cites this paper
• Hierarchical Cycle-Tree Packing Model for Optimal K-Core Attack

  2023cites this paper
• Models and Methods of Evaluation the Vulnerability of Complex Hierarchical Network Systems

  2023cites this paper
• An Augmented Index-based Efficient Community Search for Large Directed Graphs

  2023cites this paper
• Efficient community-based influence maximization in large-scale social networks

  2023cites this paper
• A network coupling approach to detecting hierarchical linkages between science and technology

  2023cites this paper
• DSCom: A Data-Driven Self-Adaptive Community-Based Framework for Influence Maximization in Social Networks

  2023cites this paper
• Edge Manipulation Approaches for K-Core Minimization: Metrics and Analytics

  2023cites this paper
• Non-Markovian node fragility in cascading failures on random networks

  2023cites this paper
• Predicting nodal influence via local iterative metrics

  2023cites this paper
• Nucleation phenomena and extreme vulnerability of spatial k-core systems

  2023cites this paper
• Structure characterization of complex networks for machine learning

  2023cites this paper