摘要
本文将“具有可达集的最小顶点割”（MVCRS）问题构建为一个优化框架，用于抑制网络系统中僵尸网络的传播，并阐明了其计算复杂性和算法解决方案。在物联网（IoT）网络中，建立防火墙以最小化损害对于应对僵尸网络传播至关重要。我们定义了基本的MVCRS问题，即最小化部署资源的权重总和以及由此产生的传播范围。虽然我们证明了该问题的受限版本是NP完全的，但我们展示了通过将其转化为最大流-最小割问题，可以在多项式时间内解决这一基本权衡优化问题。这为网络安全中的最优资源分配提供了理论基础。实验评估揭示了传统启发式方法的局限性。在基于社区结构的网络中，基于度的贪心算法会忽略关键的桥梁节点，导致实际成本比理论最小成本高出多达72.6%。相反，我们的精确算法始终能够保证最优最小成本（0%的差距），并且在各种拓扑结构下具有较高的统计稳定性。此外，它能够在实际时间限制内高效地处理10万个节点的IoT网络，证明了其在复杂现实世界系统中抑制僵尸网络的可靠性和有效性。
