Network analysis: spread of diseases and attacks
Spread of disease or of attacks can be modeled by graphs in which nodes represent people and edges represent connections. The attacker’s (or bacteria’s) problem is: given a connected graph, in which a vertex is infected if or more of its neighbors are infected, an irreversible k-conversion set is a subset of the nodes such that if we plant a disease on the nodes of this subset, the entire graph will become infected. The object of this research project is to computationally explore the size of minimal irreversible k-conversion sets in graphs, in particular in rectangular or toroidal grids.
References & Readings
- Graph-theoretical problems arising from defending against bioterrorism and controlling the spread of fires. Fred Roberts, DIMACS (graphdiseasespreadmodels-thresholdfirefighterddr4-26-06)
- DIMACS 2002-2009 Special Focus on Computational and Mathematical Epidemiology
- Web game provides breakthrough in predicting spread of epidemics