Targeted k-node collapse problem: Towards understanding the robustness of local k-core structure

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 engagement of a network, and it is exploited in diverse applications, e.g., network analysis, anomaly detection, community detection, etc. However, recent studies have demonstrated the vulnerability of k-core under malicious perturbations which focus on removing the minimal number of edges to make k-core structures collapse. Despite this, to the best of our knowledge, no existing research has yet concentrated on the minimal number of edges that must be removed to collapse a specific node in the k-core. To address this issue, in this paper, we make the first attempt to study the robustness of individual nodes in k-core and propose the Targeted k-node Collapse Problem (TNCP) with three novel contributions. Firstly, we offer a general definition of TNCP problem with a proof of its NP-hardness. Secondly, in order to cover the TNCP problem, we propose a heuristic algorithm named TNC and its improved version named ATNC for implementations on large-scale networks. Finally, experiments on 20 real-world networks across various domains verify the superiority of our proposed algorithms over 6 baseline methods with detailed comparisons and analyses. Resource related to our study is publicly available at https://github.com/Yocenly/TNCP.