# Bounding the Size and Probability of Epidemics on Networks

Joel C. Miller  655 W 12th Ave, Vancouver, BC V5Z 4R4, Canada

###### Abstract

We consider an infectious disease spreading along the edges of a network which
may have significant clustering. The individuals in the population have
heterogeneous infectiousness and/or susceptibility. We define the _out-
transmissibility_ of a node to be the marginal probability that it would
infect a randomly chosen neighbor given its infectiousness and the
distribution of susceptibility. For a given distribution of out-
transmissibility, we find the conditions which give the upper [or lower]
bounds on size and probability of an epidemic, under weak assumptions on the
transmission properties, but very general assumptions on the network. We find
similar bounds for a given distribution of in-transmissibility (the marginal
probability of being infected by a neighbor). We also find conditions giving
global upper bounds on size and probability. The distributions leading to
these bounds are network-independent. In the special case of networks with
high girth (locally tree-like), we are able to prove stronger results. In
general the probability and size of epidemics are maximal when the population
is homogeneous and minimal when the variance of in- or out-transmissibility is
maximal.

###### keywords:

Epidemiology, Networks, Attack Rate, Probability, Transmissibility

Joel C. Miller

92D3060K35

##  1 Introduction

The spread of infectious disease is governed by many different factors which
vary on the individual level. Heterogeneity in the population comes from a
number of sources including, but not limited to, genetic diversity, previous
infections, vaccination history, or existence of co-infections. In this paper
we investigate the effects of heterogeneity on disease spread, focusing on the
effect of simultaneous heterogeneities in infectiousness and susceptibility.

Figure 1: The spread of disease in a network. The outbreak begins with a
single infected individual [large empty circles] and then spreads along edges
to others. The infected nodes recover with immunity [large filled circles].
Eventually the outbreak dies out.

We consider the spread of infectious diseases in networks as shown in figure
1. Individuals in the population are modeled as nodes and potentially
infectious contacts are modeled as edges between the corresponding nodes. We
consider the spread of an SIR disease, that is the nodes are divided into
three compartments: _Susceptible_ , _Infected_ , and _Recovered_. A
susceptible node may be infected by an infected neighbor. Following infection,
the newly infected node may infect some, all, or none of its neighbors and
then recover. After recovery, a node cannot be reinfected. Typically in a
large network outbreaks are either small or large (in a sense made more formal
in section 2). We are primarily interested in what controls the probability of
large outbreaks and the fraction of nodes infected in a large outbreak.

Before discussing earlier results, we introduce some terminology. The
_transmissibility_ $T_{uv}$ is the probability that an infection of node $u$
would result in direct infection of the neighbor $v$. The _in-
transmissibility_ $T_{in}(v)$ is the marginal probability that a neighbor of
$v$ would infect $v$ given the characteristics of $v$, and the _out-
transmissibility_ $T_{out}(u)$ is the marginal probability that $u$ would
infect a neighbor given the characteristics of $u$. Both the in- and out-
transmissibility necessarily have the same average, $\left\langle
T\right\rangle$. These definitions will be made more precise in section 2.

Most network-based epidemic models assume homogeneous transmissibility
$T_{uv}=\left\langle T\right\rangle$ between all pairs of neighboring nodes.
Models that do allow heterogeneities generally show that they reduce the
probability or size of epidemics [4, 16, 29, 21, 13]. For an arbitrary network
with homogeneous susceptibility [$T_{in}(v)=\left\langle T\right\rangle$ for
all $v$], but heterogeneous infectiousness, [16] showed that epidemics are
most likely and largest if infectiousness is homogeneous
[$T_{out}(u)=\left\langle T\right\rangle$ for all $u$]. It was noted by [29]
that the same argument shows that with homogeneous susceptibility epidemics
are least likely and smallest if infectiousness is maximally heterogeneous
($T_{out}=0$ for a fraction $1-\left\langle T\right\rangle$ of the population
and $T_{out}=1$ for the remainder). The recent work of [21, 13] considered the
effect of heterogeneity on a specific subclass of unclustered networks
(variously called Molloy–Reed networks [23] or Configuration Model networks
[26]), finding similar results. One of these, [21], studied simultaneous
heterogeneities in susceptibility and infectiousness, showing that for given
$\left\langle T\right\rangle$, the same cases give the upper and lower bounds
on probability while epidemics are largest if susceptibility is homogeneous
and smallest if susceptibility is maximally heterogeneous. We are unaware of
any work which has considered simultaneous heterogeneities in infectiousness
and susceptibility in networks with clustering or even in unclustered networks
more general than Molloy–Reed networks.

In this paper we investigate the spread of epidemics in which $T_{in}$ and
$T_{out}$ can simultaneously be heterogeneous, using techniques from [16] and
[21]. We will consider both clustered and general unclustered networks.
Clustered networks are more difficult because of the existence of short
cycles, and so a stronger assumption will be made for them.

Often only the distribution of $T_{out}$ (or, more rarely, of $T_{in}$) would
be available early in an outbreak. If we know the distribution of $T_{out}$,
it does not in general uniquely determine the distribution of $T_{in}$ and so
we cannot fully predict the final details of an outbreak. Our focus is on
identifying the best and worst case scenarios given the distribution of
$T_{out}$ (or $T_{in}$), thus helping to provide policy makers with knowledge
of what to expect and how best to mitigate it.

Mathematical theories modeling the spread of infectious diseases have been
developed in a number of fields [14, 1, 2, 8]. The techniques used include
differential equations, stochastic models, agent-based simulations, and
network-based approaches. The differential equations approaches may be thought
of as a mean-field approximation to a subclass of network models, while the
stochastic and agent-based approaches can be made formally equivalent to
network-based methods [13, 24]. Consequently results for networks will apply
to other models as well. Network epidemic models have primarily been studied
by the statistics community [30, 16, 17, 4, 5, 22, 3] and the statistical
physics/applied mathematics communities [25, 20, 19, 28, 9, 27, 18, 10, 11].
In general the statistics community has produced more rigorous results, but
has considered more restricted classes of networks. The physics and applied
mathematics communities have considered a wider range of networks, but the
results are less rigorous. The interaction between these fields has been
relatively sparse, leading to repeated discoveries of some results and a lack
of cohesion in the topics studied. We attempt to bring some of these different
approaches together in this paper.

This paper is structured as follows: in section 2 we introduce the model and
clarify definitions. In section 3 we consider epidemics spreading on general
networks. In section 4 we find stronger results for networks with no short
cycles. Finally in section 5 we discuss extensions and implications of our
results.

##  2 Epidemics in networks

We consider the spread of disease on a network $G$. An _outbreak_ begins when
a single node (the _index case_) chosen uniformly from the population is
infected. The disease spreads from an infected node $u$ to a neighboring
susceptible node $v$ with a probability equal to the _transmissibility_
$T_{uv}$. Each infected node attempts to infect each of its neighbors and then
recovers (and is no longer susceptible or infected). The outbreak ends when no
infected nodes remain.

This section, like Gaul, is divided into three parts. First we describe the
neighbor-to-neighbor transmissibility $T_{uv}$. This will depend on the
characteristics of both $u$ and $v$. We then introduce the concept of an
Epidemic Percolation Network, which is a tool to study the routes of
transmission in a given network. We finally discuss tools which will be used
to make the concept of a “large network” rigorous.

###  2.1 Transmissibility

Following [21], we assume that the factors influencing infectiousness of node
$u$ and susceptibility of node $v$ may be summarized in $\mathcal{I}_{u}$ and
$\mathcal{S}_{v}$. In general, these may be vector-valued functions (though
with few exceptions they are taken to be scalars in the literature). For
example, $\mathcal{I}_{u}$ may represent $u$’s viral load, duration of
infection, and willingness or ability to leave work if sick, while
$\mathcal{S}_{v}$ may represent $v$’s previous vaccination history, genetic
predisposition to infection, and previous exposure to related infections. If
$u$ and $v$ are neighbors, the transmissibility $T_{uv}$ is then

