JAIST Repository
https://dspace.jaist.ac.jp/

Title

Oscillatory epidemic prevalence in growing scale‑free networks

Author(s)Hayashi Yukio; Minoura Masato; Matsukubo Jun

Citation

Physical Review E, 69(1): 016112‑1‑016112‑8

Issue Date

2004‑01

Type

Journal Article

Text version

publisher

URL

http://hdl.handle.net/10119/3412

RightsYukio Hayashi, Masato Minoura, and Jun Matsukubo,
Physical Review E, 69(1), 016112, 2004.
"Copyright 2004 by the American PhysicalSociety."
http://scitation.aip.org/getabs/servlet/GetabsSer
vlet?prog=normal&id=PLEEE800006900000101611200000
1&idtype=cvips&gifs=Yes

Description

Japan Advanced Institute of Science and Technology

PHYSICAL REVIEW E 69, 016112 共2004兲

Oscillatory epidemic prevalence in growing scale-free networks
Yukio Hayashi, Masato Minoura, and Jun Matsukubo
Japan Advanced Institute of Science and Technology, Ishikawa 923-1292, Japan
共Received 5 February 2003; revised manuscript received 6 August 2003; published 28 January 2004兲
We study the persistent epidemic prevalence with oscillatory behavior and the extinction of computer viruses
via e-mails on a contact relational network growing with new users, for which scale-free structure is estimatedfrom real data. Typical oscillatory phenomenon is simulated in a stochastic model for the execution anddetection of viruses. The conditions of extinction by random and targeted immunizations for hubs are derived
through bifurcation analysis for simpler deterministic models by using a mean-field approximation without theconnectivity correlations. We can qualitatively understand the mechanisms of the spread in linearly growing
scale-free networks.
DOI: 10.1103/PhysRevE.69.016112

PACS number共s兲: 05.65.⫹b, 87.23.Ge, 05.40.⫺a, 89.20.Hh

I. INTRODUCTION

In spite of different interactions between social, technological, or biological elements, many complex networks inreal worlds have a common structure. It is based on a universal self-organized mechanism: network growth and preferential attachment of connections 关1,2兴. The structure iscalled scale-free 共SF兲 network, which exhibits a power-law
degree distribution P(k)⬃k ⫺ ␥ , 2⬍ ␥ ⬍3, for the probabilityof vertex with k connections. The topology deviates from theconventional homogeneous regular lattices and randomgraphs. Many researchers are attracted to a new paradigm of
the heterogeneous SF networks in this active and fruitfularea.
The structure of SF networks also has a strong impact on
the dynamics of epidemic models for computer viruses, HIV,and others. Recently, it has been shown 关3兴 that asusceptible-infected-susceptible 共SIS兲 model on SF networks
has no epidemic threshold; infections can be proliferated,
whatever small infection rate they have. This result disproves
the threshold theory in epidemiology 关4兴. The heterogeneous
structure is also crucial for spreading the viruses on theanalysis of susceptible-infected-recovered 共SIR兲 models
关5,6兴. In contrast to the absence of epidemic threshold, an
immunization strategy has been theoretically presented in a
SIS model on SF networks 关7,8兴. The targeted immunization
for the most highly connected vertices such as hubs applies
the property of the extreme disconnections by attacks against
the hubs 关9兴 to a prevention against the spread of infections.
In this paper, we investigate the dynamic properties for
spreading of computer viruses on the SF networks estimatedfrom real data of e-mail communication 关10兴. As a new property in both simulation and theoretical analysis, we suggestthat a growing network with new e-mail users causes theoscillatory prevalence recovered from a temporary silence ofalmost complete extinction. We refer to the typical oscillatory phenomenon in observations 关11,12兴 as recoverable
prevalence, which is not explained by the above statisticalanalyses at steady states or mean values 共in the fixed size orN→⬁). We first consider a realistic epidemic model on thegrowing SF network in simulations with the probabilistic
execution and detection of viruses. Then, for understanding
the mechanisms of such recoverable prevalence and extinc1063-651X/2004/69共1兲/016112共8兲/$22.50

