On Interdicting Dense Clusters in a Network

Haonan Zhong (), Foad Mahdavi Pajouh (), Sergiy Butenko () and Oleg A. Prokopyev ()
Additional contact information
Haonan Zhong: School of Business Management, Yunnan University of Finance and Economics, Kunming 650221, China
Foad Mahdavi Pajouh: School of Business, Stevens Institute of Technology, Hoboken, New Jersey 07030
Sergiy Butenko: Wm Michael Barnes ‘64 Department of Industrial & Systems Engineering, Texas A&M University, College Station, Texas 77843
Oleg A. Prokopyev: Department of Business Administration, University of Zurich, 8032 Zurich, Switzerland

INFORMS Journal on Computing, 2025, vol. 37, issue 4, 1069-1086

Abstract: Given a vertex-weighted undirected graph with blocking costs of its vertices and edges, we seek a minimum cost subset of vertices and edges to block such that the weight of any γ -quasi-clique in the interdicted graph is at most some predefined threshold parameter. The value of γ ∈ ( 0 , 1 ] specifies the edge density of cohesive vertex groups of interest in the network. The considered weighted γ-quasi-clique interdiction problem can be viewed as a natural generalization of several variations of the clique blocker problem previously studied in the literature. From the application perspective, this setting is primarily motivated by the problem of disrupting adversarial (“dark”) networks (e.g., social or communication networks), where γ -quasi-cliques represent “tightly knit” groups of adversaries that we aim to dismantle. We first address the theoretical computational complexity of the problem. We then exploit some basic characterization of its feasible solutions to derive a linear integer programming (IP) formulation. This linear IP model can be solved using a lazy-fashioned branch-and-cut scheme. We also propose a combinatorial branch-and-bound algorithm for solving this problem. The computational performance of the developed exact solution schemes is studied using a test bed of randomly generated and real-life networks. Finally, some interesting insights and observations are also provided using a well-known example of a terrorist network.

Keywords: network interdiction; dense clusters; γ -quasi-cliques; computational complexity; exact algorithms (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0027 (application/pdf)

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:inm:orijoc:v:37:y:2025:i:4:p:1069-1086

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().