The Azimuth Project
Invasion fitness in moment-closure treatments (part 3) (changes)

Showing changes from revision #6 to #7: Added | Removed | Changed

This page is has a been superceded by my article in progress, written by Blake Stacey. To discuss as it is being written, go to the Azimuth Forum.

Continued from Part 2.

Example 2: Epidemic in an Adaptive Network

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:

SIR model

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 SS plus an II becomes an II plus an II. If the disease runs its course in an individual, they gain the status of RR 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 RR individuals transition back to SS, or the immunity might only be partial, so that we have transitions from RR directly back to II. 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 SS and II in the population at any time. Therefore, the probability that an organism chosen at random has status SS and the probability that an organism chosen at random has status II sum to 1:

p S+p I=1. p_S + p_I = 1.

Following Gross et al. (2006) and Do et al. (2009), we choose to normalize our pairwise densities in the following way:

p SS+p SI+p II=k, p_{S S} + p_{S I} + p_{I I} = \langle k \rangle,

where k\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 rr, 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 Ip_I:

ddtp I=τp SIrp I. \frac{d}{d t} p_I = \tau p_{S I} - r p_{I}.

In the original SIR example, where everyone was in contact with everyone else, we could say p SIkp Sp Ip_{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 Sp Ip_S p_I stays the same when we move links around. So, to write an equation for how p Ip_I changes, we need to write down how the density of SIS I pairs will change, but in order to do that, we have to include the rewiring effect.

Let’s introduce a third parameter, ww, to indicate how much rewiring is going on. The density of SSS 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.

ddtp SS=(r+w)p SIτp SSI. \frac{d}{d t} p_{S S} = (r + w) p_{S I} - \tau p_{S S I}.
ddtp II=τ(p SI+p ISI)2rp II. \frac{d}{d t} p_{I I} = \tau(p_{S I} + p_{I S I}) - 2r p_{I I}.

We now enforce a pair approximation, by writing three-way probabilities in terms of lower-order ones:

p ISI=qkp SI 2p S. p_{I S I} = \frac{\langle q \rangle}{\langle k \rangle} \cdot \frac{p_{S I}^2}{p_S}.

The “mean excess degree” q\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 q=k\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,

ddtp I=τp SIrp I, \frac{d}{d t} p_I = \tau p_{S I} - r p_I,

and then the rules we deduced using pair approximation:

ddtp SS=(r+w)p SI2τp SIp SSp S, \frac{d}{d t} p_{S S} = (r + w)p_{S I} - 2 \tau p_{S I} \frac{p_{S S}}{p_S},


ddtp II=τp SI(1+p SIp S)2rp II. \frac{d}{d t} p_{I I} = \tau p_{S I} \left(1 + \frac{p_{S I}}{p_S}\right) - 2r p_{I I}.

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.


  • H. Matsuda, N. Ogita, A. Sasaki, and K. Sato (1992), “Statistical mechanics of population”, Progress of Theoretical Physics 88, 6: 1035–49 (web).
  • U. Dieckmann, R. Law, and J. A. J. Metz, eds., The Geometry of Ecological Interactions: Simplifying Spatial Complexity. Cambridge University Press, 2000.
  • T. Gross, C. J. Dommar D’Lima and B. Blasius (2006), “Epidemic dynamics on an adaptive network”, Physical Review Letters 96, 20: 208701 (web). arXiv:q-bio/0512037.
  • A.-L. Do and T. Gross (2009), “Contact processes and moment closure on adaptive networks”, in T. Gross and H. Sayama, eds., Adaptive Networks: Theory, Models and Applications. Springer.
  • B. Allen (2010), Studies in the Mathematics of Evolution and Biodiversity. PhD thesis, Boston University (web).
  • J. A. Damore and J. Gore (2011), “Understanding microbial cooperation”. Journal of Theoretical Biology DOI:10.1016/j.jtbi.2011.03.008 (pdf).
  • B. Simon, J. A. Fletcher and M. Doebeli (2011), “Hamilton’s rule in multi-level selection models” Journal of Theoretical Biology. PMID:21820447.
    • B. C. Stacey, A. Gros and Y. Bar-Yam (2014), “Eco-Evolutionary Feedback in Host–Pathogen Spatial Dynamics”, arXiv:1110.3845 [nlin.AO].
  • J. D. Van Dyken, T. A. Linksvayer and M. J. Wade (2011), “Kin Selection–Mutation Balance: A Model for the Origin, Maintenance, and Consequences of Social Cheating” The American Naturalist 177, 3: 288–300. JSTOR:10.1086/658365 (pdf).

category: blog