tion, we analyze simpler growing models in deterministic
equations. By using a mean-field approximation without theconnectivity correlations, we derive bifurcation conditions
from the extinction to the recoverable prevalence 共or the opposite兲, which is related to the growth, infection, and immune rates. Moreover, we verify the effectiveness of the targeted immunization for hubs by antiviruses even in thegrowing system.
II. E-MAIL NETWORK
A. The state transition for infection

We consider a network of contact relations whose vertices
共nodes兲 and edges 共links兲 correspond to computers and thecommunication via e-mails between users, respectively. Eachvertex has two degrees, an in-degree for a received mail,which is the number of edges that point into the vertex, andan out-degree for a sent mail, which is the number pointing
out. In the mailing processes, the state at each computer i⫽1, . . . ,N is changed from the susceptible, hidden, infectious, and to the recovered by the removal of viruses andinstallation of antiviruses. We make a realistic model in stochastic state transitions with probabilities of the execution
and the detection of viruses. Figure 1 shows the state transitions, where ␭ and ␦ denote the execution rate from thehidden to the infectious state and the detection rate from thespecial subjects or doubtful attachment files. The probabilityof at least one detection from the n i viruses on the computeris 1⫺(1⫺ ␦ ) n i , and the probability of at least one execution

69 016112-1

FIG. 1. S-H-I-R state transition diagram.
©2004 The American Physical Society

PHYSICAL REVIEW E 69, 016112 共2004兲

HAYASHI, MINOURA, AND MATSUKUBO

FIG. 2. Power-law degree distributions with the exponents
␥ out ⫽2.5 and ␥ in ⫽1.9 estimatedfor questionnaires of 共a兲 sent
mails and 共b兲 received mails between users including the internal
共measured users兲 and the external
共other people兲 关10兴. The frequency
at degree k is counted in the interval between 关 k,k⫹10兴 , except forthe outer of more than 100 degreeat k⫽200. Similar distributions
with 共c兲 ␥ out ⫽2.07 and 共d兲 ␥ in
⫽1.85 are estimated for the server
log files of e-mails 关13兴 including
the internal and the external.

is 1⫺(1⫺␭) n i . We assume the infected mail not sent again
for the same communication partner 共sent it at only one time兲
to be difficult for detection. Thus, n i is at most the number of
in-degree at each vertex. In the stochastic 共susceptible–
hidden infected–infections-recovered兲 SHIR model, the final
state is the one recovered or immuned by antiviruses, if at
least one infected mail is received.
B. The scale-free structure

We show the e-mail network structure based on real datameasured by questionnaires for 2555 users in a part of WorldInternet Project 2000 关10兴. The distributions of both sent andreceived mails follow a power law in Fig. 2共a兲, the exponents
are estimated as ␥ out ⫽2.5, ␥ in ⫽1.9, and the average num-

ber of mails per day k̄⫽5 –20. These values are close to␥ out ⫽2.07 and ␥ in ⫽1.85 estimated in the same range 1⬍k⭐100 for the server log files of e-mails 关13兴 ( ␥ out ⫽2.03⫾0.12 and ␥ in ⫽1.49⫾0.12 in Ref. 关14兴兲. There exists aslight difference between these estimated values which depend on the sample, measuring, and numerical precision. In
addition, we have found that the cumulative histograms ofless than degree k have similar shapes in a larger network of
e-mail address books 关15兴. However, in the estimation forboth data 关10,13兴 by a stretched exponential function as inRef. 关15兴, the exponential parts almost vanish. Thus, the cumulative histograms are approximated by a power law asshown in Figs. 3共a兲 and 3共b兲. To discuss the delicate difference in the estimations for cumulative histograms is beyond

FIG. 3. The cumulative distributions of the in-degree and out-degree for e-mail networks in 共a兲 the questionnaires 关10兴 and 共b兲 the server
log files 关13兴. The linear fits are obtained by the integration of power-law functions estimated in Figs. 2共a–d兲 The misfit in the left-hand sideof 共a兲 is due to the dispersion in the limited size of data 关10兴, especially around k⫽100 关see Fig. 2共b兲兴.
016112-2

PHYSICAL REVIEW E 69, 016112 共2004兲

OSCILLATORY EPIDEMIC PREVALENCE IN GROWING . . .
TABLE I. Directed edge generation by the ␣ -␤ coin.
Probability

␤
1⫺ ␤

␣

III. SIMULATIONS FOR STOCHASTIC MODEL1⫺ ␣

Self-loop at new vertex Origin: new, terminal: old
Terminal: new, origin: oldBoth of old vertices

the scope of this paper. It may be caused by the limited sizeof our sample.
C. The „ ␣ , ␤ … model

We generate a SF network for the contact relations between e-mail users, by applying the simple ( ␣ , ␤ ) model 关16兴with the estimated exponents ␥ in and ␥ out in the preceding
section. The slopes of power law ␥ in ⬇1/(1⫺ ␣ ) and ␥ out⬇1/(1⫺ ␤ ) are controlled by the ␣ -␤ coin in Table I 共in thecase of e-mails ␣ ⫽0.4736 and ␤ ⫽0.6). Growing with a newvertex at each step, k edges are added as follows. As theterminal, a coin toss chooses a new vertex with probability ␣
and an old vertex with probability 1⫺ ␣ in proportion to its
in-degree. As the origin, the coin chooses a new vertex withprobability ␤ and an old vertex with probability 1⫺ ␤ inproportion to its out-degree. According to both the growth
and the preferential attachment 关1,2兴, the generation processes are repeated until the required size N is obtained as aconnected component without self-loops and multiedges.
The ( ␣ , ␤ ) model generates both edges from/to a new vertex
and edges between old vertices, the processes are somewhat
analogous to the ones in the generalized Barabási-Albert
共BA兲 model 关1,17兴.

