This page has been superceded by my thesis.
Continued from Part 2.
We can juice things up a little by considering another example, one which is topical for these jittery times. Let’s look at the spread of an epidemic. There’s a classic genre of models for this, which we can call after a prototypical representative, the Susceptible–Infected–Recovered or SIR model. In the SIR model, we imagine a population of individuals through which a disease can spread. Each individual is either Susceptible to the disease, Infected with it or Recovered from it. The Petri net for an SIR model would look like this:
We can read off the possible transitions from the diagram. Contact with an Infected individual can turn a Susceptible one into an Infected, so an $S$ plus an $I$ becomes an $I$ plus an $I$. If the disease runs its course in an individual, they gain the status of $R$ and are thereafter immune to further infection. (Perfect immunity is, mathematically, the same as death, but we’ll be optimistic with our labels today.) We can complicate the model in many ways, for example by making the immune response imperfect, so that individuals who have recovered can be re-infected later. This could happen by the immunity fading over time, so that $R$ individuals transition back to $S$, or the immunity might only be partial, so that we have transitions from $R$ directly back to $I$. We can also add population structure: interesting things happen when the individuals are not all in direct contact with one another. This complication is obviously something we’ll have to address if we want to do epidemiology with real-world diseases! Speaking from a more mathematical perspective, we find neat phase-transition effects when we put these epidemic models on a lattice; see Stacey et al. (2011) and references therein.
The complicating factor we’ll consider today is the following: the spread of a disease through a social network can itself change the way people contact each other. This makes epidemiology a candidate subject for the study of adaptive networks: graph-structured systems in which the states associated with the vertices and the topology of the edges can change on the same timescales, feeding back on one another.
To the SIR problem we described earlier, we add two extra wrinkles: first, the individuals are arranged in a network, and infection spreads only along the links within that network. Second, if a susceptible individual is in contact with an infected one, that link can be broken, and a new link established to another susceptible individual, which we pick at random from the pool of eligible susceptibles (that is, those who aren’t already neighbours — we are disallowing multiple links). This rewiring rule makes this scenario an adaptive-network problem.
For the moment, let’s say that once they’re infected, these organisms don’t recover. We have only $S$ and $I$ in the population at any time. Therefore, the probability that an organism chosen at random has status $S$ and the probability that an organism chosen at random has status $I$ sum to 1:
Following Gross et al. (2006) and Do et al. (2009), we choose to normalize our pairwise densities in the following way:
where $\langle k \rangle$ is the average degree of the nodes in the network.
The number of infected individuals decreases as organisms recover from the disease, while it increases as the contagion spreads over links from those already infected. We say how quickly recovery happens using the parameter $r$, and we encode the ease with which the disease travels along network links with the transmissibility $\tau$. With these definitions, we can write the following rate equation for the density of infected individuals, $p_I$:
In the original SIR example, where everyone was in contact with everyone else, we could say $p_{S I} \approx \langle k \rangle p_S p_I$. But we ought to be wary of using this approximation here, for two reasons. First, any time we have a system which has a chance of developing heterogeneity, of forming lumps in one region which don’t directly affect lumps in another, then averaging over the whole system becomes a risky business. Second, more specifically, this approximation can’t capture rewiring. Links are breaking and re-forming all the time in our model, but the product $p_S p_I$ stays the same when we move links around. So, to write an equation for how $p_I$ changes, we need to write down how the density of $S I$ pairs will change, but in order to do that, we have to include the rewiring effect.
Let’s introduce a third parameter, $w$, to indicate how much rewiring is going on. The density of $S S$ pairs will go down as the disease spreads to them from infected nodes, but it will go up as nodes recover and as susceptible nodes rewire their links.
We now enforce a pair approximation, by writing three-way probabilities in terms of lower-order ones:
The “mean excess degree” $\langle q \rangle$ is the number of additional links we expect to find after we follow a random link. It turns out (Do 2009) that $\langle q \rangle = \langle k \rangle$ is a reasonable approximation.
Our dynamical system is defined by three equations. First, we have the rule we wrote before,
and then the rules we deduced using pair approximation:
and
Having written these equations, we can compare the behaviour of the dynamical system they define to that of a simulation of the original model. They actually agree pretty well (Gross et al. 2006, Do et al. 2009).
Note that we have made an important simplifying assumption, not in the analytical treatment of our model but in the original definition of it: we chose a rewiring rule which lets nodes form new links to S-type nodes anywhere else in the system. That is, the rewiring rule lacks any notion of proximity. Depending on the phenomenon we’re trying to model, it might be reasonable to allow rewiring only to neighbours of a node’s current neighbours, for example. This could be the case if information about available opportunities for building new connections had to spread through existing links. Or, if the nodes’ spatial positions are significant, perhaps links which span longer geographical distances should be disfavoured. These are the sorts of complications which can make pair approximations inapplicable.
The study of dynamical processes on and of graph structures brings together the subjects of “network theory”, as the term has been used around Azimuth, and “complex networks”, to invoke a term which has been trending elsewhere.
Continued in Part 4.