5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ THere's a lot of work on "influence maximization in social networks" that uses tools of this kind. But they don't have a notion of immunity. $\endgroup$ – Suresh Venkat Jun 1 '13 at 0:31
  • 3
    $\begingroup$ Infectious Random Walks. $\endgroup$ – Pratik Deoghare Jun 1 '13 at 6:03
2
$\begingroup$

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
$\endgroup$
1
$\begingroup$

This looks like a simplified version of the SIR model applied to networks, as used to represent contagions. You can have a look at the Wikipedia page on Epidemic models, and also to this MSc thesis: The Dynamics of Social Contagion (Barash 2011). It gives a nice overview of this model and its variants.

Considering the SIR model has been largely studied, you should find relevant information for your specific model, by starting digging from this.

$\endgroup$
  • $\begingroup$ (Barash only seems to consider models where the contagion becomes more likely as the neighbours are infected, so this doesn't seem to fit.) The SIR model on graphs seems to be exactly what the OP is asking about; for instance arxiv.org/pdf/1007.3958 seems highly relevant. Forest fire models may also be relevant: orca.cardiff.ac.uk/1641/1/… $\endgroup$ – András Salamon Jun 1 '13 at 14:59
  • $\begingroup$ Yes, I actually meant to highlight the review part of the thesis (section 1.4) and forgot to do so. Thanks for noticing. $\endgroup$ – Vincent Labatut Jun 1 '13 at 15:02
0
$\begingroup$

I'm fairly sure I got it, though I dont have proofs right now. I'm 99% sure this works for trees, and I'm pretty sure it works for more general graphs. The code below is in psudo-haskell

For trees:

GetProbability (G,N): //G = a graph, N = a node
if N.infected == True
    return 1
if N.neigbhors.size == 0
    return 0
NeighborsInfectedP = map (getP(G with N removed) ) N.neighbors
return (1 - N.q) * (1 - (AllAttacksFail NeighborInfectedP)

AllattacksFail listOfProbs = foldl1 (*) [map (\x -> 1- x)] listOfProbs

To make it work for more general graphs, remove the other neighbors of N when calling getP recursivly on any one neighbor. I'm less sure about the general solution.

$\endgroup$
-1
$\begingroup$

your question indicates you're just starting out on this topic. there is some highly specialized research at this point on this subject of mathematical and computer models for virus spreading. virus spreading behavior has seen to have widespread similarities in different/diverse milieus eg computer viruses, human viruses, animal viruses. havent seen a good scientific survey paper. however here are two refs written by leading computer scientist experts/specialists/discoverers in natural/physical applications of graph theory. full disclosure, they are popular science type books, but they should be sufficient for your query to find further research leads.

$\endgroup$

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.