We study the typical behavior in the SHIR model on the
SF networks. In the following simulations, we set the execution rate ␭⫽0.1, the detection rate ␦ ⫽0.04, the average
number of edges k̄⫽6.6, and initial infection sources of randomly chosen five vertices 共the following results are similar
to other small values ␭⫽0.2,0.3 and ␦ ⫽0.05,0.06). These
small values are realistic, because computer viruses are notrecognized before the prevalence and it may be executed bysome users. We note the parameters are related to the sharpness of increasing/decreasing infections up/down ( ␦ is moresensitive兲. It is well known that, in a closed system of the
SHIR model, the number of infected computers in the hidden
and infectious states is initially increased and saturated, andfinally converged to zero as extinction. While the pattern
may be different in an open system, indeed, oscillations havebeen described by a deterministic Kermack-McKendrik
model 关4兴. However, a constant population 共equal rates ofbirth and death兲 or territorial competition has been mainly
discussed in the classical model, the growth of computer
network is obviously more rapid, and the communications inmailing are not competitive. Thus, we consider a growing
system, in which 50 vertices and the corresponding new k̄
edges are added at every step, from an initial SF networkwith N⫽400 up to 203 50 at 400 steps. Here, one step iscorresponding to a day 共400 steps ⬇ 1 yr兲. These values of␭, ␦ , k̄, and the growth rate are only examples with something of reality for simulations, since the actual values that
depend on the observed period are still unknown. As shownin Figs. 4共a兲 and 4共b兲, the phenomena of persistent recoverable prevalence are found in the open system, but not in theclosed system.

FIG. 4. Typical behavior of the spread on SF networks in 共a兲 a closed system and 共b兲 an open system with simultaneous progress of bothspread of viruses and growth of network. The lines show the differences in stochastic state transitions. The effects of immunization are
shown as the averages in the open system for 共c兲 hub and 共d兲 random immunization. The open diamond, square, triangle, and cross marks
are corresponding to the normal detection by the state transitions, immunization of 10%, 20%, and 30%, respectively.
016112-3

PHYSICAL REVIEW E 69, 016112 共2004兲

HAYASHI, MINOURA, AND MATSUKUBO

FIG. 5. Number of vertices in the recovered state by 共a兲 hub and 共b兲 random immunization of 30%. Each of them is the average value
for recoverable prevalence in 100 trials. The dashed lines represent the number of vertices that are already changed to the recovered states
before the immunization.

To prevent the wide spread of infections, we investigate
how to assign antivirus software onto the SF networks. We
verify the effectiveness of the targeted immunization forhubs even in the cases of recoverable prevalence. Figures
4共c兲 and 4共d兲 show the average number of infected computers with recoverable prevalence in 100 trials, where immunized vertices are randomly selected or as hubs according tothe out-degree order of 10%, 20%, 30% of growing size at
every 30 steps 共corresponding to a month兲. The number isdecreased as larger immune rates for hubs, viruses are nearly
extinct 共there exist only few viruses兲 in 30% as marked by ⫻in Fig. 4共c兲. While it is also decreased as larger immune rates
for randomly selected vertices, however they are not extinct
even in 30% as marked by ⫻ in Fig. 4共d兲. Figures 5共a兲 and5共b兲 show the number of recovered states by the hub andrandom immunization of 30% 共triangle marks兲 for the comparison with the normal detections 共rectangle marks兲. The
immunized hubs are more dominant than the normal detections in Fig. 5共a兲. However, there is no such difference forthe random immunization in Fig. 5共b兲. In the case of 10%,
the relation is exchanged; the number of detections is larger
than that of both hub and random immunizations. It is intermediate in the case of 20%. From these results, we remarkthat the targeted immunization for hubs strongly prevents the
spread of infections in spite of the fewer totally recovered
states than that in random immunization.
IV. ANALYSIS FOR DETERMINISTIC MODELdS 共 t 兲⫽⫺b 具 k 典 S 共 t 兲 I 共 t 兲 ⫹a,dt

共1兲

dI 共 t 兲⫽⫺ ␦ 0 I 共 t 兲 ⫹b 具 k 典 S 共 t 兲 I 共 t 兲 ,dt

共2兲where a⬎0 and 0⬍b, and ␦ 0 ⬍1 denote the growth, infecdef

tion, and detection rates, respectively. 具 k 典 ⫽ 兺 k k P(k) is theaverage number of connections with a probability P(k) of
the degree k. The term S(t)I(t) represents the frequency ofcontact relations. Note that the number of recovered vertices
R(t) is a shadow variable defined by dR(t)/dt⫽ ␦ 0 I(t).
From the network size N(t)⫽S(t)⫹I(t)⫹R(t), the solution
is given by N(t)⫽N(0)⫹at as a linear growth. Figure 6共a兲shows the nullclines of
dS
⫽0:
dt

S⫽

a
b具k典I

and
dI
⫽0:
dt

def ␦

S⫽S * ⫽

0

b具k典

,

共 I⫽0 兲for Eqs. 共1兲 and 共2兲. The directions of vector field are definedby the positive or negative signs of dS/dt and dI/dt. There
def

Although the stochastic SHIR model is realistic, theanalysis is very difficult in the open system. Thus, we analyze simpler deterministic SIR models for the spreading ofcomputer viruses to understand the mechanisms of recoverable prevalence and extinction by immunization. We consider the time evolutions of S(t)⬎0 and I(t)⬎0 (t⭓0),which are the number of susceptible and infected vertices.
We assume that infection sources exist in an initial network,and that both network growth and the spread of viruses
progress in continuous time as an approximation. In addition,
we have no specific rules for growing, but consider a linearlygrowing network size and the degree distribution on an undirected connected graph as a consequence.
A. Homogeneous SIR model

As the most simple case, in the homogeneous networks
with only the detection of viruses, the time evolutions are
given byexists a stable equilibrium point (I * ,S * ), I * ⫽ a/ ␦ 0 . The

FIG. 6. Nullclines and the vector fields for 共a兲 homogeneous and共b兲 heterogeneous SIR models. The state in both cases is converged
to an equilibrium point with a damped oscillation, which corresponds to persistent recoverable prevalence around the nonzero
level I * or I *k .

016112-4

PHYSICAL REVIEW E 69, 016112 共2004兲

OSCILLATORY EPIDEMIC PREVALENCE IN GROWING . . .

states of S and I are converged to the point with a damped
oscillation. We can easily check that the real parts of eigenvalues for the Jacobian are negative at the point.

dS k
⫽0:
dt

B. Heterogeneous SIR model

Next, we consider the heterogeneous SF networks at themean-field level, in which the connectivity correlations are
neglected 关18兴. We know that static and grown networks
have different properties for the size of giant component 关19兴and the connectivity correlations 关20,21兴 even if the degree
distributions are the same. In particular, the correlations may
have influence on the spread, however they are not found in
all growing network models or real systems. We have experimentally observed that the correlations are very weak in the( ␣ , ␤ ) model in the previous simulations similar to the nearest neighbors average connectivity of vertex with k edges in
the generalized BA model rather than the fitness model orautonomous system 共AS兲 in the Internet 关22兴. At least, noncorrelation does not seem to be crucial for the absence of
epidemic threshold 关3,7,8,18兴, the existence of correlations isstill much less nontrivial in e-mail networks. Although themean-field approach by neglecting the correlations in macroscopic equations at a large network size is a crude approximation method, it is useful for understanding the mechanisms of the spread in growing networks, as far as it isqualitatively similar to the behavior of viruses in the stochastic model or observed real data. Indeed, the following results
are consistent with the analysis for correlated cases 关23兴,
except of the quantitative differences.
We introduce a linear kernel 关21兴 as N k (t)⬃a k t,N k (t)⫽S k (t)⫹I k (t)⫹R k (t), which is the sum of the numbers ofsusceptible, infected, and recovered vertices with degree k,
def

dI k
⫽0:
dt

dS k 共 t 兲⫽⫺bkS k 共 t 兲 ⌰ 共 t 兲 ⫹a k ,
dt

共3兲

共4兲

def

᭚⌰ * ⫽

factor⬘␦ 0I kkbc k I k ⫹kb

兺
k
⬘

,
c k⬘I *k⬘兺 c k I k* ⬃
k⭓m

冕
␦

A ␥ m ⫺␥⬁0mk ⫺( ␯ ⫹ ␥ ⫹1) dk⫽

A ␥ m ⫺␯,
␦ 0共 ␯ ⫹ ␥ 兲

C. Effect of immunization

We study the effect of random and hub immunization.
With the randomly immune rate 0⬍ ␦ r ⬍1, the time evolutions are given by
dS k 共 t 兲⫽⫺bkS k 共 t 兲 ⌰ 共 t 兲 ⫹a k ⫺ ␦ r S k 共 t 兲 ,dt

共5兲dI k 共 t 兲⫽⫺ ␦ 0 I k 共 t 兲 ⫹bkS k 共 t 兲 ⌰ 共 t 兲 ⫺ ␦ r I k 共 t 兲 ,dt

共6兲where the shadow variable R k (t) is defined by dR k (t)/dt⫽ ␦ 0 I k (t)⫹ ␦ r „S k (t)⫹I k (t)….
Similar to discussions in the preceding section, we consider a section of I k ⬘ ⫽I *k ⬘ : const for all k ⬘ ⫽k. From thenullclines of Eqs. 共5兲 and 共6兲 with random immunization,
def

there exists a stable equilibrium point (I k* ,S k* )⫽ 关 (a k⫺ ␦ rS *k )/( ␦ 0 ⫹ ␦ r ),a k /( ␦ r ⫹kb⌰ * ) 兴 , if the solution
1

冉

␦

冊

def

r
⫽ f 共⌰*兲兺k c k I k* ⫽ ␦ 0 ⫹ ␦ r 兺k a k c k 1⫺ ␦ ⫹bk⌰*r

is self-consistent at the point. The condition is given by

冏

Ab
df
⬇
d⌰ ⌰⫽0 ␦ r 共 ␦ 0 ⫹ ␦ r 兲⌰(t)⫽ 兺 k c k I k (t),c k⫽ k P(k)/ 具 k 典 , represents the expectation that any given edge
points to an infected vertex.
We consider a section of I k ⬘ ⫽I *k ⬘ : const. for all k ⬘ ⫽k.
Figure 6共b兲 shows the nullclines of兺k,c k⬘I *
k⬘by using c k ⫽ ␥ ⫻m ␥ ⫻k ⫺( ␥ ⫹1) for the generalized BA model
关18兴 with a power-law degree distribution P(k)⫽(1⫹ ␥ )m 1⫹ ␥ k ⫺2⫺ ␥ , 具 k 典 ⫽m(1⫹ ␥ )/ ␥ 共which includes thesimple BA model 关2兴 at ␥ ⫽1). On these state spaces in Figs.
6共a兲 and 6共b兲, only the case of a⫽0 or a k ⫽0 gives theextinction: I * ⫽0 or I *k ⫽0. It means that we must stop thegrowth to prevent the infections by detection. In addition, thehomogeneous and heterogeneous systems are regarded as oscillators in Figs. 7共a兲 and 7共b兲.

