Research in Scientific Computing in Undergraduate Education

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 k \geq 1 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.

When k \geq 2 this problem is known to be computationally hard (it is NP-complete) so approximate algorithms are required for the solution.

References & Readings

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: