Robust Network Flow Interdiction Problems with Applications to Counter-Narcotics

Source: arXiv:2606.14611 · Published 2026-06-12 · By Diksha Gupta, Madhav Marathe, Anil Vullikanti

TL;DR

This paper addresses the problem of network flow interdiction under structural uncertainty with applications in counter-narcotics. Traditional flow interdiction aims to block or surveil nodes or edges in a network to minimize illicit flow between source and sink, but this is hampered by extremely limited and uncertain data on trafficking networks. The authors propose a novel framework combining data-driven network synthesis and robust optimization to find interdiction strategies that perform well across an ensemble of plausible network realizations, rather than a single fixed network. Using a limited real-world Latin American narcotics dataset (Narcologic network and CCDB flow volumes), they generate stochastic ensembles of trafficking networks consistent with observed regional traffic volumes. Then, they formulate the robust network flow interdiction problem as an integer linear program and solve for strategies minimizing worst-case residual flows across the ensemble. Their results show that even modest interdiction budgets significantly reduce maximum flow, but optimal node selections vary greatly across scenarios. Robust strategies achieve near-optimal performance on all plausible networks, remaining stable despite data uncertainty. This provides a principled method to hedge against network uncertainty and maximize interdiction investment returns in data-scarce security domains.

Key findings

• Generated an ensemble of 2560 trafficking networks from uncertain real-world data; filtered to 230 data-consistent networks using an Average Relative Error threshold η=0.50.
• The ensemble synthesis method matches aggregate regional trafficking volumes from CCDB within low error bounds, as shown by Average Relative Error distributions (Fig 4).
• Robust network flow interdiction strategies, optimized against the entire filtered ensemble, achieve near-optimal reductions in maximum illicit flow on every plausible network realization.
• Optimal interdiction node sets vary substantially across networks and budgets, with robust strategies identifying a smaller stable core set of critical nodes (Fig 7).
• Residual network capacity decreases sharply with interdiction budget in the low budget regime — e.g., small node removals yield large flow reductions (Fig 6).
• Sensitivity analysis shows that model parameters controlling topology pruning and flow assignment (τp, τd, α, δ) significantly influence network consistency and ensemble diversity.
• The ILP formulations proposed yield exact optimal solutions to the binary node interdiction and robust interdiction problems, enabling consistent evaluation across ensembles.

Threat model

The adversary is a narcotics trafficking network routing illicit flow through uncertain and partially observed transportation networks from source (Colombia) to sink (Mexico). The adversary chooses maximal flow paths unknown to the defender. The defender aims to interdict by monitoring or blocking nodes under budget constraints without full knowledge of the exact network structure or capacities. The adversary does not adapt dynamically to interdiction decisions during the interdiction phase modeled here.

Methodology — deep read

1. Threat Model & Assumptions: The adversary is a drug trafficking network moving illicit flow from a known source to sink across uncertain networks. The defender controls interdiction resources to surveil or remove nodes under budget constraints. The defender’s uncertainty lies in the network topology (edges) and edge flow capacities, with only partial regional aggregated flow data. The adversary maximizes flow on whichever network configuration realizes, unknown precisely to the defender.

2. Data: Used a baseline Narcologic network with 156 nodes and 1006 edges representing geographic trafficking routes in Central America. Regional aggregate narcotics flow data comes from the CCDB dataset covering 22 administrative regions. Nodes correspond to fixed geographic locations; edges and capacities must be inferred. The node set and partial regional volume estimates are known; edge sets and capacities are synthesized.

3. Network Ensemble Synthesis: The authors propose a procedure varying parameters (edge pruning radius τp, minimum fractional degree τd, flow scaling α, perturbation δ) to generate edge sets by pruning and probabilistically reinserting long edges, repairing connectivity, and enforcing local degree thresholds to maintain realistic topology. For each generated network, edge-level minimum flows are computed based on regional flow estimates scaled proportionally over incident edges and nodes. Stochastic perturbations ensure diversity.

4. Flow Estimation: For each network, feasibility of flows consistent with regional aggregate volumes is assessed by a linear program minimizing total source flow subject to flow conservation, regional constraints with tolerance ε, and edge lower bounds. Binary search finds the smallest ε ensuring a feasible flow solution, providing edge capacities.

5. Data Consistency Filtering: From 2560 generated networks, 230 are selected whose induced flows have Average Relative Error ≤ 0.50 against CCDB observations to form a realistic scenario ensemble.

6. Integer Linear Programming (ILP): Binary decision variables choose nodes to interdict under budget. The ILPs minimize maximum residual flow in each network by modeling the network cut sets and interdiction. The robust ILP extends to minimize the worst-case residual flow across all scenarios simultaneously.

7. Evaluation: Solved ILPs on filtered ensemble for varying budgets. Measured residual capacity vs budget, node selection frequency distributions, stability metrics (Jaccard similarity) of solutions across scenarios. Analyzed parameter sensitivity of network synthesis.

8. Reproducibility: The paper does not mention releasing code or datasets but uses established public datasets (Narcologic, CCDB) and details the network generation and ILP formulations comprehensively for replication.

