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.
翻译:k-core 概念,它表明每个节点都有或有更多的邻接点的最大引导子集,在衡量网络的凝聚力和参与程度方面起着重要作用,并且被各种应用,例如网络分析、异常检测、社区探测等所利用。 最近的工作表明,k-core在恶意干扰下的脆弱性,这些恶意干扰的重点是消除最小的边缘,使整个 k-core 结构崩溃。然而,根据我们的知识,目前没有集中研究至少应消除多少边缘以使K-core 崩溃成为任意的节点的现有研究。因此,在本文中,我们第一次尝试研究目标 k-node 崩溃问题(TNCP),并作出四项新的贡献。首先,我们用其NP- 硬性证据来说明TRCP 问题的一般定义。第二,为了解决TNCP 问题,我们建议了一种叫跨国公司的超自然算法,其改进版名为ATNC,用于大规模网络的实施。随后,对16个真实世界网络的实验,在各个领域进行详细的K-nordfredistructional 分析,最后核实了我们提议的Kral 4 结构的超标度。