k-core organization of complex networks

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 birth points -- the bootstrap percolation thresholds. We show that in networks with a finite mean number z_2 of the second-nearest neighbors, the emergence of a k-core is a hybrid phase transition. In contrast, if z_2 diverges, the networks contain an infinite sequence of k-cores which are ultra-robust against random damage.

5 pages, 3 figures

References in corpus (20)

• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Error and attack tolerance of complex networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Random graphs with arbitrary degree distributions and their applications
• Evolution of networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Critical phenomena in complex networks
• New Model of Internet Topology Using k-shell Decomposition
• MEDUSA - New Model of Internet Topology Using k-shell Decomposition
• Clique percolation in random networks
• Percolation Critical Exponents in Scale-Free Networks
• Thermodynamic limit of the first-order phase transition in the Kuramoto model
• Percolation and Epidemic Thresholds in Clustered Networks
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• Clustering in complex networks. II. Percolation properties
• On $k$-Core Percolation in Four Dimensions
• Rigidity percolation in a field
• Nested Subgraphs of Complex Networks

Cited by in corpus (230)

• Characterization of complex networks: A survey of measurements
• Critical phenomena in complex networks
• Vital nodes identification in complex networks
• The Kuramoto model in complex networks
• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• New Model of Internet Topology Using k-shell Decomposition
• MEDUSA - New Model of Internet Topology Using k-shell Decomposition
• Robustness and resilience of complex networks
• Ranking spreaders by decomposing complex networks
• Recent advances in percolation theory and its applications
• Avalanche Collapse of Interdependent Network
• Explosive transitions in complex networks' structure and dynamics: percolation and synchronization
• Percolation on complex networks: Theory and application
• Searching for superspreaders of information in real-world social media
• Small vulnerable sets determine large network cascades in power grids
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• "Explosive Percolation" Transition is Actually Continuous
• Anatomy of an online misinformation network
• A k-shell decomposition method for weighted networks
• The entropy of network ensembles
• Ranking the spreading influence in complex networks
• High-accuracy approximation of binary-state dynamics on networks
• The entropy of randomized network ensembles
• Network Geometry
• Bootstrap Percolation on Complex Networks
• Identification of core-periphery structure in networks
• Explosive Phenomena in Complex Networks
• Percolation and Epidemic Thresholds in Clustered Networks
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• A measure of individual role in collective dynamics
• Congestion phenomena on complex networks
• The k-core as a predictor of structural collapse in mutualistic ecosystems
• Clustering in complex networks. I. General formalism
• Recent advances and open challenges in percolation
• Dynamics of social contagions with memory of non-redundant information
• Kuramoto model with frequency-degree correlations on complex networks
• Resilience and rewiring of the passenger airline networks in the United States
• Immunization and targeted destruction of networks using explosive percolation
• The unreasonable effectiveness of tree-based theory for networks with clustering
• Resilience of networks with community structure behaves as if under an external field
• Competing activation mechanisms in epidemics on networks
• Cascading Failures in Complex Networks
• Clustering in complex networks. II. Percolation properties
• Local cluster aggregation models of explosive percolation
• Core percolation on complex networks
• Distinct types of eigenvector localization in networks
• Cascades on a class of clustered random networks
• Articulation Points in Complex Networks
• Higher-order percolation processes on multiplex hypergraphs
• k-Core percolation on multiplex networks
• Dynamical Systems on Networks: A Tutorial
• Computational Socioeconomics
• Emergence of core-peripheries in networks
• Heterogeneous-k-core versus Bootstrap Percolation on Complex Networks
• Weak percolation on multiplex networks
• Recent advances of percolation theory in complex networks
• Relating Topological Determinants of Complex Networks to Their Spectral Properties: Structural and Dynamical Effects
• Inducing Effect on the Percolation Transition in Complex Networks
• Hybrid Phase Transition into an Absorbing State: Percolation and Avalanches
• Hybrid Percolation Transition in Cluster Merging Processes: Continuously Varying Exponents
• $k$-core percolation on complex networks: Comparing random, localized and targeted attacks
• Eigenvector localization in real networks and its implications for epidemic spreading
• Leveraging local h-index to identify and rank influential spreaders in networks
• Deciphering the global organization of clustering in real complex networks
• Tricritical point in heterogeneous k-core percolation
• Covering Problems and Core Percolations on Hypergraphs
• Critical dynamics of the k-core pruning process
• Comparative evaluation of community-aware centrality measures
• Organization of modular networks
• Identifying an influential spreader from a single seed in complex networks via a message-passing approach
• Large deviations of cascade processes on graphs
• Effects of human dynamics on epidemic spreading in Côte d'Ivoire
• Remarks on Bootstrap Percolation in Metric Networks
• Phase Transitions in Cooperative Coinfections: Simulation Results for Networks and Lattices
• Stochastic cellular automata model of neural networks
• Fluctuations in percolation of sparse complex networks
• Generalization of core percolation on complex networks
• Controlling the uncertain response of real multiplex networks to random damage
• Accelerating Community Detection by Using K-core Subgraphs
• The localization of non-backtracking centrality in networks and its physical consequences
• Rhythmogenic neuronal networks, pacemakers, and k-cores
• Clique percolation in random graphs
• Equivalence of several generalized percolation models on networks
• On the number of circuits in random graphs
• Giant components in directed multiplex networks
• Chinese Internet AS-level Topology
• Robustness and fragility of the susceptible-infected-susceptible epidemic models on complex networks
• Exotic Critical Behavior of Weak Multiplex Percolation
• Universal mechanism for hybrid percolation transitions
• Effective potential approach to hybrid synchronization transitions
• Critical phenomena in heterogeneous k-core percolation
• Dynamic facilitation picture of a higher-order glass singularity
• Diverse types of percolation transitions
• Structural stability of interaction networks against negative external fields
• Critical behavior of $k$-core percolation: Numerical studies
• Superspreading k-cores at the center of COVID-19 pandemic persistence
• Origin of the mixed-order transition in multiplex networks: the Ashkin-Teller model
• SIR epidemics with long range infection in one dimension
• On the study of force-balance percolation
• Analytical results for bond percolation and k-core sizes on clustered networks
• Percolation on random networks with arbitrary k-core structure
• Critical phenomena and noise-induced phase transitions in neuronal networks
• The jamming transition is a k-core percolation transition
• Correlated percolation and tricriticality
• Cascades on clique-based graphs
• The nature of hypergraph $k$-core percolation problems
• Percolation on networks with weak and heterogeneous dependency
• Interconnections between networks act like an external field in first-order percolation transitions
• Dynamical Immunization Strategy for Seasonal Epidemics
• Topological structure and the H-index in complex networks
• Heterogeneous excitable systems exhibit Griffiths phases below hybrid phase transitions
• History-dependent percolation on multiplex networks
• k-core percolation on interdependent and interconnected multiplex networks
• Controversial information spreads faster and further in Reddit
• $(k,q)$-core decomposition of hypergraphs
• Scaling and universality in glass transition
• Reversible bootstrap percolation: Fake news and fact checking
• Generalized model for $k$-core percolation and interdependent networks
• Mixed-order phase transition of the contact process near multiple junctions
• Critical exponents of the explosive percolation transition
• Bootstrap percolation on geometric inhomogeneous random graphs
• Percolation and the effective structure of complex networks
• Prediction and mitigation of nonlocal cascading failures using graph neural networks
• Two Types of Discontinuous Percolation Transitions in Cluster Merging Processes
• Insights into bootstrap percolation: Its equivalence with k-core percolation and the giant component
• A unified approach to percolation processes on multiplex networks
• Finding influential spreaders from human activity beyond network location
• Jamming percolation and glassy dynamics
• Color-avoiding percolation
• Core organization of directed complex networks
• Dynamics of k-core percolation in a random graph
• Border trees of complex networks
• Microscopic models of mode-coupling theory: the $F_{12}$ scenario
• Shortest-path percolation on random networks
• k-core structure of real multiplex networks
• Activation thresholds in epidemic spreading with motile infectious agents on scale-free networks
• A framework for cascade size calculations on random networks
• Optimal redundancy against disjoint vulnerabilities in networks
• Decelerated spreading in degree-correlated networks
• K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases
• Modeling Epidemic Spreading through Public Transit using Time-Varying Encounter Network
• Variational Community Partition with Novel Network Structure Centrality Prior
• Failure-recovery model with competition between failures in complex networks: a dynamical approach
• Dynamics of k-core percolation
• Critical behavior of a two-step contagion model with multiple seeds
• Bond and site color-avoiding percolation in scale free networks
• Extended-range percolation in complex networks
• Highly Clustered Complex Networks in the Configuration Model: Random Regular Small-World Network
• Exotic phase transitions of k-cores in clustered networks
• Nested Subgraphs of Complex Networks
• The dynamical collision network in granular gases
• Optimal Stabilization of Boolean Networks through Collective Influence
• On the discovery of social roles in large scale social systems
• Unified framework for hybrid percolation transitions based on microscopic dynamics
• K-Scaffold subgraphs of Complex networks
• Interdependent transport via percolation backbones in spatial networks
• Core-Periphery in Networks: An Axiomatic Approach
• Critical phenomena of a hybrid phase transition in cluster merging dynamics
• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
• Fast asynchronous updating algorithms for k-shell indices
• Random Graphs with Prescribed $K$-Core Sequences: A New Null Model for Network Analysis
• The evolution of k-shell in syndication networks reveals financial performance of venture capital institutions
• Universal features of cluster numbers in percolation
• Percolation of networks with directed dependency links
• Explosive percolation in finite dimensions
• Non-Markovian random walks characterize network robustness to nonlocal cascades
• Efficient Core Maintenance in Large Dynamic Graphs
• Higher-order triadic percolation on random hypergraphs
• Network science Ising states of matter
• Two faces of greedy leaf removal procedure on graphs
• Cultural Convergence: Insights into the behavior of misinformation networks on Twitter
• Random node reinforcement and $K$-core structure of complex networks
• Two golden times in two-step contagion models
• Statistical analysis of edges and bredges in configuration model networks
• Dynamical phase separation on rhythmogenic neuronal networks
• Multi-layer network approach in modeling epidemics in an urban town
• Enhanced robustness of single-layer networks with redundant dependencies
• Sample-to-sample fluctuations in real-network ensembles
• Sufficient conditions of endemic threshold on metapopulation networks
• Hyperparameter-free and Explainable Whole Graph Embedding
• Maximizing the Collective Learning Effects in Regional Economic Development
• Generalized $k$-core pruning process on directed networks
• Hierarchical cycle-tree packing model for $K$-core attack problem
• Phase transitions on a class of generalized Vicsek-like models of collective motion
• Metabolic plasticity in synthetic lethal mutants: viability at higher cost
• Susceptible-infected-susceptible model on networks with eigenvector localization
• Double transitions and hysteresis in heterogeneous contagion processes
• Vulnerability and Resilience of Social Engagement: Equilibrium Theory
• Percolate or die: Multi-percolation decides the struggle between competing innovations
• Predicting Nodal Influence via Local Iterative Metrics
• Core language brain network for fMRI-language task used in clinical applications
• Determinable and interpretable network representation for link prediction
• Evolving complex networks with conserved clique distributions
• No-exclaves percolation on random networks
• $K$-selective percolation: A simple model leading to a rich repertoire of phase transitions
• Polymer collapse and crystallization in bond fluctuation models
• Link rewiring with local information--induced hybrid percolation transitions
• The behavior of rich-club coefficient in scale-free networks
• Stochastic quorum percolation and noise focusing in neuronal networks
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Critical avalanches of Susceptible-Infected-Susceptible dynamics in finite networks
• Identifying influential subpopulations in metapopulation epidemic models using message-passing theory
• Induced Percolation on Networked Systems
• Comparison of theoretical approaches for epidemic processes with waning immunity in complex networks
• Hidden transition in multiplex networks
• Dissecting Ethereum Blockchain Analytics: What We Learn from Topology and Geometry of Ethereum Graph
• Emergent networks in fractional percolation
• Analytical approach to the dynamics of facilitated spin models on random networks
• D-chain tomography of networks: a new structure spectrum and an application to the SIR process
• Core Influence Mechanism on Vertex-Cover Problem through Leaf-Removal-Core Breaking
• Lowest Degree Decomposition of Complex Networks
• Discontinuous percolation via suppression of neighboring clusters in a network
• Discontinuous transition in explosive percolation via local suppression
• Color-avoiding percolation in edge-colored Erdős-Rényi graphs
• Thermodynamic analysis of diverse percolation transitions
• Universality in percolation of arbitrary Uncorrelated Nested Subgraphs
• Level statistics for quantum $k$-core percolation
• Probing the robustness of nested multi-layer networks
• On the complexity of color-avoiding site and bond percolation
• Computation of K-Core Decomposition on Giraph
• Collective Influence of Multiple Spreaders Evaluated by Tracing Real Information Flow in Large-Scale Social Networks
• Monolingual and bilingual language networks in healthy subjects using functional MRI and graph theory
• Social Network of Extreme Tweeters: A Case Study
• WEM: A Node Importance Algorithm in Weighted Networks
• Improving the accuracy of the k-shell method by removing redundant links-from a perspective of spreading dynamics
• A cavity approach to optimization and inverse dynamical problems
• Crash dynamics of interdependent networks
• Aggregate-networks and p-cores of monoflow partially overlapped multilayer systems
• Metanetworks of artificially evolved regulatory networks
• Impacts of bridging nodes on the epidemic activation mechanisms