Abstract: Epidemic processes are widely used to design efficient distributed algorithms with applications in  various research fields. In this paper, we consider a dynamic epidemic process in a certain (idealistic urban environment modeled by a complete graph. The epidemic is spread among $n$ agents, which move from one node to another according to a power law distribution that describes the so called  attractiveness of the corresponding locations in the urban environment. If two agents meet at some node, then a possible infection may be transmitted from one agent to the other.

We analyze two different scenarios. In the first case we assume that the attractiveness of the nodes follows a power law distribution with some exponent less than $3$, as observed in real world examples. Then, we show that even if each agent may spread the disease for $f(n)$ time steps,  where $f(n) =\smallO(\log n)$ is a (slowly) growing function, at least a small (but still polynomial)  number of agents remains uninfected and the epidemic is stopped after a logarithmic number of  rounds. In the second scenario we assume that the power law exponent increases to some large  constant, which can be seen as an implication of certain countermeasures against the spreading  process.
Then, we show that if each agent is allowed to spread the disease for a constant number of time  steps, the epidemic will only affect a polylogarithmic number of agents and the disease is stopped  after $(\log \log n)^{\bigO(1)}$ steps. Our results explain possible courses of a disease, and point out  why cost-efficient countermeasures may reduce the number of total infections from a high percentage of the population to a negligible fraction.

Guest: Robert Elsaesser
Host: Zvi Lotker

Podcast: Play in new window | Download