def

The

kbc k I k ⫹kb

defwhere the shadow variable R k (t) is implicitly defined bydR k (t)/dt⫽ ␦ 0 I k (t).

␦ 0I k⫽kb⌰

akequilibrium point (I k* ,S k* )⫽ (a k / ␦ 0 ,a k /kb⌰ * ), because of⌰ *⫽dI k 共 t 兲⫽⫺ ␦ 0 I k 共 t 兲 ⫹bkS k 共 t 兲 ⌰ 共 t 兲 ,
dt

S k⫽

ak
⫽
kb⌰

and the vector field for Eqs. 共3兲 and 共4兲. There exists a stable⫺␯and the growth rate a k ⫽ Ak ,A⬎0, ␯ ⬎2. Note that the total N(t)⫽ 兺 k N k (t)⬃( 兺 k a k )t means a linear growth of network size. Since the maximum degree increases as the time
progresses and approaches to infinity, it has a nearly constant⬁⬁a k⬃ 兰 m
Ak ⫺ ␯ dk⫽Am 1⫺ ␯ /( ␯ ⫺1) for large
growth rate 兺 k⫽mt. As shown in Ref. 关21兴, the introduction of linear kernel is
not a contradiction with the preferential 共linear兲 attachment关1,2兴.
At the mean-field level in a somewhat large network with
only the detection of viruses, the time evolutions of S k ⬎0
and I k ⬎0 are given by

