<p>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 &gt; 0 $, the probability is (perhaps) $0$. </p>

<p>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).</p>

<p>For infinite graphs, you could start with simpler alternatives, e.g., use Markov chains to model the spreading process and find the rate at which the nodes are infected, e.g., avg. number of nodes per time unit.</p>

<p>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.</p>

<p>I hope it helped.</p>

CC BY-SA 3.0
2014-05-09T15:42:10.323Z
Also this example might be interesting (different model since nodes can or cannot be affected) http://www.stanford.edu/~jacksonm/nettipping.pdf
Ehsan
CC BY-SA 3.0
2014-05-09T15:40:26.830Z
2014-05-09T15:40:26.830Z
Ehsan
<p>there are many "spread" models, what you request does seem to have been studied. eg this paper builds a framework to analyze the difference &amp; distinguish between random virus spreading and network- (graph-) based spreading.</p>

<ul>
<li><a href="http://users.ece.utexas.edu/~cmcaram/pubs/InfectionVsSpreading.pdf" rel="nofollow">Network Forensics: Random Infection vs Spreading Epidemic</a> Milling, Caramanis, Mannor, Shakkottai</li>
</ul>

<blockquote>
  <p>Computer (and human) networks have long had to contend
  with spreading viruses. Effectively controlling or curbing an
  outbreak requires understanding the dynamics of the spread.
  A virus that spreads by taking advantage of physical links
  or user-acquaintance links on a social network can grow explosively
  if it spreads beyond a critical radius. On the other
  hand, random infections (that do not take advantage of network
  structure) have very different propagation characteristics.
  If too many machines (or humans) are infected, network
  structure becomes essentially irrelevant, and the different
  spreading modes appear identical. When can we distinguish
  between mechanics of infection? Further, how can this be
  done efficiently? This paper studies these two questions.
  We provide sufficient conditions for different graph topologies,
  for when it is possible to distinguish between a random
  model of infection and a spreading epidemic model, with
  probability of misclassification going to zero. We further
  provide efficient algorithms that are guaranteed to work in
  different regimes.</p>
</blockquote>

CC BY-SA 3.0
2014-05-08T15:15:38.910Z
EY asked in comment for another model of virus spread via random walks on graph. for that see eg [A random walk model for infection on graphs:
spread of epidemics & rumours with mobile agents](http://www.iis.ee.ic.ac.uk/~m.draief/file/Home_files/DESD10.pdf) Draief/Ganesh
vzn
CC BY-SA 3.0
2014-05-07T20:13:05.113Z
2014-05-07T20:13:05.113Z
vzn
<p><strong>Model</strong>: 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. </p>

<p><strong>Question</strong>: 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&gt;0$? </p>

<p>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 <a href="http://en.wikipedia.org/wiki/Epidemic_model">epidemic models</a> (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. </p>

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

CC BY-SA 3.0
2014-05-07T20:03:55.947Z
there seem to be many models, one involves random walkers on a graph that when "coincide" get infected. but not what you want?
vzn
CC BY-SA 3.0
2014-05-07T20:33:52.040Z
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.
greg
CC BY-SA 3.0
2014-05-08T03:04:06.333Z
@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
CC BY-SA 3.0
2014-05-08T03:06:16.160Z
@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
CC BY-SA 3.0
2014-05-08T15:17:10.557Z
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
<graph-theory><pr.probability><stochastic-process>
What is the probability of a virus spreading through a network given a virus source node?
Erdos Yi
# What is the probability of a virus spreading through a network given a virus source node?

(Asked by: username_0 on 2014-05-07)

**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](http://en.wikipedia.org/wiki/Epidemic_model) (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.

**Tags:** graph-theory, pr.probability, stochastic-process
> **Comments:**
> **username_1**: there seem to be many models, one involves random walkers on a graph that when "coincide" get infected. but not what you want?  
> **username_2**: 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.  
> **username_0**: @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?  
> **username_0**: @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.  
> **username_1**: 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....?  

---

## 2 answers

### Answer by username_3 on 2014-05-09. Score: 1

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).

For infinite graphs, you could start with simpler alternatives, e.g., use Markov chains to model the spreading process and find the rate at which the nodes are infected, e.g., avg. number of nodes per time unit.

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.

I hope it helped.

> **Comments:**
> **username_3**: Also this example might be interesting (different model since nodes can or cannot be affected) http://www.stanford.edu/~jacksonm/nettipping.pdf  

---

### Answer by username_1 on 2014-05-07. Score: 1

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.

* [Network Forensics: Random Infection vs Spreading Epidemic](http://users.ece.utexas.edu/~cmcaram/pubs/InfectionVsSpreading.pdf) Milling, Caramanis, Mannor, Shakkottai

> Computer (and human) networks have long had to contend
> with spreading viruses. Effectively controlling or curbing an
> outbreak requires understanding the dynamics of the spread.
> A virus that spreads by taking advantage of physical links
> or user-acquaintance links on a social network can grow explosively
> if it spreads beyond a critical radius. On the other
> hand, random infections (that do not take advantage of network
> structure) have very different propagation characteristics.
> If too many machines (or humans) are infected, network
> structure becomes essentially irrelevant, and the different
> spreading modes appear identical. When can we distinguish
> between mechanics of infection? Further, how can this be
> done efficiently? This paper studies these two questions.
> We provide sufficient conditions for different graph topologies,
> for when it is possible to distinguish between a random
> model of infection and a spreading epidemic model, with
> probability of misclassification going to zero. We further
> provide efficient algorithms that are guaranteed to work in
> different regimes.

> **Comments:**
> **username_1**: EY asked in comment for another model of virus spread via random walks on graph. for that see eg [A random walk model for infection on graphs: spread of epidemics & rumours with mobile agents](http://www.iis.ee.ic.ac.uk/~m.draief/file/Home_files/DESD10.pdf) Draief/Ganesh  

---

