Multi-hop generalized core percolation on complex networks

Recent theoretical studies on network robustness have focused primarily on attacks by random selection and global vision, but numerous real-life networks suffer from proximity-based breakdown. Here we introduce the multi-hop generalized core percolation on complex networks, where nodes with degree less than k and their neighbors within L-hop distance are removed progressively from the network. The resulting subgraph is referred to as G(k,L)-core, extending the recently proposed Gk-core and classical core of a network. We develop analytical frameworks based upon generating function formalism and rate equation method, showing for instance continuous phase transition for G(2,1)-core and discontinuous phase transition for G(k,L)-core with any other combination of k and L. We test our theoretical results on synthetic homogeneous and heterogeneous networks, as well as on a selection of large-scale real-world networks. This unravels, e.g., a unique crossover phenomenon rooted in heterogeneous networks, which raises a caution that endeavor to promote network-level robustness could backfire when multi-hop tracing is involved.