S k⫽

⫽

冕␥
⬁

m ␥ k ⫺( ␥ ⫹ ␯ ) dkm

Ab ␥ m ⫺( ␯ ⫺1)⬎1.
␦ r 共 ␦ 0 ⫹ ␦ r 兲共 ␥ ⫹ ␯ ⫺1 兲

In this case, the state space is the same as shown in Fig. 6共b兲.

016112-5

PHYSICAL REVIEW E 69, 016112 共2004兲

HAYASHI, MINOURA, AND MATSUKUBO

FIG. 7. Oscillators for 共a兲 homogeneous and 共b兲 heterogeneous
SIR models in the open system.
They consist of S-I pairs with excitatory → and inhibitory ⵬ connections, and an input bias a or a kof the growth rate. The factor ⌰acts as a global inhibition or excitation.

Next, we assume I k*⬘ ⫽0 for all k ⬘ ⫽k to discuss the extinction. On this section, the nullclines are
dS k
⫽0:
dt

S k⫽

ak

␦ r ⫹kb⌰⫽ak␦ r ⫹kbc k I k

and
dI k
⫽0:
dt

S k⫽

共 ␦ 0⫹ ␦ r 兲I k ␦ 0⫹ ␦ r
⫽
kb⌰
kbc k

共 I k ⫽0 兲

