Next	4- Spatial Model
Previous	2.4- Weak Links
Up	Directed-Graph Epidemiological Models of Computer Viruses

3- Hierarchical Model

Motivated by a desire to study the effect of infrequent program sharing with many other individuals, we augmented the random graph model by introducing weak links in section 2.4. However, the classification of links into just two types -- strong and weak -- is a bit crude. It is probably more realistic to assume that an individual exchanges programs at a very high rate with very few other individuals, at a lower rate with a larger class of other individuals, at an even lower rate with an even larger class of others, etc. This leads naturally to the hierarchical model illustrated in Figure 7.

  
Figure 7: Binary hierarchical graph with 3 levels. Infection rates between nodes separated by a given number of levels are listed to the left of the tree. Infected and uninfected nodes are represented by black and unfilled circles, respectively. Initially, only node 2 was infected, but it quickly infected node 1. For a while, nodes 1 and 2 attempted to infect one another (to no effect, since they were already infected). Eventually, node 1 attempted successfully to infect node 3. Node 3 quickly infected node 4, but was cured soon afterward. Node 3 will probably be infected soon by node 4, but nodes 5, 6, 7, and 8 will probably not be infected for a relatively long time.

The hierarchical model has an unexpected side benefit. Note that all nodes with a given subtree communicate with one another more frequently than with any node in any other subtree. Thus, the hierarchy of rates automatically enforces a hierarchy of cliques . In the computer community, cliques of users certainly exist, although not in such an extreme form as in this model. For example, users within a department may share software frequently among themselves, less frequently with users in other departments of the same company or university, and still less frequently with users in other cities or countries. The random graph model and others derived from it are incapable of accounting for such correlations because of the way in which they are constructed -- the connections are chosen randomly and independently.

For simplicity, we assume that the frequency of contact between two nodes decreases geometrically with the distance between them (the number of levels one must go up in the tree to reach a common ancestor), while the size of the class of neighbors at a given distance grows geometrically with . More explicitly, assume that the hierarchy consists of a binary tree with L levels. Then there are nodes. Suppose that the infection rate between nodes separated by a distance is given by . The number of nodes at distance is simply . Therefore, the total infection rate from one node is

 

As before, we assume that the cure rate for each node is .

By keeping and fixed and varying the localization parameter r, we can explore a wide range of situations. When r=0, the network effectively consists of isolated pairs of nodes with infection rate . By setting r=1, we obtain the homogeneous limit, in which the infection rate between all pairs of nodes is equal to . Thus, the parameter r ought to be similar in its effect to the connectivity .

We have investigated the dependence of the extinction probability upon the localization parameter by means of simulation. The results are summarized in Fig. 8. As expected, the extinction probability exhibits threshold behavior qualitatively similar to that of Fig. 5a. For strongly localized graphs, extinction of the infected population is virtually guaranteed, even though the infection rates are well above the classical threshold (by a factor of five for and a factor of two for ). As , the extinction probability approaches the homogeneous limit, as expected. The upward shift in position and the increase in width of the transition region as is increased are both consistent with what we have observed for larger values of as the connectivity is varied in the random graph model.

  
Figure 8: Extinction probability vs. localization parameter r for SIS model on hierarchical graph of 128 nodes. For sufficiently localized interactions (small r), rapid extinction of the virus is virtually assured, even when the infection rate is well above the classical epidemic threshold (by a factor of 5 for and a factor of 2 for ). The relatively small width of the transition region is reminiscent of Fig. 5a.

Note that we have not presented the corresponding curves for the average number of infected individuals in equilibrium. The reason is quite interesting. When r is in the transition region, the individual simulation runs often fail to attain a well-defined equilibrium. A typical example, shown in Fig. 9, displays a character much more mercurial than that of a typical simulation in the random graph model (Fig. 4). In Fig. 4, a well-defined equilibrium level is reached by t=10. However, in Fig. 9, the number of infected individuals I varies over a large range in a very irregular fashion even after many hundreds of time units. The range within which I varies lies far below the homogeneous limit of , as is expected since r is in the transition region. Inspection of a number of individual simulation runs strongly suggests that the metastable phase, if it exists, is much shorter in duration than its random graph counterpart. This is reasonable because rapid extinction is consistent with the small number of infected individuals and the large magnitude of the fluctuations in that quantity.

  

Figure 9: Number of infections I vs. time for typical simulation run on 128-node hierarchical graph with localization parameter r=0.1. The infection and cure rates have their usual values of

and

. The aimless, irregular drift in the number of infected individuals at a value much lower than the homogeneous equilibrium (I=102.4) is characteristic of simulation runs with localization parameter lying within the transition region (see

curve in Fig. 8).

We have also performed simulations on larger hierarchical graphs with as many as 8192 nodes. Interestingly, in the transition region the average number of infections does not increase with the size of the graph, and the magnitude and irregular character of the fluctuations is unaltered. This contrasts strongly with the behavior of random graphs, for which the number of infected individuals scales linearly with N and the relative size of the fluctuations decreases as . In some simulation runs, one can identify a series of plateaus in I(t), separated by relatively rapid growth spurts. The growth spurts occur when a node ``gets lucky'' and infects a distant node, which then spreads the infection throughout a previously untouched region of the graph. When r is sufficiently far above the transition region, I(t) continues to grow until it saturates eventually at the homogeneous equilibrium. The rate at which it does so is much slower than for a random graph and is extremely sensitive to r (see Fig. 12). The functional form of the growth rate and its dependence upon r is not yet known.

Next	4- Spatial Model
Previous	2.4- Weak Links
Up	Directed-Graph Epidemiological Models of Computer Viruses

Back To Index