Protection of Large Sparse Network Through Optimal Cropped Depth-First Traversal Tree
Wei Wei, Qiuyuan Hu, Qinghui Zhang, Peng Li · IEEE Transactions on Network Science and Engineering · 2025
The robustness of the network is its ability to withstand unexpected failures. There is an urgent need to enhance the robustness of sparse networks as they are prone to breakage. Among the various ways to enhance network robustness measured by the edge connectivity of the entire network, shielding candidate edges is a popular method when redundant edges are not affordable. However, existing tree-cutting favors dense graphs with exponential cropped-tree growth of search space, but the search space only scales linearly in sparse graphs. We explore sparse-graph limitations by extending cropping to maximum depth while maintaining sublinear overhead, leveraging ancestor-node constraints and cropping-chain theorems for optimal efficiency. Compared with the optimal algorithm, the results in representative network types show that the robustness measurement of small-scale graphs can be enhanced to 100%, and the ratio of acceleration can be greater than$10^{5}$. In large-scale graphs with millions of nodes, robustness can be improved to over 99%, while the time can be as low as tens of seconds.