Robustness and Strong Attack Tolerance of Low-Diameter Networks
Robustness and Strong Attack Tolerance of Low-Diameter Networks
复制标题
小直径网络的鲁棒性和抗攻击能力强
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
V. Boginski
中科院分区：
文献类型：
--
作者：
Alexander Veremyev;V. Boginski
本章分析了限制直径网络的最佳攻击网络设计和增强策略。在多个故障之后，网络组件（节点和/或边缘）的直径是随机的还是“靶向”。攻击公差，而网络的属性仅在节点/边缘故障后仅维护常规连接（对直径没有明确限制），例如在k连接网络的情况下，称为“弱”攻击公差。 R-Robust 2-Club的概念是唯一保证具有强大的攻击公差属性的直径-2网络配置（即，保持连接性和直径2）证明，如果所有边缘都具有相同的施工成本，那么最佳的R-Obust 2-Club网络设计的问题具有精确的分析解决方案，需要O（RN）构造的边缘，这使得这作为常规的稀疏连接网络，我们的成本效益不对称。考虑的概念和结果。
This chapter analyzes optimal attack-tolerant network design and augmentation strategies for bounded-diameter networks. In the definitions of attack tolerance used in this chapter, we generally require that a network has a guaranteed ability to maintain not only the overall connectivity, but also preserve the same diameter after multiple failures of network components (nodes and/or edges), regardless of whether these failures are random or targeted. This property is referred to as “strong” attack tolerance, whereas the property of a network to maintain just the regular connectivity after node/edge failures (with no explicit restriction on the diameter), such as in the case of K-connected networks, is referred to as “weak” attack tolerance. We analyze necessary and sufficient conditions for guaranteed “weak” and “strong” attack tolerance properties for fixed-diameter networks, including the important special case of diameter-2 (two-hop) networks. We demonstrate that the recently introduced concept of an R-robust 2-club is the only diameter-2 network configuration that is guaranteed to have a strong attack tolerance property (i.e., maintain both connectivity and diameter 2) after any R − 1 edges are deleted. Furthermore, we demonstrate that if all edges have the same construction cost, the problem of optimal R-robust 2-club network design has an exact analytical solution that requires O(Rn) constructed edges, which makes this configuration asymptotically as cost-efficient as a regular sparse connected network. We also give linear 0–1 formulations for related network design and augmentation problems with different edge construction costs, which are NP-hard in the general case. Illustrative examples are provided to demonstrate the considered concepts and results.