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 (8)

• Uncovering the overlapping community structure of complex networks in nature and society
• Critical phenomena in complex networks
• Clique percolation in random networks
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• Component sizes in networks with arbitrary degree distributions
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Maximum matching on random graphs
• Solution-space structure of (some) optimization problems

Cited by in corpus (9)

• Explosive transitions in complex networks' structure and dynamics: percolation and synchronization
• Emergence of bimodality in controlling complex networks
• Articulation Points in Complex Networks
• Controllability of multiplex, multi-timescale networks
• Mixed order transition and condensation in exactly soluble one dimensional spin model
• Mixed-order phase transition of the contact process near multiple junctions
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Method for estimating critical exponents in percolation processes with low sampling
• Phase-transitions of the random bond Potts chain with long-range interactions