Carnegie Mellon University
In this paper, the authors analytically studied virus-spreading (specifically the SIS model) on arbitrary, time-varying graphs. Given a set of T alternating graphs, modeling e.g. the day/night pattern of human behavior, they ask: what is the epidemic threshold? And what are the best-k nodes to immunize to defend against an epidemic? Their main contributions are: they show how to formulate the problem, namely by approximating it with a Non-Linear Dynamical System (NLDS). They give the first closed-formula for the threshold, involving the first eigenvalue of the system-matrix. They use the insight from their threshold to develop and evaluate several immunization policies on real data like MIT reality mining graphs.