for Eqs. 共5兲 and 共6兲. The necessary condition of extinction is
given by the fact that the point (0,a k / ␦ r ) on the nullcline
dS k /dt⫽0 is below the line S k ⫽( ␦ 0 ⫹ ␦ r )/kbc k : const ofdI k /dt⫽0. From the conditiona k ␦ 0⫹ ␦ r⬍,
␦ r kbc k
we obtain␦ r ⬎⫺ ␦ 0 ⫹ 冑␦ 20 ⫹4ka k bc k .

共7兲In addition, since 0⬍ ␦ r ⬍1 must be satisfied, it is given bya k ⬍(1⫹2 ␦ 0 )/4b ␥ from kc k ⫽ ␥ m ␥ k ⫺ ␥ , m⭐k⬍⬁, ␥ ⬎0,
for the generalized BA model 关18兴. In this case, there exists a

stable equilibrium point, otherwise a saddle and a stableequilibrium point as shown in Figs. 8共a兲 and 8共b兲. The state
space is changed through a saddle-node bifurcation by valuesof the growth rate a k and the immune rate ␦ r .
For the hub immunization 关7兴, ␦ r is replaced by 0
⬍ ␦ h k ␶ ⬍1, ␶ ⬎0, e.g., ␶ ⫽1 as proportional immunization to
the degree of vertex. We may choose 1/k ␶ times smaller immune rate ␦ h than ␦ r for Eq. 共7兲. In other words, the necessary condition of extinction in Eq. 共7兲 is relaxed to a k⬍m ␶ (m ␶ ⫹2 ␦ 0 )/4b ␥ . Thus viruses can be removed in larger
growth rate.
The above conditions are almost fitting to the results forthe stochastic model in Sec. III. We can evaluate them using
the corresponding parameters m⫽1, ␯ ⫽2⫹ ␥ ⫽( ␥ in⫹ ␥ out )/2⫽2.2, b↔␭⫽0.1, ␦ 0 ↔ ␦ ⫽0.04, ␦ r or ␦ h⫽0.1,0.2,0.3, ␶ ⫽1, and A⫽60 from ( 兺 a k )⬃ 兰 Ak ⫺ ␯ dk
⫽Am 1⫺ ␯ / ␯ ⫺1⫽50. By simple calculations, we find thata k ⬍(1⫹2 ␦ 0 )/4b ␥ is satisfied for k⭓2. The condition 共7兲 issatisfied for only k⭓5 with random immunization of 30%
and k⭓7 with 20%, so the extinction of viruses is difficult
by spreading of infection from many vertices with low degree k⭐4, whereas it is satisfied for k⭓3 with hub immunization of both 20% and 30% by the factor of 1/k ␶ . The
delicate mismatch at k⫽1,2 may be from the difference ofthe complicated stochastic behavior as in Fig. 1 and the macroscopic crude approximation.

