通过最优裁剪深度优先遍历树保护大型稀疏网络

《IEEE Transactions on Network Science and Engineering》：Protection of Large Sparse Network Through Optimal Cropped Depth-First Traversal Tree

稀疏网络鲁棒性提升研究提出基于最大深度剪枝和链定理的方法，优化搜索空间以兼顾效率与效果，小规模图实现100%鲁棒性，加速比超10^5，大规模图99%以上鲁棒性，耗时降至秒级。

　　

摘要：

网络的鲁棒性是指其抵御意外故障的能力。由于稀疏网络容易发生故障，因此迫切需要提高其鲁棒性。在通过整个网络的边连接性来衡量网络鲁棒性的各种方法中，当无法承受冗余边的成本时，屏蔽候选边是一种常用的方法。然而，现有的树切割算法更适用于密集图，其搜索空间的增长呈指数级；而对于稀疏图，搜索空间的增长仅呈线性。我们通过将切割深度扩展到最大值，并利用祖先节点约束和切割链定理来保持亚线性开销，从而探索了稀疏图的局限性，以实现最佳效率。与最优算法相比，在代表性网络类型中的测试结果表明，小规模图的鲁棒性可以提高100%，加速比率可超过10倍。在拥有数百万节点的大规模图中，鲁棒性可以提高至99%以上，同时处理时间可缩短至几十秒。

引言

网络在遭受自然损坏或针对性攻击后仍能继续运行的能力被称为其鲁棒性。鲁棒性对各种规模的网络都至关重要，因为网络中的某个部分很可能会遭受意外损坏。自20世纪70年代以来，许多领域都对网络鲁棒性进行了大量研究[1]，其中一个核心问题是如何提高网络的鲁棒性以抵御故障并从损坏中恢复，但目前仍存在一些关键的研究空白，例如效率问题。