$T_{uv}=T(\mathcal{I}_{u},\mathcal{S}_{v})$

for some function $T$. The function $T(\mathcal{I},\mathcal{S})$ is the
probability of transmission from a node with infectiousness $\mathcal{I}$ to a
node with susceptibility $\mathcal{S}$ assuming that the nodes are joined by
an edge. We may think of $T_{uv}$ as defined only for neighboring nodes, or we
may take $T_{uv}=\chi_{\\{u,v\\}}T(\mathcal{I}_{u},\mathcal{S}_{v})$ where
$\chi_{\\{u,v\\}}=0$ if $\\{u,v\\}$ is not an edge and $1$ if it is.

We assume that $\mathcal{I}$ and $\mathcal{S}$ are assigned independently,
using the probability density functions $P(\mathcal{I})$ and $P(\mathcal{S})$
(although we use the same symbol $P$ for both, we assume that the two
functions are different). Particularly if $\mathcal{I}$ and $\mathcal{S}$ are
vectors, we may not be able to clearly define which of two nodes is “more
infectious” (_i.e._ , there may not be a well-defined ordering). For example,
with a sexually transmitted disease, we might have $u_{1}$ and $u_{2}$
infected, with $u_{1}$ having a high viral load and regular condom use (with
occasional lapses), while $u_{2}$ has a low viral load but no condom use. Let
us assume they have contacts with susceptibles $v_{1}$ and $v_{2}$ where
$v_{1}$ has a high level of resistance, and thus will only be infected by a
large dose, while $v_{2}$ has no immune protection and thus will be infected
by even a small dose. Under these assumptions, $u_{1}$ is more likely to
infect $v_{1}$, while $u_{2}$ is more likely to infect $v_{2}$. Which is “more
infectious” depends on the test susceptible considered.

The probability that $u$ infects a neighbor (prior to knowing $\mathcal{S}$
for that neighbor) is given by the _out-transmissibility_ of $u$

$T_{out}(u)=\int T(\mathcal{I}_{u},\mathcal{S})P(\mathcal{S})d\mathcal{S}$

and the probability that $v$ would be infected by a neighbor is given by the
_in-transmissibility_ of $v$

$T_{in}(v)=\int T(\mathcal{I},\mathcal{S}_{v})P(\mathcal{I})d\mathcal{I}$

At times it will be convenient to use $T_{out}(\mathcal{I})$ and
$T_{in}(\mathcal{S})$ [rather than $T_{out}(u)$ and $T_{in}(v)$] to denote the
out- and in-transmissibility of arbitrary nodes with $\mathcal{I}$ and
$\mathcal{S}$ respectively. When the concepts of being “more infectious” and
“more susceptible” are clearly defined, $T_{in}(\mathcal{S})$ and
$T_{out}(\mathcal{I})$ are invertible functions. However, because the ordering
is not well-defined in general, they may not be invertible. If they are
invertible, it is often convenient to change variables and set
$\mathcal{I}_{u}=T_{out}(u)$ or $\mathcal{S}_{v}=T_{in}(v)$. We will do this
frequently in section 3, where we restrict our attention to cases where the
ordering described above is well-defined.

From $P(\mathcal{S})$ and $P(\mathcal{I})$, we may find the distributions of
$T_{in}$ and $T_{out}$. We use $Q_{in}(T_{in})$ to denote the probability
density function for the in-transmissibility $T_{in}$ and $Q_{out}(T_{out})$
to denote the probability density function for the out-transmissibility
$T_{out}$. The averages $\int_{0}^{1}T_{in}Q_{in}(T_{in})dT_{in}$ and
$\int_{0}^{1}T_{out}Q_{out}(T_{out})dT_{out}$ are both equal to $\left\langle
T\right\rangle$.

Given distributions of $\mathcal{I}$ and $\mathcal{S}$ and the function $T$,
there is always a $Q_{in}$ and $Q_{out}$ pair that result. Also, given a
$Q_{in}$ or a $Q_{out}$ it is always possible to find $P(\mathcal{I})$,
$P(\mathcal{S})$, and $T$ that are consistent. For example, given any
$Q_{in}$, for each node $v$ we assign a $T_{in}(v)$ from $Q_{in}$ and set
$\mathcal{S}_{v}=T_{in}(v)$. Then $T(\mathcal{I},\mathcal{S})=\mathcal{S}$ is
consistent with $Q_{in}$ and yields
$Q_{out}(T_{out})=\delta(T_{out}-\left\langle T\right\rangle)$. This means
that for any distribution of in-transmissibility, it is possible that the
infectiousness of nodes is homogeneous. Although it is possible to find a
$Q_{in}$ for any $Q_{out}$ (and _vice versa_) not all pairs $Q_{out}$ and
$Q_{in}$ are compatible. For example, if $Q_{in}=(1-\left\langle
T\right\rangle)\delta(T_{in})+\left\langle T\right\rangle\delta(T_{in}-1)$
(_i.e._ , susceptibility is maximally heterogeneous) then the out-
transmissibility must be homogeneously distributed; no other distribution is
possible. This particular example will be important in Section 4.

Although in principle $\mathcal{I}$ and $\mathcal{S}$ may be vector-valued,
they frequently are assumed to be scalars with the transmissibility between
two neighbors given by (for example [7, 21])

$T_{uv}=T(\mathcal{I}_{u},\mathcal{S}_{v})=1-\exp(-\alpha\mathcal{I}_{u}\mathcal{S}_{v})$
(1)

A number of disease models yield this form. For example: let $\alpha$ be the
rate at which virus from an infected person reaches a susceptible person. Let
$\mathcal{I}_{u}$ be the infectious period of $u$. Let $\mathcal{S}_{v}$ be
the probability that a virus reaching $v$ causes infection. Then the
probability $p$ that $v$ has not become infected satisfies
$\dot{p}=-\alpha\mathcal{S}_{v}p$. Integrating this over the infectious period
$\mathcal{I}_{u}$ of $u$ yields equation (1).

We need one final concept related to the transmissibility. Let a node $u$ be
given, and let $V=\\{v_{1},\ldots,v_{m}\\}$ be a subset of the neighbors of
$u$. Assume we know
$\vec{\mathcal{S}}=(\mathcal{S}_{v_{1}},\ldots,\mathcal{S}_{v_{m}})$, but not
$\mathcal{I}_{u}$. Define

$\phi_{in}(V,\vec{\mathcal{S}})=\int\prod_{v\in
V}[1-T(\mathcal{I},\mathcal{S}_{v})]P(\mathcal{I})d\mathcal{I}\,.$ (2)

This is the probability that $u$ will not infect any node in $V$ given
knowledge of $\mathcal{S}$ for each $v\in V$, but marginalized over the
possible values of $\mathcal{I}$ for $u$. We may similarly define

$\displaystyle\psi_{in}(V)$
$\displaystyle=\int\phi_{in}(V,\vec{\mathcal{S}})P(\vec{\mathcal{S}})d\vec{\mathcal{S}}\,,$
(3) $\displaystyle=\int(1-T_{out})^{|V|}Q_{out}(T_{out})dT_{out}\,.$ (4)

This is the probability that $u$ will not infect any $v\in V$ marginalized
over $\mathcal{S}$ of $v\in V$ and the values of $\mathcal{I}$ for $u$. If
$|V|=1$, then $\psi_{in}(V)=1-\left\langle T\right\rangle$, which will be
important later when we consider unclustered networks.

###  2.2 Epidemic Percolation Networks

