  The concept of k-core in complex networks plays a key role in many
applications, e.g., understanding the global structure, or identifying
central/critical nodes, of a network. A malicious attacker with jamming ability
can exploit the vulnerability of the k-core structure to attack the network and
invalidate the network analysis methods, e.g., reducing the k-shell values of
nodes can deceive graph algorithms, leading to the wrong decisions. In this
paper, we investigate the robustness of the k-core structure under adversarial
attacks by deleting edges, for the first time. Firstly, we give the general
definition of targeted k-core attack, map it to the set cover problem which is
NP-hard, and further introduce a series of evaluation metrics to measure the
performance of attack methods. Then, we propose $Q$ index theoretically as the
probability that the terminal node of an edge does not belong to the innermost
core, which is further used to guide the design of our heuristic attack
methods, namely COREATTACK and GreedyCOREATTACK. The experiments on a variety
of real-world networks demonstrate that our methods behave much better than a
series of baselines, in terms of much smaller Edge Change Rate (ECR) and False
Attack Rate (FAR), achieving state-of-the-art attack performance. More
impressively, for certain real-world networks, only deleting one edge from the
k-core may lead to the collapse of the innermost core, even if this core
contains dozens of nodes. Such a phenomenon indicates that the k-core structure
could be extremely vulnerable under adversarial attacks, and its robustness
thus should be carefully addressed to ensure the security of many graph
algorithms.
