New edge deletion algorithm cuts epidemic spread in SIS network models

In a new paper, researchers Hoang and Duong tackle a classic problem: how to minimize the spread of an epidemic in a network by removing connections. They extend an existing edge deletion algorithm to the discrete SIS (Susceptible-Infected-Susceptible) model, where individuals can be infected and recover multiple times. The key innovation is using a mean-field approximation to linearize the complex network dynamics into a deterministic SIS model. They analytically prove that the total number of infections over time is upper-bounded by a super-modular function. This mathematical property ensures that the greedy edge deletion algorithm is efficient—each step of removing the edge that gives the greatest reduction in the bound leads to near-optimal results.

To validate the theory, the authors ran simulations on synthetic Erdos-Renyi random networks and on real contact network data from the BBC Pandemic Haslemere app. In both cases, the algorithm successfully reduced cumulative infections, and the system converged to a stable, disease-free equilibrium. The experiments confirm that the super-modular bound is tight enough for practical use. For tech professionals, this work provides a rigorous, mathematically grounded tool for network intervention design—relevant for cybersecurity, social network moderation, or even supply chain resilience. The approach moves beyond heuristic manual edge cutting to a provable optimization framework.