Given a network $G$, the distributions $P(\mathcal{I})$ and $P(\mathcal{S})$,
and the function $T(\mathcal{I},\mathcal{S})$, we assign $\mathcal{I}$ and
$\mathcal{S}$ to each node of $G$. We then create a new directed network
$\mathcal{E}$ which is an _Epidemic Percolation Network_ (EPN) [12] as
follows: the nodes of $\mathcal{E}$ are the nodes of $G$. For each edge
$\\{u,v\\}$ of $G$, we place directed edges $(u,v)$ and $(v,u)$ into
$\mathcal{E}$ with probability $T_{uv}$ and $T_{vu}$ respectively. The
original network $G$ gives the paths a disease _could_ follow, while a
realization of $\mathcal{E}$ gives the paths the disease _will_ follow (if
given the chance) for a simulation.

The out-component of a given node $u$ found by assigning $\mathcal{I}$ and
$\mathcal{S}$ and generating an EPN comes from the same distribution as the
nodes infected by the dynamic epidemic process described earlier with $u$ as
the index case. The processes are formally equivalent.

To motivate some definitions, we assume sufficiently high transmissibility
that there are nodes in $\mathcal{E}$ with giant in- or out-components [6]. We
define $H_{out}$ to be those nodes with a giant in-component, and $H_{in}$ to
be those nodes with a giant out-component in $\mathcal{E}$. We define
$H_{scc}=H_{in}\cap H_{out}$. $H_{scc}$ will almost surely be a strongly
connected component. $H_{in}$ is the in-component of $H_{scc}$ and $H_{out}$
is its out-component. In general, infection of any $u\in H_{in}$ results in
infection of all nodes in $H_{out}$ and occasionally a few other nodes (if
$u\not\in H_{scc}$). We define such an outbreak to be an _epidemic_. If
$u\not\in H_{in}$, then a small _self-limiting_ outbreak occurs.

For large values of $N=|G|$, the probability of an epidemic is given by
$\mathcal{Y}=\mathbb{E}[|H_{in}|]/N$ and the expected fraction infected in an
epidemic is given by
$\mathcal{A}=\mathbb{E}[|H_{out}|]/N+\mathcal{O}\left(\log N/N\right)$. As $N$
grows, $|H_{out}|/N$ approaches $\mathbb{E}[|H_{out}|]/N$, and so the size of
a single epidemic in a large population closely approximates expected size of
epidemics (note that if we include non-epidemic outbreaks in the average, this
does not hold).

If the directions of arrows in the EPNs are reversed, then $H_{in}$ and
$H_{out}$ interchange roles. Consequently, replacing
$T_{uv}=T(\mathcal{I}_{u},\mathcal{S}_{v})$ with
$\hat{T}_{uv}=T(\mathcal{I}_{v},\mathcal{S}_{u})$ interchanges the size and
probability. As such, results derived for the probability of an epidemic also
apply to the size.

###  2.3 Large Networks

The results we derive will be appropriate in the limit of “large networks”.
However, in practice we are usually interested in a single given network.
Unfortunately $|G|\to\infty$ is a vague concept when we are given a single,
finite network. There are many ways to increase its size, with different
impacts on epidemics. In this section, we define what is meant by
$|G|\to\infty$ in a way that allows us to produce rigorous results.

Consider a sequence of networks $\\{G_{n}\\}$ which satisfy $|G_{n}|\to\infty$
as $n\to\infty$. We define an open ball $B_{d}(u)$ to be a network centered at
a node $u$ such that all nodes $v\in B_{d}(u)$ are at most a distance $d$ from
$u$. Given a network $G$, we define $P_{G}(B_{d}(u))$ to be the probability
that if we choose a node $\hat{u}$ randomly from $G$, then the set of nodes of
distance at most $d$ from $\hat{u}$ is isomorphic to $B_{d}(u)$ (with the
isomorphism mapping $\hat{u}$ to $u$).

We define _sequential convergence of local statistics_ to mean that given any
$d$ and $B_{d}(u)$, $P_{G_{n}}(B_{d}(u))=P_{G_{d}}(B_{d}(u))$ for all $n\geq
d$. For the results developed later, all that is strictly needed is that
$P_{G_{n}}(B_{d}(u))$ converges as $n\to\infty$, but the stronger statement
that for $n\geq d$ they do not change makes the proofs simpler. This means
that for large enough $n$, networks have the same “small-scale” structure, and
the size of what is considered “small-scale” increases with $|G|$. We restrict
our attention to sequences which have sequential convergence of local
statistics.

For a given EPN, we define $H_{in}(d)$ and $H_{out}(d)$ to be the set of nodes
from which a path of length (at least) $d$ begins or ends respectively. At
large $d$, these will correspond to the $H_{in}$ and $H_{out}$ described
earlier. We define $\mathcal{Y}_{d}(G)$ and $\mathcal{A}_{d}(G)$ to be the
probability that a randomly chosen node from $G$ is in $H_{in}(d)$ and
$H_{out}(d)$ respectively. Sequential convergence means that
$\mathcal{Y}_{d}(G_{n})=\mathcal{Y}_{d}(G_{d})$ and
$\mathcal{A}_{d}(G_{n})=\mathcal{A}_{d}(G_{d})$ for $n\geq d$. We finally
define

$\displaystyle\mathcal{Y}$
$\displaystyle=\lim_{d\to\infty}\mathcal{Y}_{d}(G_{d})\,,$
$\displaystyle\mathcal{A}$
$\displaystyle=\lim_{d\to\infty}\mathcal{A}_{d}(G_{d})\,.$

$\mathcal{Y}$ measures the probability of an epidemic and $\mathcal{A}$
measures the fraction infected.

We will prove our results in the limit $n\to\infty$ by showing that
$H_{in}(d)$ and $H_{out}(d)$ for a given $G_{n}$ are maximal or minimal under
different conditions. This means that our results are generally true for
arbitrary finite networks. The reason we use the large $n$ limit is because
for networks which are small it is unclear what constitutes a giant component
in an EPN, or similarly, for a network with some unusual structure on a size
comparable to the network size (for example a network made up of a few
disconnected components), a giant component may not be uniquely defined. Using
the large $n$ limit avoids these problems. We could avoid the need for a limit
by instead assuming the existence of a giant strongly connected component in
the EPN and showing that the same conditions maximize or minimize the
probability a node is in the in- or out-component of this giant strongly
connected component.

##  3 Bounds in general networks

We begin by considering the spread of infectious diseases on arbitrary
networks. We begin with a simple lemma which we will need in this section and
the next.

######  Lemma 3.1 (Edge Reversal)

Given $T_{uv}=T(\mathcal{I}_{u},\mathcal{S}_{v})$, if we interchange the roles
of infectiousness and susceptibility so that
$T_{uv}=T(\mathcal{I}_{v},\mathcal{S}_{u})$ for all edges, then $\mathcal{Y}$
and $\mathcal{A}$ interchange roles.

###### Proof 3.2

If we replace $T_{uv}=T(\mathcal{I}_{u},\mathcal{S}_{v})$ with
$\hat{T}_{uv}=T(\mathcal{I}_{v},\mathcal{S}_{u})$, then the new EPNs
correspond to reversing the direction of edges in the original EPNs. Since
reversing the direction of edges in an EPN interchanges $H_{in}(d)$ and
$H_{out}(d)$, this interchanges $\mathcal{Y}$ and $\mathcal{A}$, and finishes
the proof. ∎

We now make a simplifying assumption which we will need for networks with
short cycles.

[Ordering Assumption] If
$T(\mathcal{I}_{1},\mathcal{S}_{1})>T(\mathcal{I}_{2},\mathcal{S}_{1})$ for
any $\mathcal{S}_{1}$, then $T(\mathcal{I}_{1},\mathcal{S})\geq
T(\mathcal{I}_{2},\mathcal{S})$ for all $\mathcal{S}$. Further, strict
inequality occurs for a set of positive measure. Similarly if
$T(\mathcal{I}_{1},\mathcal{S}_{1})>T(\mathcal{I}_{1},\mathcal{S}_{2})$ for
any $\mathcal{I}_{1}$, then $T(\mathcal{I},\mathcal{S}_{1})\geq
T(\mathcal{I},\mathcal{S}_{2})$ for all $\mathcal{I}$ with strict inequality
for a set of positive measure.

