Source-linked AI summary
Target-Aware Network Dismantling with Limited Budgets
Jiaqi Song, Fei Jing, Wenjie Huang, Xingqin Qi, Qingpeng Zhang
TL;DR
Limited resources make it difficult to isolate known infected people and all their contacts, motivating a strategy for protecting the network from localized risks. The paper formulates target-aware network dismantling and develops RAIL to select interventions as the residual network changes. It finds that the more effective removal strategy depends on budget and setting, and reports that RAIL outperforms comparison methods across diverse networks while suppressing outbreak spread.
Problem
Limited public health capacity can make exhaustive isolation of identified infected or exposed people and their contacts infeasible, raising the question of how to allocate interventions to protect the network from known localized risks.
Source: §1 · pp. 1–2Method
Results
RAIL outperforms classical dismantling, neighbor-targeting, and adapted learning baselines across diverse real and synthetic networks, including under incomplete or noisy knowledge of infected nodes, and suppresses spread in SIR simulations and global-airport outbreak trajectories.
Source: §1 · p. 3Takeaways & Limitations
The more effective strategy can shift with intervention budget, network topology, and infected-node locations, supporting adaptive rather than static targeting within the studied settings.
Source: §1 · p. 2, §6 · p. 15The framework’s future development must address infected nodes that are underreported or shift dynamically, evolving networks, heterogeneous intervention costs, and preserving normal system functions.
Source: §6 · p. 15
Abstract
from arXiv · showhide
During epidemics, limited resources dictate critical decisions about whom to isolate or monitor. Conventional public health strategies intuitively prioritize known infected individuals and their immediate contacts. Here, we reveal that this contact-centric approach is fundamentally suboptimal under realistic resource constraints. By formulating this challenge as target-aware network dismantling, we uncover a counter-intuitive, budget-dependent intervention transition. Generating-function analysis demonstrates that when intervention budgets are scarce, isolating structurally central individuals, rather than the immediate neighbours of the infected, protects a vastly larger population. The conventional neighbour-targeting strategy only becomes optimal as available resources increase. Because this critical transition point shifts dynamically with the intervention budget, network topology, and spatial distribution of infections, static strategies inevitably fail. To overcome this, we develop Risk-Aware Isolation Learning (RAIL), a deep reinforcement learning framework that adaptively selects optimal interventions based on the evolving residual network. Across diverse synthetic and real-world networks, RAIL consistently maximizes population protection and suppresses outbreak spread. Ultimately, our findings challenge prevailing epidemiological intuitions, establishing a generalizable framework for adaptive interventions against localized risks in public health and other complex systems.
1 Introduction
Limited capacity makes it necessary to prioritize interventions that protect the largest part of a network from known localized risks. The paper formulates this as target-aware dismantling, finds that the better removal strategy depends on budget and setting, and introduces RAIL to adapt interventions to the changing network.
1 Introduction
- Target-aware dismantling minimizes the size of residual components connected to known infection sources, addressing localized risks under limited budgets without relying on explicit diffusion models.The introduction contrasts this aim with global fragmentation, diffusion-model-based influence minimization, and immediate-neighbor targeting.Source: §1 · pp. 1–2
- When budgets are too small to isolate all infected individuals’ immediate neighbors, removing structurally central nodes can protect more people; the relative effectiveness changes as budgets, network topology, and infection locations change.Generating-function analysis identifies budget-dependent transition points at which neighbor-based interventions can overtake structural ones.Source: §1 · p. 2
- RAIL uses a graph neural network and Double DQN to select removals sequentially from the evolving residual network and produce a universal ordering adaptable to different budgets without retraining.The framework extracts the active network still connected to infected nodes at each step.Source: §1 · pp. 2–3
- Across diverse real and synthetic networks, RAIL outperforms classical dismantling, neighbor-targeting, and adapted learning baselines, and suppresses pathogen spread in SIR simulations and global-airport outbreak trajectories.Its performance persists when knowledge of infected nodes is incomplete or noisy.Source: §1 · p. 3
2 Preliminaries
The section defines dismantling around removing uninfected nodes under a budget, then refocuses the objective on residual components connected to known infected nodes. It illustrates how the better removal strategy can change with the intervention budget.
2.1 Problem Formulation
- The formulation treats known infected nodes as sources that are not directly removed, and defines the intervention as removing a subset of uninfected nodes.The budget bounds the number of removed nodes.Source: §2.1 · p. 3
- Classical dismantling removes nodes under a budget to minimize residual connectivity, but these global objectives do not distinguish components containing infected nodes.The target-aware measure instead counts nodes in residual components containing at least one known infected node.Source: §2.1 · p. 3
2.2 Effective Removal Strategy Changes with the Intervention Budget
- With four removals, high-degree removal leaves 8 infected-connected nodes versus 3 for neighbor-based removal; with two, it leaves 12 versus 21.The examples illustrate that the relative effectiveness of the strategies depends on the intervention budget.Source: Figure 1 · p. 4, §2.2 · p. 4
- With sufficient budget, removing infected nodes’ neighbors can isolate their region; with very small budget, removing structurally important nodes can disconnect more of the network from infection sources.The section uses these contrasting outcomes to motivate generating-function analysis of when each strategy is more effective.Source: §2.2 · p. 4
3 Theoretical Analysis and Experimental Validation
Generating-function analysis predicts that high-degree removal can outperform neighbor-based removal at small budgets, while neighbor-based removal gains at large budgets. Finite-network experiments validate a transition whose location shifts with network structure and infection placement.
3.1 Theoretical Analysis
- Generating functions estimate the expected fraction of nodes in components containing infected nodes, using the probability that a branch reached by an edge contains no infection.This fraction approximates the normalized target-aware objective.Source: §3.1 · p. 5
- In heavy-tailed networks, high-degree removal has greater marginal gain at very small budgets, whereas neighbor-based removal leads at very large budgets under a mean-field approximation.Source: §3.1 · p. 6
- At intermediate budgets, Δ(R) compares the strategies’ marginal gains; its zeroes mark transitions and may occur more than once, but generally lack explicit closed forms.Both u and q_k vary with budget, and u is determined implicitly.Source: §3.1 · p. 6
3.2 Experimental Validation
- Finite-network validation compares analytical removal probabilities with direct removal of observed infected-node neighbors while varying network structure and infection placement.Source: §3.2 · p. 6, §3.1 · p. 6
- High-degree removal leads at small budgets, but neighbor-based removal gains as budgets grow; this transition persists with observed infected-node neighbors.The dominant rule can alternate in intermediate regimes.Source: Figure 2 · p. 7, §3.2 · p. 7, Figure 3 · p. 8
- The transition shifts with topology and infection placement: stronger communities and more infected clusters favor neighbor-based removal earlier, while high-degree-biased infections extend high-degree advantage.Higher infection density shifts the transition to larger budgets; spatial radius has no consistent effect.Source: §3.2 · p. 7
4 Learning State-Dependent Interventions with RAIL
RAIL makes interventions state-dependent by updating its view of the infected-connected residual network after each removal. It produces one learned ordering whose prefixes provide intervention sets for different budgets without retraining.
4 Learning State-Dependent Interventions with RAIL
- RAIL generates a universal ordering of removable uninfected nodes, with prefixes yielding intervention sets for different budgets without retraining.Source: §4 · p. 8
4.1 Dynamic State Encoding via Graph Neural Networks
- A message-passing encoder updates node and graph embeddings from the residual network connected to infected nodes, recomputed after every removal.Source: §4.1 · pp. 8–9, Figure 4 · p. 9
4.2 Action Evaluation on Evolving Topologies
- The decoder scores eligible uninfected candidates with Q-values and selects the highest-scoring node at evaluation.Source: §4.2 · p. 9
4.3 Sequential Policy Optimization and Training
- RAIL trains offline on 1,000 synthetic graphs of 30–50 nodes, regenerating the set every 5,000 iterations and using n-step Double DQN with replay.A structural regularization term stabilizes node embeddings as the residual network changes.Source: §4.3 · pp. 9–10
5 Experimental Evaluation
The evaluation benchmarks RAIL on synthetic and real networks, comparing component isolation and epidemic suppression under fully observed and uncertain infection information. RAIL achieves strong overall SIR suppression across datasets and performs well across component, simulation, and empirical-arrival evaluations.
5.1 Experimental Setting
- Evaluation spans criminal, social, information, communication, transportation, and biological networks, with standard dismantling and infection-aware baselines and varied removal budgets.The benchmarks also include synthetic networks and datasets with predefined infected nodes.Source: §5.1 · p. 10
5.2 Reducing Components Containing Infected Nodes
- With fully observed infections, RAIL is comparable to the strongest dismantling methods at 4% removal and has the smallest residual RT(VR) as budgets increase; it also outperforms baselines under uncertain infections.Source: §5.2 · p. 11, Figure 5 · p. 11, Figure 6 · p. 12
5.3.2 Spreading Suppression under Empirical Epidemic Arrival Sequences
- On empirical epidemic-arrival sequences, RAIL suppresses spread strongly at small budgets and performs better across a wider budget range, although Neighbor improves after more removals.Source: §5.3.2 · p. 12, Figure 9 · p. 14
5.3.1 Spreading Suppression in SIR Simulations
- RAIL has the smallest aggregated normalized AUC across datasets under both fully observed and uncertain infected nodes, while Neighbor has a larger aggregate AUC.Source: §5.3.1 · p. 12, Figure 8 · p. 14
6 Conclusions
The conclusions frame RAIL as an adaptive approach to isolating localized risks, with evaluations showing it minimizes infected-component impact and suppresses spread under uncertainty. They also identify unresolved transition points and real-world complexity as priorities for future work.
6 Conclusions
- Extensive evaluations confirm that RAIL minimizes the impact of infected components and suppresses spreading dynamics, even under high uncertainty.The conclusions describe RAIL as continuously adapting to changing network topology.Source: §6 · p. 15
- Exact transition points across network topologies remain a theoretical challenge, while shifting or underreported infections, evolving networks, heterogeneous costs, and preserving normal functions complicate deployment.The authors identify incorporating spatiotemporal uncertainties and intervention costs as future research directions.Source: §6 · p. 15
- Under severe resource constraints, the authors propose prioritizing structurally central individuals or key mobility hubs over exhaustive contact tracing.They describe integration with real-time epidemiological data as a way to dynamically allocate resources as outbreaks evolve.Source: §6 · p. 15
- The paper presents target-aware intervention as a generalizable framework for adaptive decisions in evolving environments, with applications spanning epidemic control, infrastructure protection, and cascading failures.The approach combines network topology, observable risk metrics, and sequential deep reinforcement learning.Source: §6 · p. 15
Data, ethics, and code statement
- The study used publicly available, de-identified, aggregated data; ethical approval was not required, and code is available at https://github.com/jkS529/RAIL.Source: Data, ethics, and code statement · p. 16