|
In this work we consider a simple virus spread model on a finite
population of $n$ agents connected by some neighborhood structure. Let $G$
be the graph on $n$ agents where an infection starts with some initial
number of infected sites. The infection spreads as follows: at each
discrete time step, an infected vertex tries to infect its neighbors with
probability $\beta \in (0,1)$ independently of others and then it dies
out. The process continues till all infected sites dies out. We focus on
obtaining proper lower bounds on the expected number of ever infected
sites. We obtain a simple lower bound when the infection starts with only
one individual using \emph{breadth-first search} algorithm. We show that
in a variety of examples this lower bound gives better approximation than
some of the known approximations through matrix-method based upper bounds.
Moreover the lower bound works for every value of $\beta \in (0,1)$. In
fact, it is shown that if the graph $G$ "locally looks like a tree" in the
sense of the local weak convergence then our lower bound is asymptotically
exact. Finally, we also provide a generalization of this bound when the
virus spread starts with more than one infected agents.
|