Abstract
We introduce a -leaf removal algorithm as a generalization of the so-called leaf removal algorithm. In this pruning algorithm, vertices of degree smaller than , 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 -core (-core). Performing this pruning for the sequence of natural numbers , we decompose the network into a hierarchy of progressively nested -cores. We present an analytical framework for description of -core percolation for undirected uncorrelated networks with arbitrary degree distributions (configuration model). To confirm our results, we also derive rate equations for the -leaf removal algorithm which enable us to obtain the structural characteristics of the -cores in another way. Also we apply our algorithm to a number of real-world networks and perform the -core decomposition for them.
2 More- Received 1 August 2018
- Revised 9 December 2018
DOI:https://doi.org/10.1103/PhysRevE.99.022312
©2019 American Physical Society