The ordering assumption is a statement about the functional form of
$T(\mathcal{I},\mathcal{S})$. It places no restrictions on the network. The
assumption holds for equation (1), but as noted earlier there are many
scenarios where it fails.

The ordering assumption implies that $T_{out}(\mathcal{I})$ and
$T_{in}(\mathcal{S})$ are invertible mappings. It also allows us to assume
that $\mathcal{I}$ is a scalar quantity ordered such that

$\mathcal{I}_{u}\geq\mathcal{I}_{u^{\prime}}\quad\Leftrightarrow\quad
T(\mathcal{I}_{u},\mathcal{S})\geq
T(\mathcal{I}_{u^{\prime}},\mathcal{S})\>\>\>\forall\mathcal{S}\quad\Leftrightarrow\quad
T_{out}(u)\geq T_{out}(u^{\prime})$

and further $\mathcal{I}_{u}>\mathcal{I}_{u^{\prime}}\Leftrightarrow
T_{out}(u)>T_{out}(u^{\prime})$. We may make similar conclusions about
$\mathcal{S}$. There will be more than one way to represent $\mathcal{I}$ or
$\mathcal{S}$ as scalars. It will frequently (but not always) be convenient to
identify $\mathcal{I}$ with $T_{out}(\mathcal{I})$ and $\mathcal{S}$ with
$T_{in}(\mathcal{S})$.

Previous work by [16] considered the spread of infectious diseases on networks
for which the only heterogeneity came from variation in duration of infection.
Hence all nodes have the same $T_{in}$, and variation occurs only in
$T_{out}$. This model satisfies the ordering assumption. In this section we
generalize the results of [16] by allowing $T_{in}$ and $T_{out}$ to be
heterogeneous simultaneously.

We will drop the ordering assumption in section 4 where we consider networks
with no short cycles. Even in this section, many of the results hold without
the ordering assumption, but the proofs are less clean. The assumption is only
strictly needed for Theorems 3.5, 3.9, and 3.11.

We are now ready to show that increased heterogeneity generally decreases the
size and probability of epidemics. We show that for a given $Q_{in}$ [resp.
$Q_{out}$], both $\mathcal{Y}$ and $\mathcal{A}$ are maximal when $T_{out}$
[resp. $T_{in}$] is homogeneous. They are minimal when the variance of
$T_{out}$ [resp. $T_{in}$] is maximal subject to the constraint of $Q_{in}$
[resp. $Q_{out}$].

We can also derive conditions for a global upper bound on $\mathcal{Y}$ and
$\mathcal{A}$. The upper bounds occur when $T_{uv}=\left\langle
T\right\rangle$ for all neighbors $u$ and $v$. We hypothesize a lower bound,
but cannot prove it in networks with short cycles.

To make the notation cleaner in the following lemma, we identify $\mathcal{S}$
with $T_{in}$ and so we may use $T(\mathcal{I},T_{in})$ in place of
$T(\mathcal{I},\mathcal{S})$.

###### Lemma 3.3

Assume a sequence of networks $\\{G_{n}\\}$ with sequential convergence of
local statistics and a susceptibility distribution $Q_{in}(T_{in})$. Assume
the ordering assumption holds and consider a distribution of infectiousness
$P_{1}(\mathcal{I})$ with transmissibility given by
$T_{1}(\mathcal{I},T_{in})$, that is consistent with $Q_{in}$. Let
$\phi_{in,1}(V,\vec{\mathcal{S}})$ be as in equation (2). Let
$\mathcal{A}_{1}$ and $\mathcal{Y}_{1}$ be the corresponding attack rate and
epidemic probability. Similarly choose another $P_{2}(\mathcal{I})$,
$T_{2}(\mathcal{I},T_{in})$ with corresponding $\mathcal{A}_{2}$,
$\mathcal{Y}_{2}$, and $\phi_{2}(V,\vec{\mathcal{S}})$. Assume that
$\phi_{in,1}(V,\vec{\mathcal{S}})\leq\phi_{in,2}(V,\vec{\mathcal{S}})$ for all
$V$ and $\vec{\mathcal{S}}$. Then $\mathcal{A}_{1}\geq\mathcal{A}_{2}$ and
$\mathcal{Y}_{1}\geq\mathcal{Y}_{2}$.

###### Proof 3.4

Let $d\geq 0$ be given.

Take $G_{n}$, $n\geq d$. We will show that a node in an EPN created from
$G_{n}$ using the first distribution is more likely to be in $H_{out}(d)$ than
a node in an EPN created using the second distribution.

Choose any node $u$ from $G_{n}$. Partition the nodes of $G_{n}$ into disjoint
sets $\\{u\\}$, $U_{1}$, and $U_{2}$. To the nodes in $U_{1}$ we assign
$\mathcal{I}$ from $P_{1}(\mathcal{I})$ and to the nodes in $U_{2}$ we assign
$\mathcal{I}$ from $P_{2}(\mathcal{I})$. We assign $T_{in}$ to all nodes from
$Q_{in}(T_{in})$. We will consider the effects of adding $u$ to $U_{1}$ versus
adding it to $U_{2}$.

Consider a partial EPN $\mathcal{E}$ created by assigning edges $(w,v)$ from
all $w\neq u$, using $T_{1}(\mathcal{I}_{w},T_{i}(v))$ if $w\in U_{1}$ and
$T_{2}(\mathcal{I}_{w},T_{i}(v))$ if $w\in U_{2}$. Now consider an arbitrary
node $u^{\prime}$ (which may be $u$) which is not already in $H_{in}(d)$, but
which would join $H_{in}(d)$ if the appropriate edges were added from $u$. Let
$V$ be the set of neighbors $v$ of $u$ for which adding the edge $(u,v)$ would
allow a path from $u^{\prime}$ to $u$ to be extended to a path of length $d$.

We consider extensions of $\mathcal{E}$ formed by placing $u$ into $U_{1}$ or
$U_{2}$. The probability that $u^{\prime}$ would be in $H_{in}(d)$ in the
extended EPN is equal to the probability that $u$ has at least one edge to
some node in $V$. This probability is at least as high if $u\in U_{1}$ as if
$u\in U_{2}$ by our assumption
$\phi_{in,1}(V,\vec{S})\leq\phi_{in,2}(V,\vec{S})$. Consequently the
probability of $u^{\prime}$ to be in $H_{in}(d)$ is maximal if $u\in U_{1}$.
Induction on $|U_{1}|$ shows that $\mathcal{Y}_{d}(G_{n})$ is largest if all
nodes are in $U_{1}$.

We now show that $u\in U_{1}$ increases $\mathcal{A}_{d}$ compared with $u\in
U_{2}$. We can prove that placing $u$ in $U_{1}$ versus $U_{2}$ can only
increase the probability of a node to be at the end of a length $d$ path. The
proof proceeds largely as above. Consider the same partial EPN $\mathcal{E}$
defined above. Let $u^{\prime}$ be a node which is not in $H_{out}(d)$ but
would be if an edge from $u$ to any $v\in V$ (note that $u\neq u^{\prime}$).
The probability that $u^{\prime}$ will be in $H_{out}(d)$ is
$\phi_{in,1}(V,\vec{\mathcal{S}})$ or $\phi_{in,2}(V,\vec{\mathcal{S}})$
depending on whether $u$ is assigned $\mathcal{I}$ from $P_{1}$ or $P_{2}$.
Because $\phi_{in,1}(V,\vec{\mathcal{S}})\leq\phi_{in,2}(V,\vec{\mathcal{S}})$
it follows that $\mathcal{A}_{d}$ is largest if $u\in U_{1}$. Induction on
$|U_{1}|$ shows $\mathcal{A}_{d}(G_{n})$ is maximal if all nodes are in
$U_{1}$.

