Heterogeneous k-core versus bootstrap percolation on complex networks

We introduce the heterogeneous k-core, which generalizes the k-core, and contrast it with bootstrap percolation. Vertices have a threshold r(i), that may be different at each vertex. If a vertex has fewer than r(i) neighbors it is pruned from the network. The heterogeneous k-core is the subgraph remaining after no further vertices can be pruned. If the thresholds r(i) are 1 with probability f, or k >= 3 with probability 1 - f, the process can be thought of as a pruning process counterpart to ordinary bootstrap percolation, which is an activation process. We show that there are two types of transitions in this heterogeneous k-core process: the giant heterogeneous k-core may appear with a continuous transition and there may be a second discontinuous hybrid transition. We compare critical phenomena, critical clusters, and avalanches at the heterogeneous k-core and bootstrap percolation transitions. We also show that the network structure has a crucial effect on these processes, with the giant heterogeneous k-core appearing immediately at a finite value for any f > 0 when the degree distribution tends to a power law P(q) similar to q(-gamma) with gamma < 3.