Human contact patterns are potentially complex, as the numbers and intensity of contacts can vary considerably across a population. Furthermore, contacts are transitory events such that the identities of one's contacts change in time. To capture such heterogeneity, we introduce the *neighbour exchange* (NE) model as a simple extension of a static contact network model. In this model, an individual's number of concurrent contacts remains fixed while the composition of those contacts changes at a specified rate. The model assumes that at any given time, an individual will be in contact with an individual-specific number of neighbours with whom disease transmission is possible. Each contact is temporary, lasting a variable amount of time before coming to end, at which point the neighbour is replaced by a different individual.

Let the population of interest consist of

*n* individuals, each of which falls into one of three exclusive states: susceptible, infectious or recovered. At some time

*t*, an individual

*ego* will have

contacts with other individuals (i.e.

*alters*):

. Only undirected contact networks will be considered such that if there exists a contact (

*ego*,

*alter*) there will also be a contact (

*alter*,

*ego*). In network terminology, a directed link, denoted (

*ego*,

*alter*), is called an

*arc*. An undirected link, denoted {

*ego*,

*alter*}, is called an

*edge*. The

*degree* of a node

*ego* is the number of edges connected to the node. The term

*contact* will be used specifically to denote a directed arc in the network, where two arcs correspond to each undirected edge. The

*k-degree* of a node will be the number of concurrent contacts to/from the node .

| **Table 1**Notation for epidemic and network parameters. |

The NE model assumes that the identities of a node's neighbours will continually change, while the total number of current neighbours remains constant. This occurs through an exchange mechanism in which the destination nodes of two edges are swapped. For example, two nodes

*ego* and

*ego*′ with distinct contacts (

*ego*,

*alter*) and (

*ego*′,

*alter*′) may exchange contacts such that these are replaced with (

*ego*,

*alter*′) and (

*ego*′,

*alter*). There are two edges and four contacts involved in each edge swap. The fate of each edge and contact is summarized in the following pseudo-chemical equation:

In the model, any given contact (

*ego*,

*alter*) will be reassigned to (

*ego*,

*alter*′) at a constant rate

*ρ*. Equivalently, a given edge is swapped at a rate

*p*/2.

A node's degree never changes during an edge swap and thus the degree distribution is preserved. This property has made the random edge swap a common starting point for investigations of dynamic networks. Discrete-time versions of the rewiring process have been well studied in applications outside of epidemiology (

Watts & Strogatz 1998;

Maslov & Sneppen 2002;

Evans & Plato 2007;

Holme & Zhao 2007)

For mathematical tractability, we make a few simplifying assumptions about the epidemic process. First, for the duration of a contact, infectious individuals transmit disease to neighbours at a constant rate *r*. Second, infectious individuals become recovered at a constant rate *μ*.

We also simplify the mathematics by considering only the simplest category of heterogeneous networks—semi-random networks that are random with respect to a given degree distribution (Molloy & Reed

1995,

1998). The degree distribution will have density

*p*_{k}, which is the probability that a node chosen uniformly at random has

*k* concurrent contacts.

The simultaneous epidemic and network dynamics described above collectively determine the NE model. An even more realistic model would allow the number *k* of concurrent contacts of a node to vary stochastically, but the current model offers a valuable first step towards understanding epidemiological processes on dynamic host networks.

(a) Dynamics

We will expand on the dynamic probability generating function (PGF) techniques first introduced in

Volz (2007) to model SIR-type epidemics in static networks. These techniques are powerful and are easily extended to consider dynamic contact networks. We start with an overview of the basic model and then introduce additional terms that model the NE process.

The concurrent degree distribution

*p*_{k} will be generated by the PGF

The dummy variable

*x* in this equation serves as a placeholder for dynamic variables.

Let

_{X} be the sets of contacts (arcs) where

*ego* is in the set

*X*. We will consider the sets of all susceptible, infected and recovered nodes, denoted

,

and

, respectively.

is then defined as the fraction of total contacts in set

_{X}. Now let

_{XY} be the set of contacts such that

*ego* is the set

*X* and

*alter* is in the set

*Y*, and

be the fraction of total contacts in set

_{XY}. For example,

is the fraction of all arcs in the network that connect two currently susceptible nodes ().

| **Table 2**Notation for network and epidemic quantities. |

The following derivation assumes that each contact of a susceptible node

has a uniform probability that

, denoted

, and a uniform probability

that

. A degree

*k* susceptible node has an expected number

contacts with infectious nodes; and, in a small time d

*t*, an expected number

of a degree

*k* susceptible nodes' contacts will transmit disease to that node. The instantaneous hazard of infection for a degree

*k* susceptible node is then given by

Let

denote the fraction of degree

*k* nodes remaining susceptible at time

*t*. Equation

(2.3) implies

Now let

be the fraction of degree

*k*=1 nodes in the network that remain susceptible at time

*t*. Equation

(2.4) implies that

. (Henceforth, variables that are clearly dynamic, for example

*θ*, appear without a time (

*t*) variable.)

We use the PGF for the network degree distribution (equation

(2.2)) to calculate the fraction of nodes that remain susceptible at time

*t*.

The dynamics of

*θ* in equation

(2.5) are given by

Unfortunately, this does not form a closed system of differential equations, as equation

(2.6) depends on the dynamic variable

*p*_{I}. From the definition of

*p*_{I} we have

To obtain the derivatives of

and

, we observe that, in time d

*t*,

nodes become infectious, resulting in modifications to the sets

,

and

. In particular, any given arc from a newly infected individual was formerly in one of

,

or

and is now in one of

,

or

. The

new infected are not selected uniformly at random from the susceptible population, but rather with probability proportional to the number of contacts to infectious nodes.