Taking $d\to\infty$, it follows then that $\mathcal{Y}$ and $\mathcal{A}$ are
maximal if all nodes are in $U_{1}$, and so the proof is finished. ∎

We begin by showing that for fixed distribution of in-transmissibility, the
size and probability are largest when the out-transmissibility is homogeneous.

###### Theorem 3.5

Let $Q_{in}(T_{in})$ be given. Assume that the ordering assumption holds and
that $\\{G_{n}\\}$ satisfies sequential convergence of statistics. Set
$\mathcal{S}_{v}=T_{in}(v)$. Then $\mathcal{Y}$ and $\mathcal{A}$ are
maximized when $T(\mathcal{I},T_{in})=T_{in}$.

###### Proof 3.6

By the ordering assumption, we may take $\mathcal{I}$ to be scalar with
$\mathcal{I}_{1}>\mathcal{I}_{2}$ iff
$T_{out}(\mathcal{I}_{1})>T_{out}(\mathcal{I}_{2})$. This allows us to use
Chebyshev’s “other” inequality [15]: if $h_{1}$ and $h_{2}$ are decreasing
functions of $x$ and $p$ is a probability density function,

$\int h_{1}(x)h_{2}(x)p(x)\,dx\geq\left[\int h_{1}(x)p(x)\,dx\right]\left[\int
h_{2}(x)p(x)\,dx\right]$

By induction $\int[\prod h_{j}(x)]p(x)\,dx\geq\prod\int h_{j}(x)p(x)\,dx$ for
any number of decreasing functions $h_{j}$.

Applying this to the decreasing function
$h_{j}(\mathcal{I})=1-T(\mathcal{I},T_{in}(v_{j}))$ we have

$\displaystyle\phi_{in}(V,\vec{\mathcal{S}})$
$\displaystyle=\int\left[\prod_{v\in
V}h_{j}(\mathcal{I})\right]P(\mathcal{I})\,d\mathcal{I}\,,$
$\displaystyle\geq\prod_{v\in V}1-T_{in}(v)\,,$

with equality if $T(\mathcal{I},T_{in})=T_{in}$. Thus by Lemma 3.3,
$\mathcal{A}$ and $\mathcal{Y}$ are maximal, completing the proof. ∎

We have proven the upper bounds given $Q_{in}(T_{in})$ occur when $T_{out}$ is
homogeneous. We now show the lower bounds occur when $T_{out}$ is maximally
heterogeneous. Because of the ordering assumption, we may take
$\mathcal{S}_{v}=T_{in}(v)$.

###### Theorem 3.7

Let $Q_{in}(T_{in})$ be given, assume the ordering assumption holds, and
assume that $\\{G_{n}\\}$ satisfies sequential convergence of statistics. Take
$\mathcal{I}$ to be chosen uniformly from $[0,1]$. Setting

$T(\mathcal{I},T_{in})=\begin{cases}0&T_{in}<\mathcal{I}\\\
1&T_{in}>\mathcal{I}\end{cases}$ (5)

minimizes $\mathcal{Y}$ and $\mathcal{A}$.

###### Proof 3.8

Given equation (5), we have $\phi_{in}(V,\vec{\mathcal{S}})=\min_{v\in
V}\\{1-T_{in}(v)\\}$.

We need to prove that for any arbitrary transmission function
$\hat{T}(\mathcal{I},T_{in})$ satisfying the ordering assumption and
consistent with $T_{in}$, $\phi_{in}(V,\vec{\mathcal{S}})\leq\min_{v\in
V}\\{1-T_{in}(v)\\}$. To do this, let $\hat{T}$ be given, $T_{in}$ assigned to
$v_{1}$, …, $v_{n}$ and assume $v_{1}$, …, $v_{n}$ are ordered such that
$T_{in}(v_{1})\geq T_{in}(v_{2})\geq\cdots\geq T_{in}(v_{n})$.

Then

$\displaystyle\phi_{in}(V,\vec{\mathcal{S}})$
$\displaystyle=\int\prod_{j=1}^{n}[1-\hat{T}(\mathcal{I},T_{in}(v_{j}))]P(\mathcal{I})d\mathcal{I}\,,$
$\displaystyle\leq\int[1-\hat{T}(\mathcal{I},T_{in}(v_{1}))]P(\mathcal{I})d\mathcal{I}\,,$
$\displaystyle\leq 1-T_{in}(v_{1})\,.$

This shows that for any $\hat{T}$, $\phi_{in}(V,\vec{\mathcal{S}})$ is at most
the value it takes for (5). Thus Lemma 3.3 shows that $\mathcal{Y}$ and
$\mathcal{A}$ are minimal, completing the proof. ∎

We derived the results above with fixed $Q_{in}$. Lemma 3.1 shows that the
equivalent results must hold for $Q_{out}$.

###### Theorem 3.9

Let $Q_{out}(T_{out})$ be given. Assume that the ordering assumption holds and
that $\\{G_{n}\\}$ satisfies sequential convergence of statistics. Set
$\mathcal{I}_{u}=T_{out}(u)$.

  * •

If

$T(T_{out},\mathcal{S})=T_{out}$

Then $\mathcal{Y}$ and $\mathcal{A}$ are maximized.

  * •

If $\mathcal{S}$ is chosen uniformly in $[0,1]$ and

$T(T_{out},\mathcal{S})=\begin{cases}0&T_{out}<\mathcal{S}\\\
1&T_{out}>\mathcal{S}\,,\end{cases}$

then $\mathcal{Y}$ and $\mathcal{A}$ are minimized.

###### Proof 3.10

This follows immediately from Lemma 3.1 with Theorems 3.5 and 3.7. ∎

We now give a global upper bound for both $\mathcal{Y}$ and $\mathcal{A}$.

###### Theorem 3.11

Let $\left\langle T\right\rangle$ be given. Under the ordering assumption with
sequential convergence of statistics for $\\{G_{n}\\}$, the maximum of
$\mathcal{Y}$ and $\mathcal{A}$ occur when $T_{uv}=\left\langle
T\right\rangle$ for all neighboring nodes.

###### Proof 3.12

Consider a $P(\mathcal{I})$, $P(\mathcal{S})$, and
$T(\mathcal{I},\mathcal{S})$ which yields a global maximum for either
$\mathcal{Y}$ or $\mathcal{A}$. If $T_{in}$ is not homogeneous, then we can
find a new infection process which preserves the same $Q_{out}(T_{out})$ with
homogeneous $T_{in}$ which can only increase $\mathcal{Y}$ or $\mathcal{A}$. A
repeated application preserving the new homogeneous in-transmissibility, but
now making $T_{out}$ also homogeneous again can only increase $\mathcal{Y}$ or
$\mathcal{A}$. $T_{out}$ and $T_{in}$ are then homogeneous. This completes the
proof.∎

We finish with a conjecture about global lower bounds.

###### Conjecture 3.13

Under the ordering assumption with sequential convergence of statistics for
$\\{G_{n}\\}$, the minimum of $\mathcal{Y}$ occurs when
$Q_{out}(T_{out})=\left\langle T\right\rangle\delta(T_{out}-1)+(1-\left\langle
T\right\rangle)\delta(T_{out})$.

The minimum of $\mathcal{A}$ occurs when $Q_{in}(T_{in})=\left\langle
T\right\rangle\delta(T_{in}-1)+(1-\left\langle T\right\rangle)\delta(T_{in})$.