Example End-to-End: Starting with the Narcologic baseline and CCDB regional volumes, they estimate missing region flows by averaging neighbors, prune edges longer than τp, probabilistically reinsert some, repair connectivity, and enforce minimum node degree τd. For each resulting network, edge flow lower bounds are determined from regional flows scaled by parameter α and perturbed by δ. A network flow LP (Figure 3) computes edge capacities minimizing the residual error to CCDB volumes. Networks with less than 50% relative error are retained. Then the robust interdiction ILP (Fig 5) computes the node set minimizing worst-case residual flow over all these networks subject to budget constraints. The resulting interdiction sets consistently reduce flow across all sampled plausible networks.

Technical innovations

• A simulation-driven framework combining network science and LP to synthesize ensembles of plausible trafficking networks under extreme data scarcity and partial aggregate observations.
• A novel parameterized network pruning and connectivity repair method generating structurally diverse, realistic network topologies consistent with noisy regional flow data.
• Formulation and ILP solution of a robust network flow interdiction problem minimizing worst-case maximum flow across multiple uncertain network realizations.
• Introduction of a data-consistency filtering metric (Average Relative Error threshold) to select plausible networks for robust interdiction analysis.
• Explicit quantification of tradeoffs between interdiction budget, performance, and robustness over ensembles representing network uncertainty.

Datasets

• Narcologic Network — 156 nodes, 1006 edges — public research baseline network for Central American narcotics trafficking [17]
• CCDB Dataset — 22 administrative regions with aggregated trafficking volumes — public temporal dataset for Central America counter-narcotics

Baselines vs proposed

• Optimal scenario-specific interdiction: residual capacity decreases rapidly but solutions vary significantly between networks.
• Robust interdiction (single solution for all scenarios): achieves near-optimal flow reduction across all 230 data-consistent networks vs. scenario-specific optimum varying up to 10-20%.
• Random node interdiction baseline (implied low performance): robust strategies substantially outperform random or uniform node removal under same budgets.

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2606.14611.

Fig 4: (Top) Distribution of Average Relative Error (ARE) between reconstructed network flows re-

Fig 5: ILP formulations for the FLOWINTERDICTION and ROBUST-FLOWINTERDICTION problems.

Fig 3: Linear programming (LP) for approximating edge flows from regional flows.

Fig 7: Distribution of interdicted nodes over the filtered ensemble of networks. (Left) The robust

Fig 6: Residual Capacity across interdiction

Fig 6 (page 9).

Fig 8: Jaccard Similarity for the optimal set of interdicted nodes.

Fig 9: Feature Distribution of interdicted nodes. Comparison of features of all nodes with the mean

Limitations

• The datasets are limited geographically and temporally, representing mainly Central America; generality to other regions is untested.
• Node interdiction costs are assumed uniform due to lack of ground truth, potentially masking cost-benefit tradeoffs.
• No explicit adversarial adaptation or strategic countermeasures modeled, assuming fixed maximal flow adversaries.
• Uncertainty modeled only on network topology and capacities; dynamic temporal changes or flow disruptions not captured.
• Scalability of ILP formulation to larger networks or continuous interdiction budgets not assessed.
• Robustness defined as worst-case over finite sampled ensemble; true uncertainty may be broader or multi-modal.

Open questions / follow-ons

• How to incorporate dynamic or temporal changes in networks and flows into robust interdiction frameworks?
• Can heterogeneous and realistic interdiction costs be incorporated to improve operational relevance?
• What are scalable solution methods (heuristics or decompositions) for robust interdiction in larger, more complex networks?
• How do strategic adaptive adversaries who change flow routes in response to interdiction affect solution robustness?

Why it matters for bot defense

For bot-defense and CAPTCHA practitioners, this paper illustrates a rigorous robust optimization framework under severe uncertainty and sparse observational data that parallels challenges in detecting adversarial network behaviors under incomplete knowledge. The network flow interdiction analogy highlights the importance of considering multiple plausible adversarial scenarios rather than optimizing for a single known profile, a principle applicable to robust bot detection models. The data-consistency filtering approach provides a quantitative way to select realistic adversarial scenarios for evaluation. Furthermore, the tradeoffs between solution optimality and robustness under budget constraints mirror resource-constrained defenses in bot mitigation. Practitioners can adapt such ensemble-driven, robust optimization formulations for scenarios like adversarial session routing, proxy networks, or evolving botnets under detection uncertainty. However, the ILP formulations and computation may be intractable for real-time or large-scale CAPTCHA applications requiring approximations. Overall, the paper advocates for principled scenario-based robust strategies rather than single point optimizations in security-critical, data-limited contexts.

Cite

@article{arxiv2606_14611,
  title={ Robust Network Flow Interdiction Problems with Applications to Counter-Narcotics },
  author={ Diksha Gupta and Madhav Marathe and Anil Vullikanti },
  journal={arXiv preprint arXiv:2606.14611},
  year={ 2026 },
  url={https://arxiv.org/abs/2606.14611}
}

Read the full paper

• arXiv:2606.14611 (abstract)
• arXiv:2606.14611 (PDF)