We pause for a few definitions. First, it is useful to break the degree of a node into three quantities: the number of contacts to currently susceptible, infected and recovered nodes. We refer to these as

*X-degrees*, where

or

*R*, respectively. Second, imagine following a randomly chosen contact to its

*alter* and counting all the edges emanating from that node, except for the one on which we have arrived. We call the resulting total quantity the

*excess degree* of the node, and the resulting neighbour-specific quantities

*excess X-degrees* of the node, where

*X* indicates one of the three possible disease states.

We introduce the notation

to represent the average excess

*Z*-degree of nodes currently in disease state

*X* selected by following a randomly chosen arc from the set

; in other words, the excess

*Z*-degree of a node of type

*X* selected with probability proportional to the number of contacts to nodes of type

*Y*. We further define

to be the average (total) excess degree of nodes currently in disease state

*X* selected by following a randomly chosen arc from the set

. For example, imagine first randomly choosing an arc from

, then following that arc to its destination (susceptible) node and finally counting all of the other edges emanating from that node (ignoring the one along which we arrived). Then

,

and

give the average number of contacts to other susceptible, infected and recovered nodes chosen in this way, respectively;

gives the average total number of contacts emanating from nodes chosen in this way.

Using this notation, the equations for

and

are as follows (for more details, see

Volz (2007))

The calculations of the

are straightforward and based on the current degree distribution of susceptible nodes. The calculations are given in the electronic supplementary material and in

Volz (2007) and result in the following:

Combining the equations for

and

yields the dynamics of

*p*_{I} in terms of the parameters

*r* and

*μ*, the PGF

*g*(·), and the dynamic variable

*p*_{S}. The resulting model is given in . The dynamics for

*p*_{S} complete the model and can be derived analogously to the equation for

*p*_{I} (see the electronic supplementary material for details).

| **Table 3**System of equations used to model the spread of SIR epidemic in a static semi-random network. |

(i) Dynamic contact networks

We now extend the model given in to allow NEs at a rate

*ρ*. First consider

*θ*. An edge swap (equation

(2.1)) will affect the arrangement of edges among susceptible, infectious or recovered nodes; however, it will never directly cause a node to change its disease state. The dynamics of

*θ* are only indirectly influenced by NE dynamics, through changes to

*p*_{I}, and thus equation

(2.6) still holds.

NE does, however, affect the composition of contacts between susceptible and infectious nodes. We postulate that the equations for

and

can be expressed in the following modified forms:

and

where the functions

represent the contribution of NE dynamics to the system.

Thus

*p*_{I} will be decreased by NE dynamics at a rate

.

Thus

*p*_{I} is increased by NE dynamics at rate

. We add the positive and negative contributions to calculate the total influence of NE on

*p*_{I}.

By similar reasoning, we determine

.

The complete system of NE-adjusted equations is reported in . The dynamic variable

*M*_{I}, however, appears in equation

(2.17) and cannot be put in terms of the variables

*θ, p*_{S} and

*p*_{I}. Therefore, a fourth dynamical equation must be included for

*M*_{I}, which is listed in . Fortunately, the dynamics are very straightforward. Recall that

*δ*_{S,I} denotes the average excess degree of susceptibles chosen by following randomly selected arcs between infectious and susceptible nodes, and thus indicates the average excess degree for individuals who become infected in a small time interval d

*t*. We add one (

) to obtain the average degree for such newly infected nodes. Then, recalling that

*M*_{I} decays at rate

*μ*, we have

| **Table 4**Deterministic NE model. (This system of equations is used to model the spread of an SIR-type epidemic in a dynamic semi-random network with stochastic exchange of neighbours at constant rate *ρ*.) |

All of the results that follow will assume that a very small fraction

*ϵ* of nodes is initially infected, and thus there is only a very small probability that two initially infected individuals contact each other. Then we anticipate the following initial conditions (

Volz 2007):

(b) Convergence to a mass-action model

In the limit of large mixing rate (*ρ*→∞), the probability of being connected to a susceptible, infectious or recovered node is directly proportional to the number of edges emanating from nodes in each state. Referring to , it is clear that *p*_{I} converges instantly to *M*_{I} and *p*_{S} converges instantly to *M*_{S}. Here, we show that as the mixing rate grows, the underlying network structure becomes irrelevant and the model converges to a mass-action model.

To see this, we replace every occurrence of the variable

*p*_{I} in the system of equations in with

*M*_{I}. Then

Neither equations

(2.22) or

(2.23) depend on

*p*_{S}, and thus together form a closed system of equations that describe the epidemic dynamics. These equations incorporate arbitrary heterogeneity in contact rates, but no longer consider an explicit contact network. When we assume that contact rates are homogeneous throughout the population, then these equations are equivalent to a simple SIR compartmental model. To illustrate, we retrieve the standard SIR dynamics by setting

*g*(

*x*)=

*x*, which means that every node has exactly one concurrent contact. In such a population, the number of arcs to infectious individuals is exactly equal to the number of infectious nodes, that is,

*p*_{I}=

*I*. Then, substituting into equations

(2.22) and

(2.23), we reproduce the standard equations

Equations

(2.22) and

(2.23) are potentially extremely useful, as they incorporate arbitrary heterogeneity into a system of equations no more complex than the standard compartmental SIR model.

demonstrates the convergence of the NE model to the corresponding mass-action model for a Poisson degree distribution (

*r*=

*μ*=0.2,

*z*=1.5). The circles indicate the solution to the mass-action model (equations

(2.22) and

(2.23)). We observe that the convergence is quite rapid as

*ρ* is increased in the multiples of

*μ*. This supports the common assumption that the mass-action model is a reasonable approximation for populations marked by many short-duration contacts.