An algorithm for calculating the probability of a disease spreading through a graph The following problem came up in my undergrad research project: You have some undirected graph. Some nodes are "sick" and some are not. The probability that a neighbour of a sick node becomes sick is (1 - q_i), where q is a number specific to the node under attack, ranging from 0 to 1. If a node succesfully resists an attack from a sick neighbor, it becomes immune and cannot get sick from any other node. What is the probability that any given node will become sick, given a graph A, some initial sick nodes, and a vector of q's characterizing the nodes?

I feel like this problem has been solved, but I'm having trouble finding sources. Any help or references to papers/books will be greatly appreciated.
Immunity seems to make your problem easier in one sense, as it means that infection can be modelled by a process that terminates after a linear number of infection attempts.  The stipulation that the probability of infection does not depend on the neighbours of a vertex also helps.  However, the model does not seem easy to analyse: the immune vertices in effect are removed from the graph, so a vertex may effectively become unreachable.
The infection, immune, and unreachable probabilities depend on the intermediate graphs created by the infection process.

It might be useful to start with cliques, paths, and cycles with a single initially infected vertex.  Cliques are trivial.  For a path with one infected endpoint the probability that the other endpoint becomes infected at some stage is the product of the probabilities of infection of all the intermediate vertices.  For a cycle, the probability depends on both paths; the longer path becomes relevant if an immune vertex appears on the shorter path.  Trees also have a single path between any two vertices, so can be handled as for the path case.

It might then be feasible to extend the analysis to $k$-connected graphs and regular grids, though this already seems quite tricky.



I am not familiar with literature that deals with this specific problem.  Here are some general comments and pointers.

Some relevant keywords are "contagion" (in the context of network models) and "percolation" (in statistical mechanics).  These models tend to focus on the behaviour of randomized processes that behave like the one you suggest.  However, different models focus on different parameters of interest, so you might have to examine several to find one that best matches the specific one you are interested in.

As an example, a lot of post-2008 work has applied contagion models to financial systems, since it has been argued that these models explain well the gridlock experienced at that time by the global financial system.

The Ising model is one of the simplest and earliest models that involve interacting parties in a graph, and has an extensive literature.

From a purely TCS perspective, computing the partition function of spin systems like the Ising model is equivalent to counting the solutions of a constraint satisfaction problem.  The mixing time is also often of interest.


Andrei Bulatov and Martin Grohe, The complexity of partition functions, TCS 348, 2005, 148–186.  doi:10.1016/j.tcs.2005.09.011 (preprint)
Martin Dyer, Leslie Ann Goldberg and Mark Jerrum, Matrix norms and rapid mixing for spin systems, Annals of Applied Probability, 19, 2009, 71–107.
doi:10.1214/08-AAP532