FIG. 8. Saddle-node bifurcation between 共a兲 damped oscillation of recoverable prevalence and共b兲 convergence to the extinction
by the immunization in the heterogeneous SIR model. The state
space is changed by the bifurcation parameters ␦ r and a k for thedefvalue of Ŝ k ⫽ ( ␦ 0 ⫹ ␦ r )/kbc k .

016112-6

PHYSICAL REVIEW E 69, 016112 共2004兲

OSCILLATORY EPIDEMIC PREVALENCE IN GROWING . . .

FIG. 9. Nonextinction in 共a兲homogeneous and 共b兲 heterogeneous SIS models. The number of
infected state I or I k finally diverges to infinity.

D. SIS model

On a section I k ⬘ : const, the nullclines are

Finally, to show that the recovered state is necessary, we
consider the SIS models in the open system. The time evolutions on homogeneous networks are given by
dS 共 t 兲⫽ ␦ 0 I 共 t 兲 ⫺b 具 k 典 S 共 t 兲 I 共 t 兲 ⫹a,dt

共8兲

dI 共 t 兲⫽⫺ ␦ 0 I 共 t 兲 ⫹b 具 k 典 S 共 t 兲 I 共 t 兲 ,
dt

共9兲

dS k
⫽0:
dt

S k⫽

␦ 0 I k ⫹a k
kb⌰

and

dI k
⫽0:
dt

S k⫽

␦ 0I kkb⌰

for Eqs. 共10兲 and 共11兲. There also exists a gap between the
nullclines. Figures 9共a兲 and 9共b兲 show the nullclines and thevector field. Thus, the dynamics in the SIS model is quite
different from that in the SIR model. We cannot realize boththe extinction and the recoverable prevalence of viruses on
the SIS model, in any case, even in the open system.

where N(t)⫽S(t)⫹I(t). The nullclines are
dS
⫽0:
dt

S⫽

V. CONCLUSIONa␦ 0 I⫹a
␦0
⫹
⫽
b具k典I
b具k典 b具k典I

and
dI
⫽0:
dt

S⫽

␦0
:const, 共 I⫽0 兲
b具k典

for Eqs. 共8兲 and 共9兲. There exists a gap of a/b 具 k 典 I⬎0 evenin I * →⬁. Furthermore, the time evolutions on heterogeneous networks are given by
dS k 共 t 兲⫽ ␦ 0 I k 共 t 兲 ⫺bkS k 共 t 兲 ⌰ 共 t 兲 ⫹a k ,
dt

共10兲

