Class13

We study natural models for the spread of mutating worms or viruses on computer networks. The models can also be used to describe the propagation of faults. We obtain necessary and sufficient conditions for fast recovery from the epidemic on arbitrary network topologies. While these don’t match in general, they do match on several topologies of interest, implying the presence of a threshold for the infection or cure rate which separates fast and slow recovery. This result is analogous to, and generalizes, known results on phase transitions for epidemics on infinite lattices. Next, we use these techniques to study strategies for combating epidemics. In particular, we consider patching schemes which could divide their effort unevenly among the nodes. We show that allocating effort in proportion to node degree is close to optimal in expander graphs, which are good models of many real-world networks.

Ayalvadi Ganesh Ganesh graduated from the Indian Institute of Technology, Madras, in 1988. He received his MS and PhD in Electrical Engineering from Cornell University in 1991 and 1995 respectively. He has been with Microsoft Research, Cambridge, since March 1999.

Host: Prof. Alanyali
Student Host: James Kang