On designing networks resilient to clique blockers

Haonan Zhong, Foad Mahdavi Pajouh and Prokopyev, Oleg A．

European Journal of Operational Research, 2023, vol. 307, issue 1, 20-32

Abstract: 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.

Keywords: Networks; Integer programming; Network design; Network resiliency; Vertex clique blockers (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722007251
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:307:y:2023:i:1:p:20-32

DOI: 10.1016/j.ejor.2022.09.013

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().