Rumour/Gossip theory problem to simulate fire propagation.

Question

I have a set of planar graphs I am using to model a landscape. I am trying to model fire propagation. So if say fire starts at node A, there is a chance that fire can propagate to all of A's adjacent nodes.

Currently I am trying to find a way to model fire propagation as a rumour/gossip model. So if fire starts at A, there is a chance that fire might propagate to say B, or C, which are adjacent to A. And then from B or C, fire can propagate to adjacent nodes as well.

It sounds like a model for infectious diseases but so far I have found very simplistic study on this.

Does anyone know or can give me directions where I can go to study more on this?

Answer 1

It sounds a bit like a Markov Chain model. Looking that up will help you understand the idea of transition matrices.

BUT using a Markov Chain approach will not adequately model your problem. In particular, a Markov Chain imagines the fire moving completely away from one of the nodes to a single other. That means that your transition matrix will not have some of the properties of a Markov Chain matrix.

I don't think that will be a problem. You will, however, have to think carefully about the probabilities of transfer when a node is surrounded by fire as opposed to when it just has one neighbour on fire.

One problem you will have is that the probabilities will become greater than 1 - you will have to check for entries greater than 1 and reduce to 1. That step makes some of the analysis trickier.

Having said that, expected time to reach a particular node etc should all work if you can calculated modified $M, M^2, M^3$ etc.

Answer 2

I'm going to show you through an example how you could start to model this kind of situation using Markov Chains.

Consider first this map:

There are four possible starting states:

1) Fire in A
2) Fire in B
3) Fire in C
4) Fire in D

Suppose the fire can only spread from one area to another. You will need to decide on how to model the probabilities. Does the length of common border change the likelihood of transfer?

Suppose we are in state 1 (Fire in A). Let's say that the probability of fire moving to B is $0.1$, which gives us a new possible state:

6) Fire in both A and B

Suppose we are in state 2 (Fire in B). There are three different events, which I am going to assume are independent.

Fire moves to A (probability $0.1$). Note that I'm assuming that the transfer can occur equally in both directions, but this might not be true - think prevailing winds etc.

Fire moves to C (probability $0.08$ because border length is shorter).

Fire moves to D (probability $0.7$).

I'm going to assume that these are independent, because it makes the following calculations easier.

The fire could move from B to A but not from B to either of the others. Probability $0.1 \times 0.92 \times 0.93 = 0.08556$

The fire could move from B to C but not from B to either of the others. Probability $0.9 \times 0.08 \times 0.93 = 0.06696$

The fire could move from B to D but not from B to either of the others. Probability $0.9 \times 0.92 \times 0.07 = 0.05796$

The fire could move from B to both A and C but not from B to D. Probability $0.1 \times 0.08 \times 0.93 = 0.00744$

The fire could move from B to both A and D but not from B to C. Probability $0.1 \times 0.92 \times 0.07 = 0.00644$

The fire could move from B to both C and D but not from B to A. Probability $0.9 \times 0.08 \times 0.07 = 0.00504$

The fire could move from B to all three other areas. Probability $0.1 \times 0.08 \times 0.07 = 0.00056$

These give probabilities of moving from state 2 to the following states:

6) Fire in both A and B (already defined)
7) Fire in both B and C
8) Fire in both B and D
9) Fire in A, B and C
10) Fire in B, C and D
11) Fire in A, B and D
12) Fire in A, B, C and D

The maximum possible number of distinct states is $2^n$, where $n$ is the number of nodes. In our case one more is possible but not yet defined:

13) Fire in both C and D

The following states are not possible in this model because fire can not jump over gaps (although they might if two fires were started at the same time):

14) Fire in both A and C
15) Fire in both A and D

This state is not of any use to us at the moment, but it might be useful if you were modelling the start of the fires - so lightning strikes etc:

16) No fires at all

Establishing all possible states may become prohibitively difficult, but this approach will yield a perfectly good Markov Chain.