Core percolation on complex networks

Abstract

As a fundamental structural transition in complex networks, core percolation is related to a wide range of important problems. Yet, previous theoretical studies of core percolation have been focusing on the classical Erdős-Rényi random networks with Poisson degree distribution, which are quite unlike many real-world networks with scale-free or fat-tailed degree distributions. Here we show that core percolation can be analytically studied for complex networks with arbitrary degree distributions. We derive the condition for core percolation and find that purely scale-free networks have no core for any degree exponents. We show that for undirected networks if core percolation occurs then it is always continuous while for directed networks it becomes discontinuous when the in- and out-degree distributions are different. We also apply our theory to real-world directed networks and find, surprisingly, that they often have much larger core sizes as compared to random models. These findings would help us better understand the interesting interplay between the structural and dynamical properties of complex networks.

17 pages, 6 figures

References in corpus (29)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Epidemic spreading in scale-free networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Catastrophic cascade of failures in interdependent networks
• Random graphs with arbitrary degree distributions and their applications
• Identification of influential spreaders in complex networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Critical phenomena in complex networks
• Universal Behavior of Load Distribution in Scale-free Networks
• Interdependent networks: Reducing the coupling strength leads to a change from a first to second order percolation transition
• k-core organization of complex networks
• Clique percolation in random networks
• Controlling edge dynamics in complex networks
• "Explosive Percolation" Transition is Actually Continuous
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• The number of matchings in random graphs
• Core percolation in random graphs: a critical phenomena analysis
• Component sizes in networks with arbitrary degree distributions
• Vertex cover problem studied by cavity method: Analytics and population dynamics
• Analytic solution of a static scale-free network model
• Statistical mechanics of the vertex-cover problem
• Exactly solvable model with two conductor-insulator transitions driven by impurities
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Maximum matching on random graphs
• On $k$-Core Percolation in Four Dimensions
• Solution-space structure of (some) optimization problems

Cited by in corpus (43)

• Control Principles of Complex Networks
• Explosive transitions in complex networks' structure and dynamics: percolation and synchronization
• Percolation on complex networks: Theory and application
• Emergence of bimodality in controlling complex networks
• Statistical physics approaches to the complex Earth system
• Resilience of networks with community structure behaves as if under an external field
• Articulation Points in Complex Networks
• Controllability of multiplex, multi-timescale networks
• Inducing Effect on the Percolation Transition in Complex Networks
• Covering Problems and Core Percolations on Hypergraphs
• Phase Transitions in Cooperative Coinfections: Simulation Results for Networks and Lattices
• Generalization of core percolation on complex networks
• Resilience and Controllability of Dynamic Collective Behaviors
• Mixed order transition and condensation in exactly soluble one dimensional spin model
• Controllability and maximum matchings of complex networks
• Efficient network immunization under limited knowledge
• Exact extreme value statistics at mixed order transitions
• Bridges in Complex Networks
• Long-range random transverse-field Ising model in three dimensions
• Fluctuation-dominated phase ordering at a mixed order transition
• Network Properties for Robust Multilayer Infrastructure Systems: A Percolation Theory Review
• Mixed-order phase transition of the contact process near multiple junctions
• The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
• Core organization of directed complex networks
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Method for estimating critical exponents in percolation processes with low sampling
• Mixed-order transition in the antiferromagnetic quantum Ising chain in a field
• Phase-transitions of the random bond Potts chain with long-range interactions
• Two faces of greedy leaf removal procedure on graphs
• Generalized $k$-core pruning process on directed networks
• Emergent information dynamics in many-body interconnected systems
• Emergence of biconnected clusters in explosive percolation
• Degree product rule tempers explosive percolation in the absence of global information
• Typical Approximation Performance for Maximum Coverage Problem
• Controllability, matching ratio and graph convergence
• Induced Percolation on Networked Systems
• Control core of undirected complex networks
• A local algorithm and its percolation analysis of bipartite $z$-matching problem
• Discontinuous transition in explosive percolation via local suppression
• Fundamental building blocks of controlling complex networks: A universal controllability framework
• Quantum Potts chain in alternating field
• Reduce the rank calculation of a high-dimensional sparse matrix based on network controllability theory
• Statistical mechanics of the minimum vertex cover problem in stochastic block models