Generalized k-cores of networks under attack with limited knowledge

Network theory has been used as an effective approach for understanding and controlling many real-world large-scale systems. A significant aspect of network operation is its robustness against failures and attacks. Here, we develop a theoretical framework for two classes of network attack with limited knowledge, namely, min-n and max-n attacks, where only n nodes are observed and a node with smallest or largest degree is removed at a time until a fraction 1 − p of nodes are attacked. We study the effect of these attacks on the generalized k-core (Gk-core) of the network, which is obtained by implementing a k-leaf pruning process, removing progressively nodes with degree smaller than k alongside their nearest neighbors. This removal process can be viewed as a generation of the ordinary k-core decomposition. It is found that the G2-core undergoes a continuous phase transition with respect to p while Gk-core shows a first-order percolation transition for k ≥ 3 under both types of attacks for all n. We reveal that knowing one more node during attacks, improving from n = 1 to n = 2, turns out to be most beneficial in terms of changing the robustness of Gk-core in both directions. Moreover, it is shown that degree heterogeneity plays a role in robustness as prioritizing attack on small-degree nodes in heterogeneous networks may help consolidate the Gk-core, but also in stability where hub nodes act like anchors stabilizing the Gk-core structure. Our results offer insight into the design of resilient complex systems and evaluation of network robustness and stability.