At a Glance
- Studied how to stop contagion spread by cutting network links (edges).
- Proved key edge-removal problems are NP-hard and developed a novel edge-removal heuristic.
- Showed the heuristic significantly improves containment of both simple and complex contagions.
Visual highlights
The Problem
- Selecting an optimal set of edges to delete for maximum containment is NP-hard.
- For complex contagions (requiring multiple exposures), edge removal has no constant-factor approximation.
- Prior research mostly focused on node removal or ignored outbreak-specific contagion dynamics.
The Solution
- Formulated edge removal as optimization problems under various constraints (budgets, targeted closures).
- Proved new hardness results for complex contagions and identified special tractable cases.
- Developed an “edge-covering” heuristic to select edges to cut in weighted and unweighted networks.
- Simulated contagion spread on large real networks to compare the heuristic against existing methods.
Architecture Overview
- Combined graph-theoretic edge cover and cut models with contagion dynamics (independent cascade and threshold models).
- Analyzed computational complexity of edge removal versus node removal strategies.
- Used a simulation framework on real networks (e.g., contact and social graphs) to test interventions.
- Heuristic algorithm considered edge weights, directions, and outbreak source information to prioritize cuts.
Results and Impacts
- The edge-removal heuristic outperformed prior strategies, blocking more contagion spread in 12 test scenarios.
- Confirmed that while optimal solutions are intractable, a scalable heuristic achieves strong containment.
- Compared node vs. edge removal: cutting specific links often contained outbreaks more cost-effectively.
- Methods informed follow-up research and have been applied to other network intervention scenarios.
Skills and Tools Used
| Technique/Skill | Tools/Implementation |
|---|---|
| Graph algorithms and theory | NP-completeness proofs, approximation limits |
| Heuristic design | Edge-blocking algorithm (implementation) |
| Network simulation | Contagion diffusion on large graphs |
| Data analysis | Comparative evaluation on real networks |
| Interdisciplinary approach | Algorithms + epidemiology for interventions |
Cross-Project Capabilities
- Edge-cutting techniques integrate with community-based blocking by isolating cross-community links.
- Developed general methods handling both simple and complex contagions for a versatile intervention toolkit.
- Established large-scale simulation and evaluation practices used across other contagion projects.
Published Papers/Tools
- Blocking Simple and Complex Contagion by Edge Removal – IEEE ICDM 2013. Paper
- Released an edge-blocking heuristic code, validated on real social networks (e.g., Montgomery County network).
- Findings cited in later network science research and integrated into contagion simulation platforms.