Attacking the Core Structure of Complex Network

作     者：Zhou, Bo Lv, Yuqian Wang, Jinhuan Zhang, Jian Xuan, Qi 

作者机构：Zhejiang Univ Technol Inst Cyberspace Secur Coll Informat Engn Hangzhou 310023 Peoples R China Zhejiang Inst Commun Dept Intelligent Control Hangzhou 311112 Peoples R China PCL Res Ctr Networks & Commun Peng Cheng Lab Shenzhen 518000 Peoples R China Utron Technol Co Ltd Hangzhou 310056 Peoples R China 

出 版 物：《IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS》 (IEEE Trans. Computat. Soc. Syst.)

年 卷 期：2023年第10卷第4期

页      面：1428-1442页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Key R&D Program of Zhejiang [2022C01018] National Natural Science Foundation of China [U21B2001, 61973273] Zhejiang Provincial Natural Science Foundation of China [LR19F030001] Research and Development Center of Transport Industry of New Generation of Artificial Intelligence Technology [202102H] 

主　　题：Adversarial attack AI security graph data mining k-core decomposition network science social network structural robustness 

摘      要：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 a 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 article, we investigate the robustness of the k-core structure under adversarial attacks by deleting edges, for the first time. First, we give the general definition of the 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 the 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 marie graph algorithms. An open-source implementation is available at https://***/Yocenly/COREATTACCK.