Epidemic Spreading Algorithm

One of the standard models of epidemic spreading is the SIS model [13], in which the nodes can either be infected or healthy. A healthy node can be infected by neighboring infected node with a certain constant probability per unit of time. With some other constant probability it can recover. We use that approach except that we assume that a node can never recover.

The number of epidemics is equal to the number of seeds. Initially the only nodes that are infected are the seeds. Once a node is infected by some epidemic it cannot be infected by another, thus the epidemics compete over the nodes they can infect. In each iteration of the algorithm, one node is infected. The probability of infection by a given epidemic is linearly proportional to the number of neighbors that are infected by that epidemic.



Ali Salehi 2005-04-29