Theoretical Statistics and Mathematics Unit, ISI Delhi

On the Expected Total Number of Infections for Virus Spread on a Finite Network

by Antar Bandyopadhyay and Farkhondeh Sajadi

In this paper we consider a simple virus infection spread model on a finite population of $n$ agents
connected by some neighborhood structure. Given a graph $G$ on $n$ vertices, we begin with some fixed number of
initial infected vertices. 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 vertices die out.
We focus on obtaining proper lower bounds on the expected number of ever infected vertices. We obtain a simple lower bound,
using \textit{breadth-first search} algorithm and show that for a large class of graphs which can be classified as the ones which
locally ``look like'' a tree in sense of the \emph{local weak convergence} \cite{AlSt04}, this lower bound gives better approximation than
some of the known approximations through matrix-method based upper bounds \cite{DrGaMa08}.

isid/ms/2012/03 [fulltext]

Click here to return to Preprints Page