Imagine trying to stop a disease from spreading through a city by closing certain roads. You want to cut off the infection's path — but you also don't want to paralyze the whole city. This project asks: which roads (or network connections) should you remove, and how many, to create isolated "safe zones" while keeping disruption minimal? We discovered that the best strategy depends entirely on the structure of the network — and that four distinct approaches each excel in different situations.
This project investigates optimal link-removal strategies to create safe zones in networks, limiting the spread of infections while minimizing disruption. Focusing on one-edge and two-edge-connected graphs, we develop generalizable techniques for disconnecting networks efficiently.
We extend our analysis to k-edge-connected graphs, demonstrating how increasing connectivity alters containment strategies, and introduce a tree-like model for bipartite graphs to better understand infection spread. Our findings identify four optimal link removal strategies — weak, strong, betweenness centrality (BC), and weighted betweenness centrality (BCw) — each suited to different network structures.
What is the optimal way to break a network?
The core question is deceptively simple: given a network through which an infection spreads, which edges should be removed — and in what order — to most efficiently create isolated safe zones? This question has no single answer. The optimal strategy depends on the network's connectivity structure, degree distribution, and the intensity of intervention available.
We investigate this across three graph families: one-edge-connected graphs (where a single edge removal can disconnect the network), two-edge-connected graphs (requiring at least two removals), and the generalized k-edge-connected case. We also introduce a tree-like bipartite model to capture the layered structure seen in real-world systems like hospital contact networks.
Four optimal link-removal approaches
A central finding of this work is that no single strategy dominates across all network types. Instead, four distinct approaches each represent the optimal choice under specific structural conditions:
Targets the lowest-weight or least-critical edges first. Optimal for sparse networks where removing any edge creates significant fragmentation.
Removes the highest-weight edges first. Best suited for dense networks where high-capacity links drive the majority of contagion flow.
Targets edges that lie on the most shortest paths through the network — the "bridges" of information flow. Highly effective in scale-free topologies.
Combines edge weight with betweenness centrality. Outperforms pure BC in weighted networks where both flow volume and structural position matter.
Graph-theoretic analysis and epidemic simulation
The study combines rigorous graph theory with computational epidemic simulation. For each network family, we derive analytical conditions under which each removal strategy is provably optimal — establishing a theoretical foundation before validating computationally.
Epidemic dynamics are modeled using SIS and SIR frameworks on synthetic network topologies including Barabási-Albert (scale-free) and Erdős-Rényi (random) graphs, as well as the tree-like bipartite model introduced in this work. We evaluate each strategy across a range of removal intensities, measuring both the containment achieved and the structural cost (edges removed, connectivity lost). Monte Carlo averaging over 500+ network realizations per parameter set ensures statistical robustness.
What the data showed
- No single strategy is universally optimal — the best approach is determined by the network's k-edge-connectivity and degree distribution.
- In one-edge-connected graphs, weak and BC strategies achieve maximum containment with minimum removals.
- As k increases, BCw increasingly outperforms simpler strategies, capturing the interaction between flow weight and structural position.
- The tree-like bipartite model reveals layered infection dynamics not captured by standard random graph models.
- Increasing network connectivity does not uniformly make containment harder — it shifts which strategy is optimal rather than raising the minimum cost.
- All four strategies converge in performance at very high removal intensities, suggesting diminishing returns beyond a critical threshold.
From theory to policy
The findings give decision-makers a practical test: measure a network's structural properties, then apply the provably optimal containment strategy for that topology.
Pandemic travel restrictions. In a community-structured network — dense domestic travel, sparse international links — targeting bridge routes creates containment zones up to 54× more protective than random border closures. In a hub-dominated network, severing the busiest hub connections is more effective. The framework identifies which case applies.
Hospital infection control. Hospital ward networks have exactly the community topology where bridge-targeted interventions are most effective. Restricting the specific staff or shared equipment that bridge between wards — rather than blanket protocols — reduces cross-ward transmission with minimal disruption to care.
Misinformation containment. Cross-community bridge accounts — the handful of users followed across distinct ideological groups — are the highest-leverage targets. Suspending them fragments the sharing network far more effectively than removing a larger number of accounts at random.
Power grid resilience. Pre-emptively reducing load on bridge transmission lines during peak demand can isolate regional faults before they cascade nationally — without requiring full grid separation.