K-core-based attack to the internet: Is it more malicious than degree-based attack?

K-core (k-shell) is an interesting measure that discriminates the core and fringe nodes in a complex network. Recent studies have revealed that some nodes of high k-core values may play a vital role in information diffusion. As a result, one may expect that attacking the nodes of high k-core values preferentially will collapse the Internet easily. To our surprise, however, the experiments on two Internet AS-level topologies show that: Although a k-core-based attack is feasible in reality, it is actually less effective than the classic degree-based attack. Indeed, as indicated by the measure normalized susceptibility, we need to remove 2 % to 3 % more nodes in a k-core-based attack in order to collapse the networks. Further investigation on the nodes in a same shell discloses that these nodes often have drastically varying degrees, among which are the nodes of high k-core values but low degrees. These nodes cannot lead to sufficient link deletions in the early stage of a k-core-based attack, and therefore make it less malicious than a degree-based attack. Finally, a strategy called “ELL” is employed for the Internet enhancement. Experiments demonstrate that “ELL” can greatly improve the Internet robustness at very small costs.