Note that if $Q_{out}(T_{out})=\left\langle
T\right\rangle\delta(T_{out}-1)+(1-\left\langle
T\right\rangle)\delta(T_{out})$, then
$Q_{in}(T_{in})=\delta(T_{in}-\left\langle T\right\rangle)$ is homogeneous.

###  3.1 Discussion

The results of this section have focused on extending earlier results of
Kuulasmaa [16] who considered a population with homogeneous susceptibility and
heterogeneities in infectiousness due entirely to variation in duration of
infection. We have extended these results to cover a wide range of
heterogeneities in infectiousness and susceptibility (simultaneously), under
the assumption that infectiousness and susceptibility are assigned
independently. In order to extend the proof used by Kuulasmaa, we have been
forced to make the ordering assumption, which effectively means that if we
order people by how infectious they would be to one test susceptible
individual, the order is the same as we would find for another test
susceptible individual. We do not have any counter-examples to these theorems
in the case where the ordering assumption fails, and so it is not clear that
it is needed. In section 4 we will see that similar results hold in
unclustered networks without needing the ordering assumption.

Our results show that in general increasing the heterogeneity of the
population is useful for either decreasing the size or decreasing the
probability that an epidemic occurs. Given $Q_{in}$ [resp. $Q_{out}$], both
$\mathcal{Y}$ and $\mathcal{A}$ are maximized if $T_{out}$ [resp. $T_{in}$] is
homogeneous and minimized if it is maximally heterogeneous. Similarly, given
just $\left\langle T\right\rangle$, we find that the global maxima of
$\mathcal{Y}$ and $\mathcal{A}$ occur when $T=\left\langle T\right\rangle$.
Perhaps surprisingly, the conditions leading to upper and lower bounds are
independent of the network, though the size of the variation between these
bounds is network-dependent.

Although we can prove lower bounds given $Q_{in}$ [or $Q_{out}$], we cannot
prove global lower bounds given $\left\langle T\right\rangle$. We hypothesize
that the global lower bound for $\mathcal{Y}$ occurs when $Q_{out}$ is
maximally heterogeneous and the global lower bound for $\mathcal{A}$ occurs
when $Q_{in}$ is maximally heterogeneous. In the next section we will see that
these are the lower bounds for an unclustered population. However, we have not
found a rigorous proof for general networks. In the proof of the upper bound,
we took a given $Q_{out}$ and found $Q_{in}$ that maximizes $\mathcal{Y}$ and
$\mathcal{A}$. We then held that $Q_{in}$ fixed and found $Q_{out}$ to
maximize, arriving at the upper bound. However, applying a similar technique
to the lower bound fails because given any $Q_{out}$, if we find a minimizing
$Q_{in}$, attempting to then minimize with $Q_{in}$ fixed simply returns the
original $Q_{out}$. The difficulty results from the fact that increasing
heterogeneity in $T_{out}$ restricts the amount of heterogeneity in $T_{in}$
and _vice versa_.

##  4 Bounds in unclustered networks

Most studies of infectious diseases spreading on networks have been made for
networks for which the effect of short cycles may be neglected [25]. These
investigations have generally used Molloy–Reed networks [23] (also known as
the configuration model [26]). The theory we develop here applies to these
networks, but also to more general networks which may have degree-degree
correlations, or even longer range correlations.

When we study networks with no short cycles, we are able to prove stronger
results and abandon the ordering assumption. We find that $\mathcal{Y}$
depends on the network and $Q_{out}(T_{out})$ only, while $\mathcal{A}$
depends on the network and $Q_{in}(T_{in})$ only. We can prove global upper
and (unlike in the general case) lower bounds on $\mathcal{Y}$ and
$\mathcal{A}$.

[Unclustered Assumption] Given a sequence of networks $\\{G_{n}\\}$, we assume
that $G_{n}$ has girth greater than $2n$.

This assumption means that $B_{d}(u)$ chosen from any $G_{n}$ with $n\geq d$
must be cycle free. In particular, there is no alternate path between a node
and a neighbor. It was this complication that forced the use of the ordering
assumption earlier, and since the complication no longer exists, we drop the
ordering assumption. The unclustered assumption will also allow us to use
$\psi_{in}(V)$ rather than $\phi_{in}(V,\vec{S})$. Thus we only require the
marginal probability of the set of nodes $V$ not to be infected to satisfy an
inequality, rather than the inequality be satisfied for every possible set of
susceptibilities. We must bear in mind that knowing $T_{in}$ or $T_{out}$ no
longer uniquely determines $\mathcal{I}$ or $\mathcal{S}$.

###### Lemma 4.1

Let the sequence $\\{G_{n}\\}$ satisfy the unclustered assumption with
sequential convergence of statistics. Take $P_{1}(\mathcal{I})$,
$P_{1}(\mathcal{S})$ and $T_{1}(\mathcal{I},\mathcal{S})$. Let
$\psi_{in,1}(V)$ be as in equation (4). Similarly take $P_{2}(\mathcal{I})$,
$P_{2}(\mathcal{S})$, and $T_{2}(\mathcal{I},\mathcal{S})$ with corresponding
$\psi_{in,2}(V)$. If $\psi_{in,1}(V)\leq\psi_{in,2}(V)$ then
$\mathcal{Y}_{1}\geq\mathcal{Y}_{2}$.

###### Proof 4.2

This proof is similar to that of Lemma 3.3.

Let $d\geq 0$ be given. Take $G_{n}$, $n\geq d$. Choose a node $u$ from
$G_{n}$ and partition the nodes of $G_{n}$ into $\\{u\\}$, $U_{1}$, and
$U_{2}$. To the nodes in $U_{1}$ we assign $\mathcal{I}$ from
$P_{1}(\mathcal{I})$ and to the nodes of $U_{2}$ we assign $\mathcal{I}$ from
$P_{2}(\mathcal{I})$. To each node $w$ (including $u$), we assign two
susceptibilities, $\mathcal{S}_{w,1}$ and $\mathcal{S}_{w,2}$ such that
$\mathcal{S}_{w,1}$ comes from $P_{1}(\mathcal{S})$ and $\mathcal{S}_{w,2}$
comes from $P_{2}(\mathcal{S})$.

We create a partial EPN $\mathcal{E}$ as follows. For each $v\in U_{1}$, we
assign edges $(v,w)$ using $T_{1}(\mathcal{I}_{v},\mathcal{S}_{w,1})$, and for
$v\in U_{2}$ we assign them using $T_{2}(\mathcal{I}_{v},\mathcal{S}_{w,2})$.
We do not yet assign edges from $u$ (but edges may point to $u$). Consider any
$u^{\prime}$ not in $H_{in}(d)$ which would join $H_{in}(d)$ if an edge was
added from $u$ to any $v\in V$. By assumption,
$\psi_{in,1}(V)\leq\psi_{in,2}(V)$ and so the probability is greatest if
$\mathcal{I}_{u}$ is chosen from $P_{1}(\mathcal{I})$. It follows that
$\mathcal{Y}_{1}\geq\mathcal{Y}_{2}$. This completes the proof. ∎

This proof can be modified to work on clustered networks without the ordering
assumption, so Lemma 3.3 does not require the ordering assumption. However,
the proof is more technical and provides little additional insight,
particularly because the main results following from Lemma 3.3 do require the
ordering assumption.

###### Theorem 4.3

Let the sequence $\\{G_{n}\\}$ satisfy the unclustered assumption with
sequential convergence of local statistics. Let $Q_{in}(T_{in})$ be fixed.
Then $\mathcal{A}$ is fixed.

###### Proof 4.4

We follow the technique used to prove $\mathcal{A}$ is larger for one
distribution than the other in Lemma 3.3. However, in following that proof,
the lack of clustering means $|V|=1$. Since for any distribution
$\psi(V)=1-\left\langle T\right\rangle$ when $|V|=1$, all distributions must
give the same $\mathcal{A}$, and the proof is finished. ∎

