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.

  • $\begingroup$ there seem to be many models, one involves random walkers on a graph that when "coincide" get infected. but not what you want? $\endgroup$ – vzn May 7 '14 at 20:03
  • $\begingroup$ 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. $\endgroup$ – mobius dumpling May 7 '14 at 20:33
  • $\begingroup$ @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? $\endgroup$ – Erdos Yi May 8 '14 at 3:04
  • $\begingroup$ @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. $\endgroup$ – Erdos Yi May 8 '14 at 3:06
  • $\begingroup$ 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....? $\endgroup$ – 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.

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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.