Optimal link removal for epidemic mitigation: a two-way partitioning approach

Area of Science:

• Epidemiology and Network Science
• Computational Biology and Public Health

Background:

• Disease transmission dynamics are significantly influenced by the underlying contact network structure.
• Effective epidemic control strategies necessitate efficient resource allocation, particularly when resources for interventions like quarantining are limited.

Purpose of the Study:

• To develop and validate an algorithm for optimal link removal in contact networks to minimize infection spread.
• To maximize the number of uninfected individuals by strategically quarantining specific network connections under resource constraints.

Main Methods:

• The problem is formulated as a non-convex quadratically constrained quadratic program (QCQP).
• A novel link removal algorithm is derived from the QCQP formulation.
• The algorithm's performance is evaluated on various network models, including random graphs and a real-world injection drug use network.

Main Results:

• The QCQP-based algorithm demonstrates near-optimal performance in minimizing disease spread.
• The proposed algorithm significantly outperforms intuitive methods like removing links based on edge centrality.
• Effective identification and removal of critical network links are key to maximizing population protection.

Conclusions:

• Strategic link removal, guided by a QCQP framework, is a highly effective method for epidemic control.
• This approach offers a computationally efficient and high-performing solution for resource-constrained public health interventions.
• The findings have implications for designing targeted interventions in diverse epidemiological contexts.