  The concept of k-core, which indicates the largest induced subgraph where
each node has k or more neighbors, plays a significant role in measuring the
cohesiveness and the engagement of a network, and it is exploited in diverse
applications, e.g., network analysis, anomaly detection, community detection,
etc. Recent works have demonstrated the vulnerability of k-core under malicious
perturbations which focuses on removing the minimal number of edges to make a
whole k-core structure collapse. However, to the best of our knowledge, there
is no existing research concentrating on how many edges should be removed at
least to make an arbitrary node in k-core collapse. Therefore, in this paper,
we make the first attempt to study the Targeted k-node Collapse Problem (TNCP)
with four novel contributions. Firstly, we offer the general definition of TNCP
problem with the proof of its NP-hardness. Secondly, in order to address the
TNCP problem, we propose a heuristic algorithm named TNC and its improved
version named ATNC for implementations on large-scale networks. After that, the
experiments on 16 real-world networks across various domains verify the
superiority of our proposed algorithms over 4 baseline methods along with
detailed comparisons and analyses. Finally, the significance of TNCP problem
for precisely evaluating the resilience of k-core structures in networks is
validated.