dI k 共 t 兲⫽⫺ ␦ 0 I k 共 t 兲 ⫹bkS k 共 t 兲 ⌰ 共 t 兲 .
dt

共11兲

关1兴 R. Albert and A.-L. Barabási, e-print cond-mat/0106096.
关2兴 A.-L. Barabási, R. Albert, and H. Jeong, Physica A 272, 173
共1999兲.
关3兴 R. Pastor-Satorras and A. Vespignani, Phys. Rev. E 63, 066117
共2001兲.
关4兴 N. Shigesada and K. Kawasaki, Biological Invasions: Theory
and Practice 共Oxford University Press, Oxford, 1997兲.
关5兴 R.M. May and A.L. Lloyd, Phys. Rev. E 66, 066112 共2001兲.
关6兴 M.E.J. Newman, Phys. Rev. E 65, 016128 共2002兲.
关7兴 Z. Dezsö and A.L. Barabási, Phys. Rev. E 65, 055103 共2002兲.

In summary, we have investigated the spread of computerviruses via e-mails on linearly growing SF network models
whose exponents of the degree distributions are estimatedfrom real data of sent and received mails 关13兴 or from thegeneralized BA model 关1,18兴. The dynamic behavior is thesame in both simulations for a realistic stochastic SHIR
model and a mean-field approximation without connectivity
correlations for the macroscopic equations of simpler deterministic SIR models. The obtained results suggest that therecoverable prevalence stems from the growth of network,
and it is bifurcated from the extinction state according to therelations of growth, infection, and immune rates. Moreover,
the targeted immunization for hubs is effective even in thegrowing system. Quantitative fitness with really observed virus data and more detailed analysis with the correlations arefurther studies.

关8兴 R. Pastor-Satorras and A. Vespignani, Phys. Rev. E 65, 036104
共2002兲.
关9兴 R. Albert, H. Jeong, and A.-L. Barabási, Nature 共London兲 406,
378 共2000兲.
关10兴 See http://sophy.asaka.toyo.ac.jp/users/mikami/info&media/,
http://www.commerce.or.jp/result/sp3/index.html,
http://
www.dentsu.co.jp/marketing/digital_life/
关11兴 J. O. Kephart and S. R. White, Proceedings of the 1993 IEEE
Coimputer Society Symposium on Security and Privacy 共IEEE,
Washington, 1993兲, pp. 2–15.

016112-7

PHYSICAL REVIEW E 69, 016112 共2004兲

HAYASHI, MINOURA, AND MATSUKUBO
关12兴 S. R. White, J. O. Kephart, and D. M. Chess, Proceedings ofthe Fifth Virus Bulletin International Conference, 1995 共unpublished兲;see
http://www.research.ibm.com/antivirus/
SciPapers/white/VB95/vb95.distrib.html
关13兴 See
http://www.theo-physik.uni-kiel.edu/⬃ebel/email-net/
email-net.html.
关14兴 H. Ebel, L.-I. Mielsch, and S. Bornholdt, Phys. Rev. E 66,
035103共R兲 共2002兲.
关15兴 M.E.J. Newman, S. Forrest, and J. Balthrop, Phys. Rev. E 66,
035101 共2002兲.
关16兴 R. Kumar et al., Proceedings of the 25th VLDB Conference,
1999
共unpublished兲,pp.
639-650;see
http://

www.almaden.ibm.com/cs/people/ravi/papers.html
关17兴 R. Albert and A.-L. Barabási, Phys. Rev. Lett. 85, 5234 共2000兲.
关18兴 Y. Moreno, R. Pastor-Satorras, and A. Vespignani, Euro. Phys.
J. 26, 521 共2002兲.
关19兴 S.N. Dorogovtsev, J.F.F. Mendes, and A.N. Samukhin, Phys.
Rev. E 64, 066110 共2001兲.
关20兴 D.S. Callaway et al., Phys. Rev. E 64, 041902 共2001兲.
关21兴 P.L. Krapivsky and S. Redner, Phys. Rev. E 63, 066123 共2001兲.
关22兴 R. Pastor-Satorras, A. Vázquez, and A. Vespignani, Phys. Rev.
Lett. 87, 258701 共2001兲.
关23兴 Y. Hayashi, e-print cond-mat/0307135.

016112-8