###### Theorem 4.5

If the assumptions of Theorem 4.3 hold except that $Q_{out}$ is fixed rather
than $Q_{in}$, then $\mathcal{Y}$ is fixed.

###### Proof 4.6

This follows immediately from Lemma 3.1 and Theorem 4.3. ∎

###### Theorem 4.7

Let $Q_{in}$ be given. Assume that $\\{G_{n}\\}$ satisfies the unclustered
assumption with sequential convergence of statistics. $\mathcal{Y}$ is
maximized when $T(\mathcal{I},\mathcal{S})=T_{in}(\mathcal{S})$.

Although this result is analogous to Theorem 3.5, the proof is fundamentally
altered because we no longer have the ordering assumption.

###### Proof 4.8

We first note that if $T(\mathcal{I},\mathcal{S})=T_{in}(\mathcal{S})$, then
$T_{out}=\left\langle T\right\rangle$ for all nodes.

Now consider an arbitrary function $T(\mathcal{I},\mathcal{S})$ with
$P(\mathcal{I})$ and $P(\mathcal{S})$ to satisfy $Q_{in}(T_{in})$. The
function $(1-T_{out})^{|V|}$ in equation (4) is convex, so by Jensen’s
inequality $\psi_{in}$ is minimized by $T_{out}=\left\langle T\right\rangle$.
Lemma 4.1 completes the proof. ∎

###### Theorem 4.9

Let $Q_{in}$ be given. Assume $\\{G_{n}\\}$ satisfies the unclustered
assumption with sequential convergence of statistics. $\mathcal{Y}$ is
minimized when $\mathcal{I}$ is chosen uniformly from $[0,1]$ and

$T(\mathcal{I},\mathcal{S})=\begin{cases}0&\mathcal{I}>T_{in}(\mathcal{S})\\\
1&\mathcal{I}<T_{in}(\mathcal{S})\,.\end{cases}$

###### Proof 4.10

Following the proof of Theorem 3.7, we may show that $\phi_{in}$ is maximized
(subject to $Q_{in}$) exactly when these assumptions hold. Thus from equation
(3) $\psi_{in}$ is also maximized when these assumptions hold. Lemma 4.1
completes the proof. ∎

###### Theorem 4.11

Let $Q_{out}$ be given. Assume $\\{G_{n}\\}$ satisfies the unclustered
assumption with sequential convergence of statistics.

  * •

$\mathcal{A}$ is maximized when
$T(\mathcal{I},\mathcal{S})=T_{out}(\mathcal{I})$.

  * •

$\mathcal{A}$ is minimized when $\mathcal{S}$ is chosen uniformly from $[0,1]$
and

$T(\mathcal{I},\mathcal{S})=\begin{cases}0&\mathcal{S}>T_{out}(\mathcal{I})\\\
1&\mathcal{S}<T_{out}(\mathcal{I})\,.\end{cases}$

###### Proof 4.12

This follows from Theorems 4.7 and 4.9 with Lemma 3.1. ∎

Before proving our final result, we introduce a lemma.

###### Lemma 4.13

Let $f(x)$ be a convex function on $[0,1]$ and $\rho(x)$ be a probability
density function on $[0,1]$, with expected value $\rho_{0}$. Then

$\int f(x)\rho(x)dx\leq(1-\rho_{0})f(0)+\rho_{0}f(1)\,.$

###### Proof 4.14

The definition of convexity gives

$f(x)\leq(1-x)f(0)+xf(1)\,.$

Thus

$\int
f(x)\rho(x)dx\leq\int[(1-x)f(0)\rho(x)+xf(1)\rho(x)]dx\leq(1-\rho_{0})f(0)+\rho_{0}f(1)\,.$

∎

###### Theorem 4.15

Let $\\{G_{n}\\}$ be a sequence of networks satisfying the unclustered
assumption with sequential convergence of statistics. Assume that
$\left\langle T\right\rangle$ is given:

  * •

The global upper bound for both $\mathcal{Y}$ and $\mathcal{A}$ occurs when
$T_{uv}=\left\langle T\right\rangle$ for all pairs of neighbors.

  * •

The global lower bound for $\mathcal{Y}$ occurs when
$Q_{out}(T_{out})=\left\langle T\right\rangle\delta(T_{out}-1)+(1-\left\langle
T\right\rangle)\delta(T_{out})$.

  * •

The global lower bound for $\mathcal{A}$ occurs when
$Q_{in}(T_{in})=\left\langle T\right\rangle\delta(T_{in}-1)+(1-\left\langle
T\right\rangle)\delta(T_{in})$.

###### Proof 4.16

The proof of the upper bound is identical to that of Theorem 3.11.

We prove the lower bound for $\mathcal{Y}$. The lower bound for $\mathcal{A}$
follows from Lemma 3.1.

We have $\psi_{in}(V)=\int(1-T_{out})^{|V|}Q_{out}(T_{out})dT_{out}$. We now
seek to find $Q_{out}$ which maximizes $\psi_{in}$ in order to apply Lemma
4.1.

Since $(1-T_{out})^{|V|}$ is a convex function, we may apply Lemma 4.13 with
$Q_{out}$ playing the role of $\rho$. The maximum occurs when
$Q_{out}(T_{out})=\left\langle T\right\rangle\delta(T_{out}-1)+(1-\left\langle
T\right\rangle)\delta(T_{out})$ and so Lemma 4.1 finishes the proof. ∎

Although the upper bound for both $\mathcal{Y}$ and $\mathcal{A}$ occurs when
$T_{uv}=\left\langle T\right\rangle$ for all pairs, our earlier results show
that for unclustered networks $\mathcal{Y}$ depends only on $Q_{out}(T_{out})$
and the network, and so as long as $T_{out}(u)=\left\langle T\right\rangle$
for all nodes $u$, we achieve the upper bound on $\mathcal{Y}$ (but not on
$\mathcal{A}$). Symmetrically, if $T_{in}(v)=\left\langle T\right\rangle$ for
all nodes $v$, we achieve the upper bound on $\mathcal{A}$.

Note that the lower bound for $\mathcal{A}$ requires that
$T_{out}(u)=\left\langle T\right\rangle$ for all $u$, and so the population is
homogeneously infectious. It follows from Theorem 4.9 that $\mathcal{Y}$ is
then maximal. Similarly the lower bound for $\mathcal{Y}$ requires that
$\mathcal{A}$ be maximal.

###  4.1 Discussion

The results of this section generalize those of [21] which considered the
special case of Molloy–Reed networks. These results prove that the same
scenarios give upper and lower bounds in unclustered networks with a wide
range of correlations including assortative or disassortative mixing (high
degree nodes preferentially joining with high or low degree nodes
respectively), or longer range correlations. Although we proved these under
the assumption that no short cycles exist, the results remain useful in
networks with either few short cycles, or for situations in which the
transmissibility is low enough that the short cycles are only rarely followed.

Because of the lack of short cycles, the ordering assumption is not needed.
This means that our results apply to a much wider class of disease
transmission mechanisms, but at the cost of restricting the network. Again we
find that which conditions give the upper or lower bound is network-
independent. The amount of variation there is between these bounds, however,
is network-dependent.

The main distinction from clustered networks is that $\mathcal{Y}$ depends
only on the network structure and $Q_{out}(T_{out})$. That is, $\mathcal{Y}$
is independent of $Q_{in}(T_{in})$. Similarly $\mathcal{A}$ depends only on
the structure and $Q_{in}(T_{in})$. We note that unless the effect of
clustering is very large, the dependence of $\mathcal{Y}$ on in-
transmissibility and $\mathcal{A}$ on out-transmissibility will be weak.
Curiously the global lower bound for $\mathcal{A}$ found in Theorem 4.15
requires that $Q_{out}(T_{out})=\delta(T_{out}-\left\langle T\right\rangle)$,
and so the population is homogeneously susceptible. It follows from Theorem
4.9 that $\mathcal{Y}$ is then maximal. Similarly the lower bound for
$\mathcal{Y}$ requires that $\mathcal{A}$ be maximal. This has important
implications for policy design because strategies to reduce $T$ tend to have a
heterogeneous impact on either $\mathcal{S}$ or $\mathcal{I}$.

