|
3.2- Random GraphIt is difficult to think of real ecosystems that have topologies resembling the fully-connected-graph described in the previous sub-section. In most realistic systems, a cell's neighbors constitute a very small fraction of the total number of cells. This leads very naturally to the consideration of various types of random-graph topologies, in which the average number of neighbors is an adjustable parameter.
Here I consider a particular type of random graph which is generated as follows.
Suppose that the desired average number of neighbors per node (also referred to
as the degree) is d. Then, for
each node i in the system, the number of neighbors, d(i), is chosen according
to a Poisson distribution with mean d. Finally, d(i) other nodes are
selectly randomly to be neighbors which are reachable from i
Exact analysis of the behavior of Model 1 on random graphs appears to be very
difficult, if not impossible. In the homogeneous topology, no matter how
many nodes are infected with A, each sees exactly the same environment. In
other words, each infected node has the same number of uninfected neighbors, and
each uninfected node can be infected by the same number of infected neighbors.
This permits the full dynamics of a system with N nodes to be expressed in
terms of the number of infected nodes --
a quantity which can only take on N+1 different values. By contrast, each node
in a random graph sees a different environment. An exact analysis would require
us to keep track of exactly which nodes are infected and which are not --
Along with the deterministic, homogeneous solution discussed in the previous sub-section,
Figure 1 illustrates typical simulation runs on
randomly-generated graphs of average degree d=8.0 and d=2.0. In order to facilitate
comparison with the deterministic solution, which is only valid in the large-N limit, the
graphs contained 10,000 nodes each. The birth and
death rates were taken to be the same as in the homogeneous case (i.e. the birth
rate along each link is
The similarity in shape between the d=8 and d=9999 curves in Figure 1
is striking. The initial growth is quite similar in form, and the equilibrium fractional
population is just slightly less for the d=8 random graph. The only significant difference
is a delay in when the population explosion occurs for the d=8 simulation run.
This apparent difference is illusory. By running several more
simulations on the same graph (or different random graphs with d=8),
one can obtain a fairly wide spread
in ``ignition'' times -- some occurring before that of the homogeneous curve, and some
occurring later. However, beyond fairly minor statistical
fluctuations, the basic shape is unaltered.
A more exact statistical analysis of the homogeneous topology reveals that
the wide variance in ignition times is to be expected for d=9999 as well. Thus the shift
between the d=9999 and d=8 curves in Figure 1 is merely a consequence
of trying to compare an expected value with a single sample of a distribution with a large
variance.
An average over 2500 simulations gives a survival probability of 0.77 and a fractional
population equilibrium of approximately 0.77 for d=8, as compared to 0.80 for both of
these quantities for d=9999. Further simulation shows that, for these values of the
birth and death rates, the behavior of Model 1 on random graphs
with
This recent finding [1] is significant because it establishes the validity of the homogeneous mixing assumption over a much broader range than might have been expected. Thus diseases for which a typical individual has many infectious contacts (which may be true for influenza, for example) are well-described by the homogeneous mixing approximation. However, when the average degree d is sufficiently small, the equilibrium population is suppressed substantially, as illustrated by the d=2 simulation run in Figure 1. The initial growth of the population is noticeably slower. (Unfortunately, I have not yet established the functional form of this growth; it could be exponential with an exponent of approximately half the homogeneous value.) An average over 2500 simulations gives a survival probability of 0.58 and a fractional population equilibrium of approximately 0.58 for random graphs with d=2. It seems to be more than mere coincidence that, for all three cases, the survival probability is equal to the fractional equilibrium population. This equivalence can be proven in the homogeneous case, but it is surprising that it seems to generalize to random graphs of arbitrary degree. Thus, sparse connectivity not only slows the spread of A, but limits it in the sense of decreasing the survival probability and reducing the equilibrium population even when A does survive. Sparse connectivity is probably typical of sexually transmitted diseases, at least in many communities. The much more detailed results reported in ref. [1] are perhaps the first to quantify the dangers of promiscuity from a global perspective.
Figure 1: The effect of various topologies on the population dynamics of species A: a) homogeneous mixing model, b) 10000-node random graph with d=8.0, and c) 10000-node random graph with d=2.0. The birth and death rates are  and
 in all cases. The homogeneous
mixing curve is given by Eq. 2, in which the
initial fractional population of A is taken to be
 .
The random graph curves were obtained from typical simulation runs
in which initially just one cell (out of 10000 total) was infected with A.
|
possible states in all. This is barely feasible (numerically) if N does not
exceed 15 or 20. Unfortunately, even if we succeed in analyzing one particular
randomly-generated graph, our goal is to understand the behavior of Model 1 on
the class of graphs generated by the algorithm described in the previous
paragraph. This requires us to take a weighted average over
graphs,
with a weighting function that depends on d and the number of connections in
each graph. I have done this calculation for N=3 and N=4, and can imagine
that some clever trickery might help push this limit to N=5 or
6. However, the results are only useful in an academic sense, and fail to bring
us anywhere close to the interesting large-N limit. Although I have
experimented with some approximations, it is difficult to assess their validity.
The only way to obtain believable results is to simulate the model.
). To match the homogeneous initial
condition of a(0)=0.0001, the simulations were started with just one of the
10,000 nodes being infected with A. Thus all of the parameters of the
population model itself are identical; the three curves are distinguished solely
by their topology. Taking a slightly odd point of view, one can consider the
homogeneous curve to represent a 10,000-node random graph with d=9999, which
fits it neatly into the same framework as the two random-graph simulations.
is substantially similar to that observed for the homogeneous topology
in every respect. If the birth rate is decreased to bring the system closer to the
epidemic threshold, this lower limit on d is increased.