TY - JOUR
T1 - On designing networks resilient to clique blockers
AU - Zhong, Haonan
AU - Mahdavi Pajouh, Foad
AU - A. Prokopyev, Oleg
N1 - Publisher Copyright:
© 2022 Elsevier B.V.
PY - 2023/5/16
Y1 - 2023/5/16
N2 - 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.
AB - 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.
KW - Integer programming
KW - Network design
KW - Network resiliency
KW - Networks
KW - Vertex clique blockers
UR - http://www.scopus.com/inward/record.url?scp=85139031228&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85139031228&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2022.09.013
DO - 10.1016/j.ejor.2022.09.013
M3 - Article
AN - SCOPUS:85139031228
SN - 0377-2217
VL - 307
SP - 20
EP - 32
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 1
ER -