Generalization of core percolation on complex networks

Abstract

We introduce a $k$-leaf removal algorithm as a generalization of the so-called leaf removal algorithm. In this pruning algorithm, vertices of degree smaller than $k$, together with their first nearest neighbors and all incident edges are progressively removed from a random network. As the result of this pruning the network is reduced to a subgraph which we call the Generalized $k$-core ($Gk$-core). Performing this pruning for the sequence of natural numbers $k$, we decompose the network into a hierarchy of progressively nested $Gk$-cores. We present an analytical framework for description of $Gk$-core percolation for undirected uncorrelated networks with arbitrary degree distributions (configuration model). To confirm our results, we also derive rate equations for the $k$-leaf removal algorithm which enable us to obtain the structural characteristics of the $Gk$-cores in another way. Also we apply our algorithm to a number of real-world networks and perform the $Gk$-core decomposition for them.

9 pages, 9 figures

References in corpus (23)

• The structure of scientific collaboration networks
• Random graphs with arbitrary degree distributions and their applications
• Identification of influential spreaders in complex networks
• Critical phenomena in complex networks
• Universal Behavior of Load Distribution in Scale-free Networks
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• What's in a crowd? Analysis of face-to-face behavioral networks
• New Model of Internet Topology Using k-shell Decomposition
• MEDUSA - New Model of Internet Topology Using k-shell Decomposition
• k-core organization of complex networks
• Cut-offs and finite size effects in scale-free networks
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Core percolation on complex networks
• Core percolation in random graphs: a critical phenomena analysis
• k-Core percolation on multiplex networks
• Inducing Effect on the Percolation Transition in Complex Networks
• Analytic solution of a static scale-free network model
• Statistical Mechanics of the Minimum Dominating Set Problem
• Intrinsic degree-correlations in static model of scale-free networks
• Exactly solvable model with two conductor-insulator transitions driven by impurities
• Dynamics of heuristic optimization algorithms on random graphs
• Generalized model for $k$-core percolation and interdependent networks
• Core organization of directed complex networks

Cited by in corpus (7)

• Percolation on complex networks: Theory and application
• Superspreading k-cores at the center of COVID-19 pandemic persistence
• Reversible bootstrap percolation: Fake news and fact checking
• k-core structure of real multiplex networks
• Random node reinforcement and $K$-core structure of complex networks
• A local algorithm and its percolation analysis of bipartite $z$-matching problem
• Statistical mechanics of the minimum vertex cover problem in stochastic block models