On designing networks resilient to clique blockers
On designing networks resilient to clique blockers
复制标题
DOI：
10.1016/j.ejor.2022.09.013
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
Haonan Zhong;F. M. Pajouh;O. Prokopyev
中科院分区：
文献类型：
--
作者：
Haonan Zhong;F. M. Pajouh;O. Prokopyev
网络系统的鲁棒性和脆弱性分析通常使用顶点阻塞器的概念进行。特别是，在最小代价顶点阻塞团问题中，我们寻求具有最小总阻塞代价的顶点子集，使得在被阻塞的图中（在顶点被阻塞之后）任何剩余团的权重被某个预定义参数所上限。粗略地说，我们的目标是以尽可能小的代价破坏网络，以保证网络不包含具有大权重的结构元素的内聚（例如，密切相关）组；这样的群体被建模为加权集团。在本文中，我们的重点是设计对集团拦截器具有弹性的网络。具体来说，我们在网络中构建额外的连接（边），我们的目标是确保（以新添加边的最小可能代价）对抗性决策者（或随机故障的最坏情况实现）不能以足够低的代价破坏网络（即其内聚组的权重）。该方法有助于对网络系统中有影响的集群的有效形成和保存进行建模。我们首先探索问题的结构性质。然后，基于整数规划和组合分支定界技术，给出了若干精确解方案。最后，在随机生成和现实网络实例的计算研究中探讨了我们的方法的性能。
Robustness and vulnerability analysis of networked systems is often performed using the concept of vertex blockers. In particular, in the minimum cost vertex blocker clique problem, we seek a subset of vertices with the minimum total blocking cost such that the weight of any remaining clique in the interdicted graph (after the vertices are blocked) is upper bounded by some pre-defined parameter. Loosely speaking, we aim at disrupting the network with the minimum possible cost in order to guarantee that the network does not contain cohesive (e.g., closely related) groups of its structural elements with large weights; such groups are modeled as weighted cliques. In this paper, our focus is on designing networks that are resilient to clique blockers. Specifically, we construct additional connections (edges) in the network and our goal is to ensure (at the minimum possible cost of newly added edges) that the adversarial decision-maker (or the worst-case realization of random failures) cannot disrupt the network (namely, the weight of its cohesive groups) at some sufficiently low cost. The proposed approach is useful for modeling effective formation and preservation of influential clusters in networked systems. We first explore structural properties of our problem. Then, we develop several exact solution schemes based on integer programming and combinatorial branch-and-bound techniques. Finally, the performance of our approaches is explored in a computational study with randomly-generated and real-life network instances.