##  5 Conclusions

We have extended earlier work on the effect of heterogeneity in infectiousness
on the spread of epidemics through networks. Our extensions allow for
heterogeneity in susceptibility as well. Many of the results are similar. In
general we find that the size and probability of epidemics are reduced if the
population is more heterogeneous. Unfortunately, increasing heterogeneity in
susceptibility restricts the level of heterogeneity possible in
infectiousness. In the extreme case where susceptibility is maximally
heterogeneous, infectiousness must be homogeneous. Perhaps surprisingly, we
have found that the distributions leading to upper and lower bounds on
$\mathcal{Y}$ and $\mathcal{A}$ are network-independent.

Early in an outbreak, it is likely that we may gain some information about
$Q_{out}(T_{out})$. For example, in the early stages of the SARS epidemic, it
was known that a number of people were highly infectious, while the rest were
only mildly infectious and so $Q_{out}(T_{out})$ was highly heterogeneous.
However, there was little information on $Q_{in}$. Once given the distribution
of $Q_{out}$, the results here show which distributions of $Q_{in}$ give the
largest or smallest $\mathcal{Y}$ and $\mathcal{A}$. Our results further
suggest that the distribution of infectiousness found for SARS is consistent
with a low epidemic probability. It is difficult to extrapolate from
observations what the sizes would have been without the interventions put into
place, but the fact that a number of isolated cases occurred throughout the
world without sparking local epidemics suggest that the probability of an
epidemic from each introduction was low, consistent with our predictions.

Our results further suggest that in order to prevent an epidemic, it is best
to take measures that will have a heterogeneous impact on infectiousness, but
in order to affect the size of an epidemic, it is best to take measures that
will have a heterogeneous impact on susceptibility. In terms of actual
interventions, we compare two strategies aimed at controlling a disease which
is initially spreading with homogeneous $T$: in the first we devote resources
to vaccinating half of the population, while in the second we devote them to
identifying and removing half of the infected population. Both strategies
reduce $\left\langle T\right\rangle$ by a factor of $2$. In the first, the
susceptibility is highly heterogeneous, but the probability an infected node
infects a randomly chosen neighbor has simply gone down by a factor of $2$,
and so it remains homogeneous. Assuming that the unclustered approximation is
valid, this maximizes the impact on size, but the impact on probability is
minimized. In contrast, the second strategy maximizes the impact on
probability, but minimizes the impact on size.

## Acknowledgments

This work was supported in part by the Division of Mathematical Modeling at
the UBC CDC and by DOE at LANL under Contract DE-AC52-06NA25396 and the DOE
Office of ASCR program in Applied Mathematical Sciences.

## References

  * [1] Abbey, H. (1952).  An examination of the Reed-Frost theory of epidemics.  Human Biology 24, 201–233.
  * [2] Anderson, R. M. and May, R. M. (1991).  Infectious Diseases of Humans.  Oxford University Press, Oxford.
  * [3] Andersson, H. (1999).  Epidemic models and social networks.  Math. Scientist 24, 128–147.
  * [4] Ball, F. (1985).  Deterministic and stochastic epidemics with several kinds of susceptibles.  Advances in Applied Probability 17, 1–22.
  * [5] Ball, F. and O’Neill, P. (1999).  The distribution of general final state random variables for stochastic epidemic models.  Journal of Applied Probability 36, 473–491.
  * [6] Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A. and Wiener, J. (2000).  Graph structure in the web.  Computer Networks 33, 309–320.
  * [7] Del Valle, S. Y., Hyman, J. M., Hethcote, H. W. and Eubank, S. G. (2007).  Mixing patterns between age groups in social networks.  Social Networks 29, 539–554.
  * [8] Eubank, S., Guclu, H., Kumar, V. S. A., Marathe, M. V., Srinivasan, A., Toroczkai, Z. and Wang, N. (2004).  Modelling disease outbreaks in realistic urban social networks.  Nature 429, 180–184.
  * [9] Hastings, M. B. (2006).  Systematic series expansions for processes on networks.  Physical Review Letters 96, 148701\.
  * [10] Keeling, M. J. (2005).  The implications of network structure for epidemic dynamics.  Theoretical Population Biolology 67, 1–8.
  * [11] Keeling, M. J. and Eames, K. T. D. (2005).  Networks and epidemic models.  Journal of the Royal Society Interface 2, 295–307.
  * [12] Kenah, E. and Robins, J. M. (2007).  Network-based analysis of stochastic SIR epidemic models with random and proportionate mixing.  Journal of Theoretical Biology.
  * [13] Kenah, E. and Robins, J. M. (2007).  Second look at the spread of epidemics on networks.  Physical Review E 76, 36113\.
  * [14] Kermack, W. O. and McKendrick, A. G. (1927).  A contribution to the mathematical theory of epidemics.  Royal Society of London Proceedings Series A 115, 700–721.
  * [15] Kingman, J. F. C. (1978).  Uses of exchangeability.  The Annals of Probability 6, 183–197.
  * [16] Kuulasmaa, K. (1982).  The spatial general epidemic and locally dependent random graphs.  Journal of Applied Probability 19, 745–758.
  * [17] Kuulasmaa, K. and Zachary, S. (1984).  On spatial general epidemics and bond percolation processes.  Journal of Applied Probability 21, 911–914.
  * [18] Madar, N., Kalisky, T., Cohen, R., ben Avraham, D. and Havlin, S. (2004).  Immunization and epidemic dynamics in complex networks.  The European Physical Journal B 38, 269–276.
  * [19] Meyers, L. A. (2007).  Contact network epidemiology: Bond percolation applied to infectious disease prediction and control.  Bulletin of the American Mathematical Society 44, 63–86.
  * [20] Meyers, L. A., Newman, M. and Pourbohloul, B. (2006).  Predicting epidemics on directed contact networks.  Journal of Theoretical Biology 240, 400–418.
  * [21] Miller, J. C. (2007).  Epidemic size and probability in populations with heterogeneous infectivity and susceptibility.  Physical Review E 76, 010101\.
  * [22] Mollison, D. (1977).  Spatial contact models for ecological and epidemic spread.  Journal of the Royal Statistical Society. Series B (Methodological) 39, 283–326.
  * [23] Molloy, M. and Reed, B. (1995).  A critical point for random graphs with a given degree sequence.  Random structures & algorithms 6, 161–179.
  * [24] Neal, P. (2007).  Copuling of two SIR epidemic models with variable susceptibilities and infectivities.  Journal of Applied Probability 44, 41–57.
  * [25] Newman, M. E. J. (2002).  Spread of epidemic disease on networks.  Physical Review E 66, 16128\.
  * [26] Newman, M. E. J. (2003).  The structure and function of complex networks.  SIAM Review 45, 167–256.
  * [27] Pastor-Satorras, R. and Vespignani, A. (2001).  Epidemic spreading in scale-free networks.  Physical Review Letters 86, 3200–3203.
  * [28] Serrano, M. and Boguñá, M. (2006).  Percolation and epidemic thresholds in clustered networks.  Physical Review Letters 97, 088701\.
  * [29] Trapman, P. (2007).  On analytical approaches to epidemics on networks.  Theoretical Population Biology 71, 160–173.
  * [30] van den Berg, J., Grimmett, G. R. and Schinazi, R. B. (1998).  Dependent random graphs and spatial epidemics.  The Annals of Applied Probability 8, 317–336.