# What is the probability of a virus spreading through a network given a virus source node?

Model: Consider an infinite undirected connected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$. At time $t=0$, a given virus node $s\in\mathcal{V}$ starts infecting the network $\mathcal{G}$. Specifically, for each edge $(u,v)\in\mathcal{E}$, if either $u$ or $v$ becomes infected, then the other uninfected node on the edge $(u,v)$ will be infected after a random time following an exponential distribution with rate $\lambda$. Assume the spreading times for each edge are independent and identically distributed.

Question: Now given a connected subgraph $G\subset\mathcal{G}$ ($s\in G$ ), what is the probability that all the nodes in $G$ are infected at time $t>0$?

I tried to find a mathematical model to track such an infection process on different kinds of networks (trees, grids, regular networks, etc.). However, after checking the classical epidemic models (SIS, SIR, etc.), I found these models often use the mean field approximation to find the percentages of population in different states (Suspicious, Infected, etc.) without considering the network structures. Thus I think they might not be useful in modeling the infection process described above.

Any insights or references to papers/books would be helpful and greatly appreciated.

• there seem to be many models, one involves random walkers on a graph that when "coincide" get infected. but not what you want? – vzn May 7 '14 at 20:03
• Have you tried looking at Galton–Watson processes? They're not exactly the same, but I'd hazard a guess that at least for some types of graphs they behave the same up to lower order terms when the size of the graph is taken as the asymptotic variable. – mobius dumpling May 7 '14 at 20:33
• @vzn Random walks can be helpful in calculating the probability of a certain node being infected. But when it comes to the probability of a given graph being infected, I think random walks would become very complicated since the random walks on a graph are highly correlated. Still, thanks for your comment. Could you provide any reference papers on the epidemic models involving random walkers you mentioned? – Erdos Yi May 8 '14 at 3:04
• @mobiusdumpling Insightful comment. I think Galton-Watson processes could be used in modeling the infection process in tree graphs. But for the graphs with cycles (such as grids), I think branching processes might not be able to capture the infection process since a node in the graph might be infected by different parent nodes from different paths. – Erdos Yi May 8 '14 at 3:06
• afaik for most network models the probability of connected nodes (or sets of nodes) becoming infected is a function of time and as $t \rightarrow \infty$, probability of infection $\rightarrow 1$... right? otherwise probability of infection over time is roughly related with shortest path to original infection node....? – vzn May 8 '14 at 15:17

there are many "spread" models, what you request does seem to have been studied. eg this paper builds a framework to analyze the difference & distinguish between random virus spreading and network- (graph-) based spreading.

Given that you are assuming an infinite graph, I am not sure if it is possible at all to find the probability of having all the nodes infected. I would say for any $t > 0$, the probability is (perhaps) $0$.
It will be a different problem if you consider finite graphs (e.g., you are looking for a probability of having all the nodes at distance $d$ from the source infected).
In case you have not looked up the keywords "diffusion", "SIR models", in the context of social networks, I suggest you try them first. I once did a small project on the topic of news spreading in social networks and those were the topics I had to study for it. For a finite graph, the ratio of the nodes being infected follows an $S$-shape pattern, i.e., slow first, then faster, then slows down.