3.3- Local TopologiesNow suppose that the cells are arranged in a two-dimensional square lattice in which each cell is connected only to its eight nearest neighbors. How does this influence the population dynamics of the model? Figure 2 compares a typical simulation run on a 100-by-100 square lattice to the previously-discussed homogeneous behavior. (Note the change in time scales between Figs. 1 and 2.) Again, the birth and death rates are 5.0 and 1.0, respectively, and initially just one of the 10,000 nodes is infected. In contrast to the rapid, exponential growth of populations in homogeneous systems, the population growth on the square lattice is much slower, and quadratic in form. Eventually, the population saturates at the same equilibrium as in the homogeneous case. Likewise, the survival probability is essentially the same as for the homogeneous topology, as I have established by observing many simulation runs.
Figure 2: The effect of various local topologies on the population dynamics of species A: a) homogeneous mixing model (for comparison), b) 100-by-100 square lattice (wrapped around in both dimensions to form a torus), c) 6561-node hierarchically-clustered random graph with d=4. The birth and death rates are  and
 in all cases.
In both simulation runs, just one cell was infected with A at t=0. Note that the
time scale is 5 times that of Fig. 1.
Figure 3 illustrates why the initial growth of the population is quadratic in this topology. Starting from a single infected cell, A tends to spread outwards in an expanding, roughly circular pattern, with a radius that grows linearly in time. Within this radius, the system is essentially at the homogeneous equilibrium. Thus the fractional population is proportional to the area of the infected region, which grows quadratically. See ref [1] for a further description of this effect, and ref [16] for a mathematical analysis.
Figure 3: State of simulated epidemic in Figure 2b at time t=10. Each node can infect the 8 neighbors lying within a 3-by-3 square centered on itself. Black and white squares represent infected and uninfected individuals, respectively. The boundary of the expanding infected region is roughly circular (despite the fact that the infection neighborhood is square) and fairly sharp.
It is relatively easy to do a deterministic analysis of the population dynamics
of this model in D-dimensional spaces in which the cells are merged
into a continuous medium rather than being distinct from one
another [1]. The solution
Intuitively, the slower growth rate can be attributed to the fact that A wastes much of its replication effort in areas in which it is already dense, failing to take advantage of the vast unoccupied territory lying beyond the leading edge of growth. In a sense, this is obvious. It might also seem obvious that this ``locality'' effect can only hold in spatial topologies. However, further reflection on the underlying reasons for the qualitatively slow population growth found in spatial topologies leads to a generalized concept of local topologies, of which spatial topologies are just a subset.
The basic reason why A keeps trying to infect already-infected cells in
spatial topologies is that there is a significant amount of overlap between
a node's neighbors and its neighbors' neighbors. Suppose that a single node i
in the square lattice is infected with A. This one node has 8 infectible neighbors (d=8).
Now suppose that i manages to infect all 8 of these neighbors. Then there are 9 infected
nodes, but the degree of overlap between i's neighbors and its neighbors' neighbors is so
large that they have among them just 16 infectible nodes (the ones located on the
periphery of a 5-by-5 square centered on i). Thus nine times as many nodes
have only twice as many nodes to infect. Now consider a random graph with d=8. Again,
node i would be able to infect 8 neighbors. However, the next step in the chain
of infection is quite different. Since in a
random graph there is no correlation between neighbors and neighbor's neighbors, the
chances are extremely high that none of the 9 infected nodes have any overlap among them.
Thus the number of infectible nodes at this point is
If we loosely define locality as the presence of significant overlap between a typical node's neighborhood and the neighborhoods of its neighbors, we can construct non-spatial local topologies. The hierarchically-clustered random graph is a particularly interesting example because it captures some of the essence of both social and computer networks. Consider computer networks, for example. We can imagine that users within one research group exchange software frequently among themselves, are somewhat less likely to do so with other members of their department, and are even less likely to do so with users in other companies, universities, or countries. Thus it is not too far-fetched to suppose that the typical environment inhabited by a computer virus might consist of nested clusters, with some amount of cross-linkage among them. On the basis of the above discussion we would expect this to slow the spread of computer viruses profoundly.
Here is a recipe for generating a hierarchically-clustered random graph. Imagine
a virtual tree in which the root has b branches, each of which has b branches, and so on
for L levels. There are
A simulation run on a 6561-node (b=3, L=8) hierarchically-clustered graph
is compared with the square-lattice simulation and the homogeneous solution in
Figure 2. Although the functional form of the population
growth has not yet been determined, it appears to be strongly sub-exponential, as we would
expect. By varying the localization parameter r, one can increase or decrease the
growth rate at will. In the limit
|
to the resulting
partial differential equation exhibits behavior similar to
that found in the discrete case. Thus, in both continuous and
discrete d-dimensional spaces,
the rate of population growth is polynomial (
) rather
than exponential.
. In general,
the number of infected nodes and the number of infectible nodes remain proportional to one
another until the population starts to saturate.
leaves at the bottom level of this virtual tree. These are
our nodes. For each node i, generate the list of nodes which can be infected by it as
follows: For each node
, let j be infectible by i with probability
,
where
is the number of levels one must go up in the virtual tree before
a common ancestor of i and j can be found.
Typically, one would choose
, where the
parameter r can be used to control the amount of localization.
, the graph consists of isolated
nodes or node clusters; as
, the topology approaches that of the
standard random graph. In this particular example, the equilibrium
population on the clustered graph was noticeably less than the homogeneous value
because it was somewhat sparsely connected (d was only 4).