Boosting(机器学习)
计算机科学
人工智能
边界(拓扑)
树(集合论)
数据挖掘
模式识别(心理学)
稳健性(进化)
电子邮件
算法
数据建模
算法设计
数学
决策树
机器学习
无线传感器网络
树形结构
梯度升压
滤波理论
领域(数学)
作者
Wei Wei,Hui Guo,Peng Li,Tao Ma,Qinghui Zhang
标识
DOI:10.1109/tii.2026.3690809
摘要
Protecting critical infrastructure can significantly improve the resilience of complex networks. When resilience is measured by vertex connectivity, a common strategy is to shield vertices against foreseeable network anomalies. However, optimal methods can only be applied to small-scale graphs due to the high computational complexity of the NP-hard shielding problem, while existing approximation algorithms tend to over-shield, resulting in low efficiency, and some methods may even suffer from accuracy loss. To solve this problem, we first introduce the concept of optimal trimmed traversal trees, which identify necessary shielding vertices based on cut properties through a limited number of traversals. We then develop a novel vertex set called the inner boundary and demonstrate through ablation analysis that it significantly improves both computational efficiency and shielding cost. Finally, a coupling-tree-based mechanism is designed to determine the final set of vertices to be shielded. Experimental results show that the proposed algorithm achieves the same shielding effect as the optimal solution, and the speedup can be no less than$10^{6}$relative to the optimal algorithm. On million-vertex graphs, the method maintains over 99.9% shielding coverage and significantly outperforms recent algorithms in both protection cost and runtime, requiring at most about 20 s.
科研通智能强力驱动
Strongly Powered by AbleSci AI