Which Link Matters? Maintaining Connectivity of Uncertain Networks Under Adversarial Attack
文献类型：期刊论文
| 作者 | Tang, Jianzhi1; Fu, Luoyi2; Long, Fei3; Wang, Xinbing1; Chen, Guihai2; Zhou, Chenghu4 |
| 刊名 | IEEE TRANSACTIONS ON MOBILE COMPUTING
 |
| 出版日期 | 2024-03-01 |
| 卷号 | 23期号:3页码:2039-2053 |
| 关键词 | Connectivity maintenance mobile network security uncertain graph |
| ISSN号 | 1536-1233 |
| DOI | 10.1109/TMC.2023.3248629 |
| 通讯作者 | Tang, Jianzhi(tangjianzhi@sjtu.edu.cn) |
| 英文摘要 | This article studies connectivity maintenance in uncertain networks under adversarial attack, where a defender conceals crucial links to prevent the largest connected component from being decomposed by an attacker. In contrast with its static counterpart, connectivity maintenance in uncertain networks involves additional probing on links to determine their existence. Therefore, by modeling an uncertain network as a random graph with each link associated with an existence probability and a probing cost, our goal is to design a defensive strategy for link selection that maximizes the expected size of the largest remaining connected component with the minimum expected probing cost, and moreover, the strategy should be independent of the attacking patterns. To this end, we first unravel the computational complexity of the problem by proving its NP-hardness, and then propose optimal defensive strategies based on dynamic programming and multi-objective optimization. Due to the prohibitive computational cost of optimality, two approximate defensive strategies are further designed to pursue decent performance with quasilinear complexity, in which the first one is a heuristic approach that quantifies the link vulnerability through an analogy from the degree centrality of a vertex in static networks to the connectivity weight of a link in uncertain networks, and the second one is an adaptive greedy policy incorporating the minimax rule from game theory, which minimizes the possible loss suffered by the defender in a worst-case scenario and has a constant approximation ratio. Extensive experiments on both synthetic and real-world network datasets under diverse attacking patterns demonstrate the superiority of the proposed strategies over baselines. |
| 资助项目 | NSF China |
| WOS研究方向 | Computer Science ; Telecommunications |
| 语种 | 英语 |
| WOS记录号 | WOS:001167016100021 |
| 出版者 | IEEE COMPUTER SOC |
| 资助机构 | NSF China |
| 源URL | [http://ir.igsnrr.ac.cn/handle/311030/203933]  |
| 专题 | 中国科学院地理科学与资源研究所 |
| 通讯作者 | Tang, Jianzhi |
| 作者单位 | 1.Shanghai Jiao Tong Univ, Dept Elect Engn, Shanghai 200240, Peoples R China 2.Shanghai Jiao Tong Univ, Dept Comp Sci & Engn, Shanghai 200240, Peoples R China 3.Xinhua News Agcy, State Key Lab Media Convergence Prod Technol & Sys, Beijing 100803, Peoples R China 4.Chinese Acad Sci, Inst Geog Sci & Nat Resources Res, Beijing 100101, Peoples R China |
| 推荐引用方式 GB/T 7714 | Tang, Jianzhi,Fu, Luoyi,Long, Fei,et al. Which Link Matters? Maintaining Connectivity of Uncertain Networks Under Adversarial Attack[J]. IEEE TRANSACTIONS ON MOBILE COMPUTING,2024,23(3):2039-2053. |
| APA | Tang, Jianzhi,Fu, Luoyi,Long, Fei,Wang, Xinbing,Chen, Guihai,&Zhou, Chenghu.(2024).Which Link Matters? Maintaining Connectivity of Uncertain Networks Under Adversarial Attack.IEEE TRANSACTIONS ON MOBILE COMPUTING,23(3),2039-2053. |
| MLA | Tang, Jianzhi,et al."Which Link Matters? Maintaining Connectivity of Uncertain Networks Under Adversarial Attack".IEEE TRANSACTIONS ON MOBILE COMPUTING 23.3(2024):2039-2053. |
入库方式： OAI收割
来源：地理科学与资源研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。