Effect of node deleting on network structure
Ke Deng,∗ Heping Zhao, and Dejun Li
Department of Physics, Jishou University, Jishou, Hunan 416000, People’s Republic of China
The ever-increasing knowledge to the structure of various real-world networks has uncovered their
complex multi-mechanism-governed evolution processes. Therefore, a better understanding to the
structure and evolution of these networked complex systems requires us to describe such processes
in more detailed and realistic manner. In this paper, we introduce a new type of network growth
rule which comprises of adding and deleting of nodes, and propose an evolving network model to
investigate the effect of node deleting on network structure. It is found that, with the introduction of
node deleting, network structure is significantly transformed. In particular, degree distribution of the
network undergoes a transition from scale-free to exponential forms as the intensity of node deleting
increases. At the same time, nontrivial disassortative degree correlation develops spontaneously as a
natural result of network evolution in the model. We also demonstrate that node deleting introduced
in the model does not destroy the connectedness of a growing network so long as the increasing rate
of edges is not excessively small. In addition, it is found that node deleting will weaken but not
eliminate the small-world effect of a growing network, and generally it will decrease the clustering
coefficient in a network.
I. INTRODUCTION
Network structure is of great importance in the topological characterization of complex systems in reality. Actually,
these networked complex systems have been found to share some common structural characteristics, such as the small-
world properties, the power-law degree distribution, the degree correlation, and so on [1, 2, 3]. In the theoretical
description of these findings, the Watts-Strogatz (WS) model [4] provides a simple way to generate networks with
the small-world properties. Barabási and Albert (BA) [5], with a somewhat different aim, proposed an evolving
network model to explain the origin of power-law degree distribution. In this model, by considering two fundamental
mechanisms: growth and preferential attachment (PA), power-law degree distribution emerges naturally from network
evolution. Based on the framework of BA model, many other mechanisms were introduced into network evolution
to reproduce some more complex observed network structures [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17], such as the
degree distribution of broad scale and single scale [6], as well as the degree correlation [17]. These further studies
show that real networked systems may undergo a very complex evolution process governed by multiple mechanisms
on which the occurrence of network structures depends. Therefore, to get a better understanding of the structure and
evolution of complex networks, describing such processes in more detailed and realistic manner is necessary.
In the BA’s framework, the growing nature of real-world networks is captured by a BA-type growth rule. According
to this rule, one node is added into the network at each time step, intending to mimic the growing process of real
systems. This rule gives an explicit description to the real-network’ growing process which, however, can in fact be
much more complex. One fact is that in many real growing networks, there are constant adding of new elements, but
accompanied by permanent removal of old elements (deletion of nodes) [18, 19, 20, 21, 22, 23]. Take the food webs for
a example: there are both additions and losses of nodes (species) at ecological and evolutionary time scales by means
of immigration, emigration, speciation, and extinction [18]. Likewise, for Internet and the World Wide Web (WWW),
node-deleting is reported experimentally in spit of their rapid expansion of size [19, 20, 21, 22, 23]. In the Internet’s
Autonomous Systems (ASs) map case, a node is an AS and a link is a relationship between two ASs. An AS adding
means a new Internet Service Provider (ISP) or a large institution with multiple stub networks joins the Internet. An
AS deleting happens due to the permanent shutdown of the corresponding AS as it is, for example, out of business.
Investigations of the evolution of real Internet maps from 1997 to 2000 verified such network mechanism [19, 20, 21].
The same is for the evolution of WWW, in which the deletions of invalid web pages are also frequently discovered
[22, 23]. In most cases, the deletion of a node is also accompanied with the removal of all edges once attached to it.
These facts justify the investigation of node-deletion’s influence on network structure. In this paper, we introduce a
new type of network growth rule which comprises of adding and deleting of nodes, and propose an evolving network
model to investigate the effect of node deleting on the network structure. Before now several authors have proposed
some models on node removal in networks, such as AJB networks in which a portion nodes are simultaneously removed
∗Electronic address: dengke@jsu.edu.cn
http://arxiv.org/abs/0704.0308v1
mailto:dengke@jsu.edu.cn
from the network [24], and also the decaying [25] and mortal [26] networks, which concerns networks’ scaling property
and critical behavior respectively. Sarshar et al [27] investigated the ad hoc network with node removal, focusing
on the compensatory process to preserve true scale-free state. They are different from present work, in which node
deleting is treated as an ubiquitous mechanism accompanied with the evolution of real-world networks.
This paper is organized as follows. In Section II, an evolving network model taking account of the effect of node
deleting is introduced which reduces to a generalized BA model when the effect of node deleting vanishes. Then
the effect of node deleting on network structure are investigated in five aspects: degree distribution (Section III),
degree correlation (Section IV), size of giant component (Section V), average distance between nodes (Section VI)
and clustering (Section VII). Finally, Section VIII presents a brief summary.
II. THE MODEL
We consider the following model. In the initial state, the network has m0 isolated nodes. At each time step, either
a new node is added into the network with probability Pa or a randomly chosen old node is deleted from the network
with probability Pd = 1 − Pa, where Pa is an adjustable parameter. When a new node is added to the network, it
connects to m (m 6 m0) existing node in the network according to the preferential probability introduced in the BA
model [5], which reads
kα + 1
β(kβ + 1)
where kα is the degree of node α. When an old node is deleted from the network, edges once attached to it are
removed as well. In the model, Pa is varied in the range of 0.5 < Pa ≤ 1, since in the case of Pa 6 0.5 the network
can not grow. In order to give a chance for isolated nodes to receive a new edge, we choose preferential probability
Πα proportional to kα + 1 [7]. Note that when Pa = 1, our model reduces to a generalized BA model [28].
To get a general knowledge to the effect of node deleting on network structure, firstly, a simple analysis to the
surviving probability D(i, t) is helpful. Here, D(i, t) is defined as the probability that a node is added into the
network at time step i, and this node (the ith node) has not been deleted until time step t, where t > i. Supposing
that a node-adding event happens at time step i
, and the probability that the i′th node has not been deleted until
time step t is denoted as D′(i′, t). Then, due to the independence of events happened at each time step, it is easy to
verify that D′(i′, t + 1) = D′(i′, t)[1 − (1 − Pa)/N(t)] with D′(i′, i′) = 1, where N(t) = (2Pa − 1)t is the number of
nodes in the network at moment t (in the limit of large t). In the continuous limit, we obtain
∂D′(i′, t)
= − (1− Pa)
(2Pa − 1)t
D′(i′, t), (2)
which yields
D′(i′, t) =
)−(1−Pa)/(2Pa−1)
. (3)
Thus to get the D(i, t) we should multiply D′(i′, t) with Pa, i.e.
D(i, t) = Pa
)−(1−Pa)/(2Pa−1)
. (4)
One can easily find that D(i, t) decreases rapidly as t increases and/or as i decreases provided 0.5 < Pa < 1. It is well
known that highly connected nodes, or hubs, play very important roles in the structural and functional properties of
growing networks [1, 2, 3]. The formation of hubs needs a long time to gain a large number of connections. As a
consequence, according to Eq. (4), a large portion of potential hubs are deleted during the network evolution. Thus
it can be expected that the introduction of node deleting has nontrivial effects on network structure. In the following
we show how network structure can be effected by the node deleting introduced in present model.
III. DEGREE DISTRIBUTION
The degree distribution p(k), which gives the probability that a node in the network possesses k edges, is a very
important quantity to characterize network structure. In fact, p(k) has been suggested to be used as the first criteria
to classify real-world networks [6]. Therefore it is necessary to investigate the effect of node deleting on the degree
distribution of networks firstly. Now we adopt the continuous approach [29] to give a qualitative analysis of p(k)
for our model with slight node deletion (i.e., when Pd is very small). Supposing that there is a node added into the
network at time step i′, and this node is still in the network at time t, let k(i′, t) be the degree of the i′th node at
time t, where t > i′. Then the increasing rate of k(i′, t) is
∂k(i′, t)
= Pam
k(i′, t) + 1
− (1− Pa)
k(i′, t)
, (5)
where
S(t) =
D′(i′, t)[k(i′, t) + 1] (6)
and the
′ denotes the sum of all i′ during the time step between 0 and t. It is easy to verify that the first term
in Eq. (5) is the increasing number of links of the i′th node due to the preferential attachment made by the newly
added node. The second term in Eq. (5) accounts for the losing of a link of the i′th node during the process of node
deletion, which happened with the probability k(i′, t)/N(t).
Firstly we solve for the S(t) and get
S(t) = (2Pa − 1) (2Pam+ 1) t (7)
(see the Appendix for details). Inserting Eq. (7) back into Eq. (5), one gets
∂k(i′, t)
Ak(i′, t) +B
, (8)
where
2P 2am− Pam+ Pa − 1
(2Pa − 1)(2Pam+ 1)
(2Pa − 1)(2Pam+ 1)
. (10)
When Ak +B > 0, the solution of Eq. (8) is
k(i′, t) =
(Am+B)
. (11)
Now, to get the probability p(k, t) that a randomly selected node at time t will have degree k, we need to calculate the
expected number of nodes Nk(t) with degree k at time t. Then the p(k, t) can be obtained from p(k, t) = Nk(t)/N(t),
where N(t) is the total number of nodes at time t. Let Ik(t) represent the set of all possible nodes with degree k at
time t, then one gets
p(k, t) =
Nk(t)
i∈Ik(t)
D(i, t). (12)
In the continuous-time approach, the number of nodes in Ik(t) is the number of i’s for which k 6 k(i, t) 6 k + 1,
and it is approximated to |∂k(i, t)/∂i|−1i=ik , where ik is the solution of the equation k(i, t) = k. To proceed with our
analysis, now we make the approximation that all nodes in Ik(t) have the same surviving probability D(ik, t) [44].
Under this mean-field approximation, Eq. (12) can be written as
p(k, t) =
D(ik, t)
∂k(i, t)
. (13)
From Eq. (11), we obtain
Ak +B
t. (14)
1 2 3 4 5 6 7 8 9 10
FIG. 1: Pmina [defined in Eq. (20)] as a function of m.
∂k(i, t)
= (Am+B)
t (Ak +B)
−(A+1)/A
. (15)
Inserting Eq. (14) back into Eq. (4) we get
D(ik, t) = Pa
Ak +B
)(A−B)/A
Inserting Eqs. (15) and (16) into Eq. (13), and noting that N(t) = (2Pa − 1)t, we get
p(k, t) =
2Pa − 1
(Am+B)
(B−A+1)/A
(Ak +B)
−(B+1)/A
, (17)
which is a generalized power-law form with the exponent
B + 1
= 2 +
Pam+ 1
2P 2am− Pam+ Pa − 1
. (18)
We point out again that equation (11) is only valid when Ak +B > 0, which translates into A > 0, i.e.
2P 2am− Pam+ Pa − 1 > 0. (19)
Considering that Pa > 0.5, Eq. (19) is satisfied when
Pa > P
(m− 1) +
m2 + 6m+ 1
. (20)
In Fig. 1, we plot Pmina as a function of m. One can see from Fig. 1 that the curve divides our model into two regimes.
(i) Pa > P
a : in this case Ak + B > 0 and equation (11) is valid. Thus, the degree distribution of the network
p(k) exhibits a generalized power-law form. (ii) Pa > P
a : In this case Ak + B > 0 can not be always satisfied
and equation (11) is not valid. Therefore, our continuous approach fails to predict the behavior of p(k), and we will
investigate it with numerical simulations. The Pmina (m), as one can find from Fig. 1, decreases with the increase of
In the power-law regime [Pa > P
a (m)], the behavior of p(k) is predicted by Eqs. (17) and (18), which are obtained
using a mean-field approximation [Eq. (13)]. One can easily verify that such approximation is only exact when Pa = 1,
in which case Eq. (18) turns into γ = 3 + 1/m, in good agreement with the results obtained from generalized BA
100 101 102 103
1.00 0.95 0.90
 power-law fit 
 pa=1.0
 pa=0.95
 pa=0.9
 pa=0.8
 pa=0.7
 pa=0.6
 pa=0.55 
 pa=0.51
exponential fit 
FIG. 2: Cumulative degree distribution P (k) for networks with system size N = 100000 and different values of Pa, in logarithmic
scales. The dash line is power-law fit for Pa = 1. The solid line is the exponential fit for Pa = 0.51. In the simulation, we
set m0 = m = 5 and each distribution is based on 10 independent realizations. Inset plots the power-law exponential γ as a
function of Pa. The continuous curve is according to the analytic result of Eq. (18), and circles to the simulation results.
model studied in Ref [28]. If Pmina (m) < Pa < 1, Eqs. (17) and (18) still give qualitative predictions for the model:
with slight node deletion, p(k) of the network is still power-law, and the exponential γ increases with the decrease of
Pa (inset of Fig. 2).
In remaining regime [Pa < P
a (m)], the limiting case is Pa → 0.5, in which the growth of network is suppressed (a
very slowly growing one). Similar non-growing networks have been studied, for example, for the Model B in Ref[30],
and the degree distribution has the exponential form. Here we conjecture that, in this regime, p(k) of our model
crossovers to an exponential form, which is verified by the numerical simulation results below.
Now we verify the above analysis with numerical simulations. In Fig. 2, we give the cumulative degree distributions
P (k) [3] of the networks with different Pa. As Pa gradually decreases from 1 to 0.5, Fig. 2 shows an interesting
transition process which can be roughly divided into three stages. (1) 0.9 6 Pa 6 1: In this stage, the model works in
the power-law regime and the power-law exponent γ increases as Pa decreases. Inset of Fig. 2 gives the comparison
between the value of γ predicted by Eq. (18) and the one obtained from numerical simulations. One sees that the
theory and the simulation results are in perfect agreement for Pa = 1. As Pa decreases, however, the agreement is only
qualitative and the deviation between theory and simulation becomes more and more obvious. As we have mentioned
above, such increasing deviation is due to the mean-field approximation used in the analysis. These results tell us that
slight node deletion does not cause deviation of the network from scale-free state, but only increases its power-law
exponent. Such robustness of power-low p(k) revealed here gives an explanation to the ubiquity of scale-free networks
in reality. It should be noted that a very similar robustness has also been found in the study of network resilience,
where simultaneously deleting of a portion of nodes was taken into account in static scale-free networks [24]. (2)
0.5 < Pa 6 0.6: In this stage, the model works in the regime of Pa < P
a (m). As one sees from Fig. 2, P (k) of
the network behaviors exponentially. This result indicates that with manifest node deletion, the network will deviate
from scale-free state and become exponential. (3) 0.6 < Pa < 0.9: In this stage, a crossover of the model from the
power-law regime to the exponential regime is found, in which the P (k) is no longer pure scale-free but truncated by
an exponential tail. As one can see, the truncation in P (k) increases as Pa decreases.
Besides the power-law degree distribution, it is now known that p(k) in real world may deviate from a pure power-
law form [18, 31, 32, 33, 34]. According to the extent of deviation, p(k) of real systems has been classified into three
groups [6]: scale-free (pure power-law), broad scale (power-law with a truncation), and single scale (exponential).
Many mechanisms, such as aging [6, 8, 9], cost [6], and information filtering [10], have been introduced into network
growth to explain these distributions. Here, the results of Fig. 2 indicate that a modified version of growth rule can
lead to all the three kinds of p(k) in reality, and it provides another explanation for the origin of the diversity of
degree distribution in real-world: such diversity may be a natural result of network growth.
0.0 2.0x104 4.0x104 6.0x104 8.0x104 1.0x105
-0.12
-0.10
-0.08
-0.06
-0.04
-0.02
 pa=1       pa=0.9
 pa=0.8    pa=0.7
 pa=0.6    pa=0.55
FIG. 3: Assortativity coefficient r plotted with network size N , for different Pa in the model. In the simulation, m0 = m = 5.
Result of each curve is based on 10 independent realizations.
IV. DEGREE CORRELATION
It has been recently realized that, besides the degree distribution, structure of real networks are also characterized
by degree correlations [19, 35, 36, 37, 38]. This translates into the fact that degrees at the end of any given edge in real
networks are not usually independent, but are correlated with one another, either positively or negatively. A network
in which the degrees of adjacent nodes are positively (negatively) correlated is said to show assortative (disassortative)
mixing by degree. An interesting observation emerging from the comparing of real networks of different types is that
most social networks appear to be assortatively mixed, whereas most technological and biological networks appear to
be disassortative. The level of degree correlation can be quantified by the assortativity coefficient r lying in the range
−1 6 r 6 1, which can be written as
i jiki −
(ji + ki)
(j2i + k
(ji + ki)
for practical evaluation on an observed network, where ji, ki are the degrees of the vertices at the ends of the ith edge,
with i = 1, . . . ,M [35]. This formula gives r > 0(r < 0) when the corresponding network is positively (negatively)
correlated, and r = 0 when there is no correlation [45].
Recently, Maslov et al [39] and Park et al [40] have proposed a possible explanation for the origin of such correlation.
They show for a network the restriction that there is at most one edge between any pair of nodes induces negative
degree correlations. This restriction seems to be an universal mechanism (indeed, there is no double edges in most
real networks), therefore, the authors of Ref. [40] conjecture that disassortativity by degree is the normal state of
affairs for a network. Although only a part of the measured correlation can be explained in the way of Ref. [40], this
universal mechanism does give a promising explanation for the origin of degree correlation observed in real networks
of various types.
It will be of great interest to discuss the effect of node deleting on degree correlation. In Fig. 3, we give the
assortativity coefficient r as a function of network size N , for different Pa in our model, for m = 5. As one sees
from Fig. 3, for each value of Pa, after a transitory period with finite-size effect, each r of networks tends to reach
a steady value. When Pa = 1, r → 0 as N becomes large. This result indicates that networks in the BA model are
uncorrelated, in agreement with results obtained in previous studies [35, 38]. When Pa < 1, nontrivial negative degree
correlations spontaneously develop as networks evolve. One can see from Fig. 3 that the steady value of r in the model
decreases with the decreasing Pa. In particular, when Pa 6 0.6, the value of r is about −0.1. These results indicate
that node deleting leads to disassortative mixing by degree in evolving networks. To make such relation more clear,
in Fig. 4, we plot r of networks in our model as a function of Pa, for different m. As the Fig. 3 indicates, when the
network size is larger than 40000, the assortativity coefficient r is nearly stable. So all results in Fig. 4 are obtained
from networks with N = 40000. Fig. 4 gives us the same relation between r and Pa shown in Fig. 3. What is more,
it tells us that for a given Pa, r will increase with the increasing m. The increment gets its maximum between m = 1
1.0 0.9 0.8 0.7 0.6 0.5
-0.20
-0.16
-0.12
-0.08
-0.04
 m=14
 m=15
FIG. 4: Assortativity coefficient r as a function of Pa, for different m in the model. In the simulation, N = 40000. Result of
each curve is based on 10 independent realizations.
0.0 2.0x104 4.0x104 6.0x104 8.0x104 1.0x105
-0.06
 pa=1      pa=0.9
 pa=0.8    pa=0.7
 pa=0.6    pa=0.55
FIG. 5: Assortativity coefficient r plotted with network size N , for different Pa in the randomly growing network model. In
the simulation, m0 = m = 5 and each curve is based on 10 independent realizations.
and other values. We point out that this is because when m = 1, the network has been broke up into small separate
components (see the following section). We can also find from Fig. 4 that the gap between different curves decreases
with the increasing m and the curves tend to merge at large m.
Now we give some explanations to the above observations. In the BA model, the network being uncorrelated is
the result of a competition between two factors: the growth and the preferential attachment (PA). On the one hand,
networks with pure growth is positively correlated. This is because the older nodes, also tending to be higher degree
ones, have a higher probability of being connected to one another, since they coexisted earlier. In Fig. 5, we compute
the assortativity coefficient r of a randomly growing network, which grows by the growth rule of BA-type, while the
newly added nodes connect to randomly chosen existing ones. As one can see from Fig. 5 that pure growth leads to
positive r. On the other hand, the introduction of PA makes the connection between nodes tend to be negatively
correlated, since newly added nodes (usually low degree ones) prefer to connect to highly connected ones. Then
degree correlation characteristic of the BA model is determined by this two factors. In Fig. 6, we plot the average
degree of the nearest neighbor < k >nn as a function of k in the BA model. It is found that nodes with large k show
no obvious biases in their connections. But there is a short disassortative mixing region when k is relatively small
(also reported in Ref. [41], see Fig.1a therein). Such phenomenon can be explained by the effect of these two factor:
10 20 30 40 50 60 70 80 90 100
FIG. 6: Average degree of the nearest neighbor as a function of k for the BA model. In the simulation, N = 10000 and
m = m0 = 5. Result of each curve is based on 1000 independent realizations.
1.0 0.9 0.8 0.7 0.6 0.5
1.0 0.9 0.8 0.7 0.6 0.5
FIG. 7: The relative size of the largest component S as a function of Pa for m = 2, 3, 4, 5. Inset gives the same curve for m = 1.
In the simulations, N = 100000. All results are based on 10 independent realizations.
Growth together with PA makes nodes with large k equally connect to both large and small degree nodes, and the
latter makes nodes with small degree be disassortatively connected. Now, we introduce node-deletion. According to
Eq. (4), depression of the growth of large-degree nodes also decreases the connections between them, therefore makes
the correlation negative. We also investigate the effect of node deleting on the r of the randomly growing network,
and obtained similar results. As one sees from Fig. 5, depression of connections between higher degree nodes causes
the network less positively correlated, and with stronger node-deletion, negatively correlated. Finally, with regard to
the effect of m in this relation (Fig. 4), larger m means more edges are established according to the PA probability
Eq. (1). We conjecture that the orderliness of newly added nodes connecting to large degree nodes will be weakened
by the increasing randomness as m becomes larger, thus leading to a less negative correlation. Such randomness can
not always increase and, as we see from Fig. 4, for large m, e.g., m ≥ 14, the curves tend to merge together.
V. SIZE OF GIANT COMPONENT
In a network, a set of connected nodes forms a component. If the relative size of the largest component S in a
network approaches a nonzero value when the network is grown to infinite size, this component is called the giant
component of the network [1, 2, 3]. In most previously studied growing models [1, 2, 3], due to the BA-type growth
rule they adopted, there is only one huge component in the network, i.e., S ≡ 1. In this extreme case the network
gains a perfect connectedness. The opposite case of S = 1 is the extreme of S = 0, in which case the network,
made up of small components, exhibits no connectedness. Experiments indicate that some real networks seem to
lie in somewhere between these two extreme: they contain a giant component as well as many separate components
[2, 3, 42, 43]. For example, According to Ref.[42], in May of 1999, the entire WWW, containing 203 × 106 pages,
consisted of a giant component of 186× 106 pages and the disconnected components (DC) of about 17× 106 pages. In
general, the introduction of node deletion in our model will cause the emergence of separate components even isolated
nodes in the network. What we interest here is the connectedness of the network. In Fig. 7 we plot the relative size
of the largest component S in the model, as a function of Pa, for m = 2, 3, 4, 5, where m is the number of edges
generated with the adding of a new node. One sees from Fig. 7 that for any 0.5 < Pa ≤ 1, a giant component can be
observed in the model if m > 1. In addition, for the same Pa, S increase as the increase of m. While when m = 1, the
network is found to be broke up into separate components if Pa < 1. For example, when Pa = 0.9, S of the network
with N = 100000 rapidly drops to 0.034. Inset of Fig. 7 gives the S Vs Pa curve for m = 1. These results indicate
that node deleting does not destroy the connectedness of a growing network so long as the increasing rate of edges is
not excessively small.
VI. AVERAGE DISTANCE BETWEEN NODES
Now we study the effect of node deletion on networks’ average distance L between nodes. Here the distance between
any two nodes is defined as the number of edges along the shortest path connecting them. It has been revealed that,
despite their often large size, most real networks present a relatively short L, showing the so-called small-world effect
[1, 2, 3, 4]. Such an effect has a more precise meaning: networks are said to show the small-world effect if the value
of L scales logarithmically or slower with network size for fixed mean degree. This logarithmic scaling can be proved
for a variety of network models [1, 2, 3]. As we have demonstrated in Section V, node deleting does not destroy the
connectedness of the network in our model for any m > 1, since there is always a giant component exists. Here in
our simulation, we calculate L of the giant component of the network in our model using the burning algorithm [3].
In Fig. 8, we plot L as a function of network size N , for different Pa in our model. As one can see from the figure,
for any 0.5 < Pa ≤ 1, a logarithmic scaling L ∼ lnN is obtained, while the proportional coefficient increases with
the decrease of Pa. Furthermore, for a given N , L increases with the decrease of Pa. These results tell us that node
deleting will weaken but not eliminate the small-world effect of a growing network.
VII. CLUSTERING
Finally, we investigate the effect of node deletion on network’s cluster coefficient C, which is defined as the average
probability that two nodes connected to a same other node are also connected. For a selected node i with degree ki
in the network, if there are Ei edges among its ki nearest neighbors, the cluster coefficient Ci of node i is defined as
ki (ki + 1)
. (22)
Then the clustering coefficient of the whole network is the average of all individual Ci. In Fig. 9, we plot C of the
giant component in the network as a function of network size N , for different Pa. As one sees from Fig. 9, for each Pa,
the clustering coefficient C of our model decreases with the network size, following approximately a power law form.
Such size-dependent property of C is shared by many growing network model [1, 2, 3]. Moreover, as Fig. 9 shows,
for the same network-size N , C decreases as Pa decreases. The results of Fig. 9 indicate that node deleting weakens
network’s clustering.
VIII. CONCLUSION
In summary, we have introduced a new type of network growth rule which comprises of adding and deleting of nodes,
and proposed an evolving network model to investigate effects of node deleting on network structure. It has been
102 103 104 105
 Pa=1
 Pa=0.9
 Pa=0.8
 Pa=0.7
 Pa=0.6
 Pa=0.55
 Pa=0.51
FIG. 8: Average distance L of the giant component in the network as a function of network size N , for different Pa in the
model. The chose of some parameters: m0 = m = 5. These curves are results of 10 independent realizations.
102 103 104 105
 Pa=1
 Pa=0.9
 Pa=0.8
 Pa=0.7
 Pa=0.6
 Pa=0.55
FIG. 9: Cluster coefficient C of the giant component in the network as a function of network size N , for different Pa. In the
simulation we set m0 = m = 5. These curves are results of 10 independent realizations.
found that, with the introduction of node deleting, network structure was significantly transformed. In particular,
degree distribution of the network undergoes a transition from scale-free to exponential forms as the intensity of node
deleting increased. At the same time, nontrivial disassortative degree correlation spontaneously develops as a natural
result of network evolution in the model. We also have demonstrated that node deleting introduced in our model does
not destroy the connectedness of a growing network so long as the increasing rate of edge is not excessively small. In
addition, it has been observed that node deleting will weaken but not eliminate the small-world effect of a growing
network. Finally, we have found that generally node deleting will decrease the clustering coefficient in a network.
These nontrivial effects justify further studies of the effect of node deleting on network function [3], which include
topics such as percolation, information and disease transportation, error and attack tolerance, and so on.
Acknowledgments
The authors thank Doc. Ke Hu for useful discussions. This work is supported by the National Natural Science
Foundation of China, Grant No. 10647132, and Natural Science Foundation of Hunan Province, China, Grant No.
00JJY6008.
APPENDIX: THE CALCULATION OF S(T )
To get S(t), we multiply both sides of Eq. (5) by D′(i′, t) and sum up all i′ between 0 and t:
∂k(i′, t)
D′(i′, t) = Pa(m− 1)−
1− Pa
(2Pa − 1)t
S(t) + 1. (A.1)
To get the above equation we have used the definition of S(t) [Eq. (6)] and the following equation:
D′(i′, t) =
D(i, t)di. (A.2)
The left-hand side of Eq. (A.1) can be simplified as:
∂ {[k(i′, t) + 1]D′(i′, t)}
[k(i′, t) + 1]
∂D′(i′, t)
[k(i′, t) + 1]D′(i′, t)
− [k(t, t) + 1]D(t, t)
[k(i′, t) + 1]D′(i′, t)
Pa − 1
(2Pa − 1)t
Substituting the above expression in Eq. (A.1), and noting that k(t, t) = m and D(t, t) = Pa, we get
∂S(t)
2(Pa − 1)
(2Pa − 1)t
S(t) + 2Pam+ 1.
The solution to the above equation is
S(t) = (2Pa − 1) (2Pam+ 1) t.
[1] R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002).
[2] S. N. Dorogovtsev, and J. F. F. Mendes, Adv. Phys. 51, 1079 (2002).
[3] M. E. J. Newman, SIAM Review 45, 167 (2003).
[4] D. J. Watts and S.H. Strogatz, Nature (London) 393, 440 (1998).
[5] A.-L. Barabási and R. Albert, Science, 286, 509 (1999).
[6] L. A. N. Amaral, A. Scala, M. Barthélémy and H. E. Stanley, Proc. Natl. Acad. Sci. U.S.A. 97, 11149 (2000).
[7] R. Albert and A.-L. Barabási, Phys. Rev. Lett. 85, 5234 (2000).
[8] S. N. Dorogovtsev and J. F. F. Mendes, Phys. Rev. E 62, 1842 (2000).
[9] K. Klemm and V. M. Egúıluz, Phys. Rev. E 65, 036123 (2002).
[10] S. Mossa, M. Barthélémy, H. E. Stanley and L. A. N. Amaral, Phys. Rev. Lett. 88, 138701 (2002).
[11] Z. Liu, Y.-C. Lai and N. Ye, Phys. Rev. E 66, 036112 (2002).
[12] S. Fortunato, A. Flammini and F. Menczer, Phys. Rev. Lett. 96, 218701 (2006).
[13] W. Jeżewski, Phys. Rev. E 66, 067102 (2002).
[14] R. Xulvi-Brunet and I. M. Sokolov, Phys. Rev. E 66, 026118 (2002).
[15] A. Vázquez, Phys. Rev. E 67, 056104 (2003).
[16] Tao Zhou, Gang Yan and B.-H. Wang, Phys. Rev. E 71, 046141 (2005).
[17] Wen-Xu Wang, Bo Hu, Tao Zhou, Bing-Hong Wang, and Yan-Bo Xie, Phys. Rev. E 72, 046140 (2005).
[18] J. A. Dunne, R. J. Williams and N. D. Martinez, Proc. Natl. Acad. Sci. U.S.A. 99, 12917 (2002).
[19] K.-I. Goh, B. Kahng and D. Kim, Phys. Rev. Lett. 88, 108701 (2002).
[20] Q. Chen et al., The origins of power laws in Internet topologies revisited, in Proceedings of the 21st Annual Joint Conference
of the IEEE Computer and Communications Societies, IEEE Computer Society (2002).
[21] A. Vázquez, R. Pastor-Satorras1 and A. Vespignani, Phys. Rev. E 65, 066130 (2002).
[22] S. Lawrence and C. Lee Giles, Science, 280, 98 (1998).
[23] B. A. Huberman and L. A. Adamic, Nature (London), 401, 131 (1999).
[24] R. Albert, H. Jeong and A.-L. Barabási, Nature (London) 406, 378 (2000).
[25] S. N. Dorogovtsev and J. F. F. Mendes, EuroPhys. Lett. 52, 33 (2000).
[26] J. L. Slater, B. D. Hughes and K. A. Landman, Phys. Rev. E 73, 066111 (2006).
[27] N. Sarshar and V. Roychowdhury, Phys. Rev. E 69, 026101 (2004).
[28] S. N. Dorogovtsev, J. F. F. Mendes and A. N. Samukhin, Phys. Rev. Lett. 85, 4633 (2000).
[29] S. N. Dorogovtsev and J. F. F. Mendes, Phys. Rev. E 63, 056125 (2001).
[30] A.-L. Barabási, R. Albert and H. Jeong, Physica A 272, 173 (1999).
[31] M. E. J. Newman, Computer Physics Communications 147, 40 (2002).
[32] J. Camacho, R. Guimerà and L. A. N. Amaral, Phys. Rev. Lett. 88, 228102 (2002).
[33] M. E. J. Newman, S. Forrest and J. Balthrop, Phys. Rev. E 66, 035101 (2002).
[34] H. Jeong, S. P. Mason, A.-L. Barabási and Z. N. Oltvai, Nature (London), 411, 41 (2001).
[35] M. E. J. Newman, Phys. Rev. Lett. 89, 208701 (2002).
[36] R. Pastor-Satorras1, A. Vázquez and A. Vespignani, Phys. Rev. Lett. 87, 258701 (2001).
[37] S. Maslov and K. Sneppen, Science, 296, 910 (2002).
[38] M. E. J. Newman, Phys. Rev. E 67, 026126 (2003).
[39] S. Maslov, K. Sneppen and A. Zaliznyak, e-print cond-mat/0205379.
[40] J. Park and M. E. J. Newman, Phys. Rev. E 68, 026112 (2003).
[41] Huang Zhuang-Xiong, Wang Xin-Ran and Zhu Han, Chinese Physics 13, 273 (2004).
[42] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener, in Proceedings of
the 9th WWW Conference (Elsevier, Amsterdam, 2000), p. 309.
[43] S. N. Dorogovtsev, J. F. F. Mendes and A. N. Samukhin, Phys. Rev. E 64, 025101(R) (2001).
[44] It seems that this is not a very good approximation, since investigations indicate that values of (∂D(i, t)/∂i) |i=ik are large
and increase rapidly with the decrease of Pa. Thus the analysis here is a qualitative one and only suit for the condition of
slight node deletion in the model.
[45] Another way to represent degree correlation is to calculate the mean degree of the nearest neighbors of a vertex as a function
of the degree k of that vertex. Although such way is explicit to characterize degree correlation for highly heterogeneously
organized networks, for less heterogeneous networks (this is the case in the proposed model when the intensity of node
deleting increases, see Fig. 2), it may be very nosy and difficult to interpret. So here we adopt the assortativity coefficient
r to characterize degree correlation in the model.
http://arxiv.org/abs/cond-mat/0205379
	INTRODUCTION
	THE MODEL
	DEGREE DISTRIBUTION
	DEGREE CORRELATION
	SIZE OF GIANT COMPONENT
	AVERAGE DISTANCE BETWEEN NODES
	CLUSTERING
	CONCLUSION
	Acknowledgments
	THE CALCULATION OF S(T)
	References

  The ever-increasing knowledge of the structure of various real-world networks
has uncovered their complex multi-mechanism-governed evolution processes.
Therefore, a better understanding of the structure and evolution of these
networked complex systems requires us to describe such processes in a more
detailed and realistic manner. In this paper, we introduce a new type of
network growth rule which comprises addition and deletion of nodes, and propose
an evolving network model to investigate the effect of node deleting on network
structure. It is found that, with the introduction of node deleting, network
structure is significantly transformed. In particular, degree distribution of
the network undergoes a transition from scale-free to exponential forms as the
intensity of node deleting increases. At the same time, nontrivial
disassortative degree correlation develops spontaneously as a natural result of
network evolution in the model. We also demonstrate that node deleting
introduced in the model does not destroy the connectedness of a growing network
so long as the increasing rate of edges is not excessively small. In addition,
it is found that node deleting will weaken but not eliminate the small-world
effect of a growing network, and generally it will decrease the clustering
coefficient in a network.

Effect of node deleting on network structure
Ke Deng,∗ Heping Zhao, and Dejun Li
Department of Physics, Jishou University, Jishou, Hunan 416000, People’s Republic of China
The ever-increasing knowledge to the structure of various real-world networks has uncovered their
complex multi-mechanism-governed evolution processes. Therefore, a better understanding to the
structure and evolution of these networked complex systems requires us to describe such processes
in more detailed and realistic manner. In this paper, we introduce a new type of network growth
rule which comprises of adding and deleting of nodes, and propose an evolving network model to
investigate the effect of node deleting on network structure. It is found that, with the introduction of
node deleting, network structure is significantly transformed. In particular, degree distribution of the
network undergoes a transition from scale-free to exponential forms as the intensity of node deleting
increases. At the same time, nontrivial disassortative degree correlation develops spontaneously as a
natural result of network evolution in the model. We also demonstrate that node deleting introduced
in the model does not destroy the connectedness of a growing network so long as the increasing rate
of edges is not excessively small. In addition, it is found that node deleting will weaken but not
eliminate the small-world effect of a growing network, and generally it will decrease the clustering
coefficient in a network.
I. INTRODUCTION
Network structure is of great importance in the topological characterization of complex systems in reality. Actually,
these networked complex systems have been found to share some common structural characteristics, such as the small-
world properties, the power-law degree distribution, the degree correlation, and so on [1, 2, 3]. In the theoretical
description of these findings, the Watts-Strogatz (WS) model [4] provides a simple way to generate networks with
the small-world properties. Barabási and Albert (BA) [5], with a somewhat different aim, proposed an evolving
network model to explain the origin of power-law degree distribution. In this model, by considering two fundamental
mechanisms: growth and preferential attachment (PA), power-law degree distribution emerges naturally from network
evolution. Based on the framework of BA model, many other mechanisms were introduced into network evolution
to reproduce some more complex observed network structures [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17], such as the
degree distribution of broad scale and single scale [6], as well as the degree correlation [17]. These further studies
show that real networked systems may undergo a very complex evolution process governed by multiple mechanisms
on which the occurrence of network structures depends. Therefore, to get a better understanding of the structure and
evolution of complex networks, describing such processes in more detailed and realistic manner is necessary.
In the BA’s framework, the growing nature of real-world networks is captured by a BA-type growth rule. According
to this rule, one node is added into the network at each time step, intending to mimic the growing process of real
systems. This rule gives an explicit description to the real-network’ growing process which, however, can in fact be
much more complex. One fact is that in many real growing networks, there are constant adding of new elements, but
accompanied by permanent removal of old elements (deletion of nodes) [18, 19, 20, 21, 22, 23]. Take the food webs for
a example: there are both additions and losses of nodes (species) at ecological and evolutionary time scales by means
of immigration, emigration, speciation, and extinction [18]. Likewise, for Internet and the World Wide Web (WWW),
node-deleting is reported experimentally in spit of their rapid expansion of size [19, 20, 21, 22, 23]. In the Internet’s
Autonomous Systems (ASs) map case, a node is an AS and a link is a relationship between two ASs. An AS adding
means a new Internet Service Provider (ISP) or a large institution with multiple stub networks joins the Internet. An
AS deleting happens due to the permanent shutdown of the corresponding AS as it is, for example, out of business.
Investigations of the evolution of real Internet maps from 1997 to 2000 verified such network mechanism [19, 20, 21].
The same is for the evolution of WWW, in which the deletions of invalid web pages are also frequently discovered
[22, 23]. In most cases, the deletion of a node is also accompanied with the removal of all edges once attached to it.
These facts justify the investigation of node-deletion’s influence on network structure. In this paper, we introduce a
new type of network growth rule which comprises of adding and deleting of nodes, and propose an evolving network
model to investigate the effect of node deleting on the network structure. Before now several authors have proposed
some models on node removal in networks, such as AJB networks in which a portion nodes are simultaneously removed
∗Electronic address: dengke@jsu.edu.cn
http://arxiv.org/abs/0704.0308v1
mailto:dengke@jsu.edu.cn
from the network [24], and also the decaying [25] and mortal [26] networks, which concerns networks’ scaling property
and critical behavior respectively. Sarshar et al [27] investigated the ad hoc network with node removal, focusing
on the compensatory process to preserve true scale-free state. They are different from present work, in which node
deleting is treated as an ubiquitous mechanism accompanied with the evolution of real-world networks.
This paper is organized as follows. In Section II, an evolving network model taking account of the effect of node
deleting is introduced which reduces to a generalized BA model when the effect of node deleting vanishes. Then
the effect of node deleting on network structure are investigated in five aspects: degree distribution (Section III),
degree correlation (Section IV), size of giant component (Section V), average distance between nodes (Section VI)
and clustering (Section VII). Finally, Section VIII presents a brief summary.
II. THE MODEL
We consider the following model. In the initial state, the network has m0 isolated nodes. At each time step, either
a new node is added into the network with probability Pa or a randomly chosen old node is deleted from the network
with probability Pd = 1 − Pa, where Pa is an adjustable parameter. When a new node is added to the network, it
connects to m (m 6 m0) existing node in the network according to the preferential probability introduced in the BA
model [5], which reads
kα + 1
β(kβ + 1)
where kα is the degree of node α. When an old node is deleted from the network, edges once attached to it are
removed as well. In the model, Pa is varied in the range of 0.5 < Pa ≤ 1, since in the case of Pa 6 0.5 the network
can not grow. In order to give a chance for isolated nodes to receive a new edge, we choose preferential probability
Πα proportional to kα + 1 [7]. Note that when Pa = 1, our model reduces to a generalized BA model [28].
To get a general knowledge to the effect of node deleting on network structure, firstly, a simple analysis to the
surviving probability D(i, t) is helpful. Here, D(i, t) is defined as the probability that a node is added into the
network at time step i, and this node (the ith node) has not been deleted until time step t, where t > i. Supposing
that a node-adding event happens at time step i
, and the probability that the i′th node has not been deleted until
time step t is denoted as D′(i′, t). Then, due to the independence of events happened at each time step, it is easy to
verify that D′(i′, t + 1) = D′(i′, t)[1 − (1 − Pa)/N(t)] with D′(i′, i′) = 1, where N(t) = (2Pa − 1)t is the number of
nodes in the network at moment t (in the limit of large t). In the continuous limit, we obtain
∂D′(i′, t)
= − (1− Pa)
(2Pa − 1)t
D′(i′, t), (2)
which yields
D′(i′, t) =
)−(1−Pa)/(2Pa−1)
. (3)
Thus to get the D(i, t) we should multiply D′(i′, t) with Pa, i.e.
D(i, t) = Pa
)−(1−Pa)/(2Pa−1)
. (4)
One can easily find that D(i, t) decreases rapidly as t increases and/or as i decreases provided 0.5 < Pa < 1. It is well
known that highly connected nodes, or hubs, play very important roles in the structural and functional properties of
growing networks [1, 2, 3]. The formation of hubs needs a long time to gain a large number of connections. As a
consequence, according to Eq. (4), a large portion of potential hubs are deleted during the network evolution. Thus
it can be expected that the introduction of node deleting has nontrivial effects on network structure. In the following
we show how network structure can be effected by the node deleting introduced in present model.
III. DEGREE DISTRIBUTION
The degree distribution p(k), which gives the probability that a node in the network possesses k edges, is a very
important quantity to characterize network structure. In fact, p(k) has been suggested to be used as the first criteria
to classify real-world networks [6]. Therefore it is necessary to investigate the effect of node deleting on the degree
distribution of networks firstly. Now we adopt the continuous approach [29] to give a qualitative analysis of p(k)
for our model with slight node deletion (i.e., when Pd is very small). Supposing that there is a node added into the
network at time step i′, and this node is still in the network at time t, let k(i′, t) be the degree of the i′th node at
time t, where t > i′. Then the increasing rate of k(i′, t) is
∂k(i′, t)
= Pam
k(i′, t) + 1
− (1− Pa)
k(i′, t)
, (5)
where
S(t) =
D′(i′, t)[k(i′, t) + 1] (6)
and the
′ denotes the sum of all i′ during the time step between 0 and t. It is easy to verify that the first term
in Eq. (5) is the increasing number of links of the i′th node due to the preferential attachment made by the newly
added node. The second term in Eq. (5) accounts for the losing of a link of the i′th node during the process of node
deletion, which happened with the probability k(i′, t)/N(t).
Firstly we solve for the S(t) and get
S(t) = (2Pa − 1) (2Pam+ 1) t (7)
(see the Appendix for details). Inserting Eq. (7) back into Eq. (5), one gets
∂k(i′, t)
Ak(i′, t) +B
, (8)
where
2P 2am− Pam+ Pa − 1
(2Pa − 1)(2Pam+ 1)
(2Pa − 1)(2Pam+ 1)
. (10)
When Ak +B > 0, the solution of Eq. (8) is
k(i′, t) =
(Am+B)
. (11)
Now, to get the probability p(k, t) that a randomly selected node at time t will have degree k, we need to calculate the
expected number of nodes Nk(t) with degree k at time t. Then the p(k, t) can be obtained from p(k, t) = Nk(t)/N(t),
where N(t) is the total number of nodes at time t. Let Ik(t) represent the set of all possible nodes with degree k at
time t, then one gets
p(k, t) =
Nk(t)
i∈Ik(t)
D(i, t). (12)
In the continuous-time approach, the number of nodes in Ik(t) is the number of i’s for which k 6 k(i, t) 6 k + 1,
and it is approximated to |∂k(i, t)/∂i|−1i=ik , where ik is the solution of the equation k(i, t) = k. To proceed with our
analysis, now we make the approximation that all nodes in Ik(t) have the same surviving probability D(ik, t) [44].
Under this mean-field approximation, Eq. (12) can be written as
p(k, t) =
D(ik, t)
∂k(i, t)
. (13)
From Eq. (11), we obtain
Ak +B
t. (14)
1 2 3 4 5 6 7 8 9 10
FIG. 1: Pmina [defined in Eq. (20)] as a function of m.
∂k(i, t)
= (Am+B)
t (Ak +B)
−(A+1)/A
. (15)
Inserting Eq. (14) back into Eq. (4) we get
D(ik, t) = Pa
Ak +B
)(A−B)/A
Inserting Eqs. (15) and (16) into Eq. (13), and noting that N(t) = (2Pa − 1)t, we get
p(k, t) =
2Pa − 1
(Am+B)
(B−A+1)/A
(Ak +B)
−(B+1)/A
, (17)
which is a generalized power-law form with the exponent
B + 1
= 2 +
Pam+ 1
2P 2am− Pam+ Pa − 1
. (18)
We point out again that equation (11) is only valid when Ak +B > 0, which translates into A > 0, i.e.
2P 2am− Pam+ Pa − 1 > 0. (19)
Considering that Pa > 0.5, Eq. (19) is satisfied when
Pa > P
(m− 1) +
m2 + 6m+ 1
. (20)
In Fig. 1, we plot Pmina as a function of m. One can see from Fig. 1 that the curve divides our model into two regimes.
(i) Pa > P
a : in this case Ak + B > 0 and equation (11) is valid. Thus, the degree distribution of the network
p(k) exhibits a generalized power-law form. (ii) Pa > P
a : In this case Ak + B > 0 can not be always satisfied
and equation (11) is not valid. Therefore, our continuous approach fails to predict the behavior of p(k), and we will
investigate it with numerical simulations. The Pmina (m), as one can find from Fig. 1, decreases with the increase of
In the power-law regime [Pa > P
a (m)], the behavior of p(k) is predicted by Eqs. (17) and (18), which are obtained
using a mean-field approximation [Eq. (13)]. One can easily verify that such approximation is only exact when Pa = 1,
in which case Eq. (18) turns into γ = 3 + 1/m, in good agreement with the results obtained from generalized BA
100 101 102 103
1.00 0.95 0.90
 power-law fit 
 pa=1.0
 pa=0.95
 pa=0.9
 pa=0.8
 pa=0.7
 pa=0.6
 pa=0.55 
 pa=0.51
exponential fit 
FIG. 2: Cumulative degree distribution P (k) for networks with system size N = 100000 and different values of Pa, in logarithmic
scales. The dash line is power-law fit for Pa = 1. The solid line is the exponential fit for Pa = 0.51. In the simulation, we
set m0 = m = 5 and each distribution is based on 10 independent realizations. Inset plots the power-law exponential γ as a
function of Pa. The continuous curve is according to the analytic result of Eq. (18), and circles to the simulation results.
model studied in Ref [28]. If Pmina (m) < Pa < 1, Eqs. (17) and (18) still give qualitative predictions for the model:
with slight node deletion, p(k) of the network is still power-law, and the exponential γ increases with the decrease of
Pa (inset of Fig. 2).
In remaining regime [Pa < P
a (m)], the limiting case is Pa → 0.5, in which the growth of network is suppressed (a
very slowly growing one). Similar non-growing networks have been studied, for example, for the Model B in Ref[30],
and the degree distribution has the exponential form. Here we conjecture that, in this regime, p(k) of our model
crossovers to an exponential form, which is verified by the numerical simulation results below.
Now we verify the above analysis with numerical simulations. In Fig. 2, we give the cumulative degree distributions
P (k) [3] of the networks with different Pa. As Pa gradually decreases from 1 to 0.5, Fig. 2 shows an interesting
transition process which can be roughly divided into three stages. (1) 0.9 6 Pa 6 1: In this stage, the model works in
the power-law regime and the power-law exponent γ increases as Pa decreases. Inset of Fig. 2 gives the comparison
between the value of γ predicted by Eq. (18) and the one obtained from numerical simulations. One sees that the
theory and the simulation results are in perfect agreement for Pa = 1. As Pa decreases, however, the agreement is only
qualitative and the deviation between theory and simulation becomes more and more obvious. As we have mentioned
above, such increasing deviation is due to the mean-field approximation used in the analysis. These results tell us that
slight node deletion does not cause deviation of the network from scale-free state, but only increases its power-law
exponent. Such robustness of power-low p(k) revealed here gives an explanation to the ubiquity of scale-free networks
in reality. It should be noted that a very similar robustness has also been found in the study of network resilience,
where simultaneously deleting of a portion of nodes was taken into account in static scale-free networks [24]. (2)
0.5 < Pa 6 0.6: In this stage, the model works in the regime of Pa < P
a (m). As one sees from Fig. 2, P (k) of
the network behaviors exponentially. This result indicates that with manifest node deletion, the network will deviate
from scale-free state and become exponential. (3) 0.6 < Pa < 0.9: In this stage, a crossover of the model from the
power-law regime to the exponential regime is found, in which the P (k) is no longer pure scale-free but truncated by
an exponential tail. As one can see, the truncation in P (k) increases as Pa decreases.
Besides the power-law degree distribution, it is now known that p(k) in real world may deviate from a pure power-
law form [18, 31, 32, 33, 34]. According to the extent of deviation, p(k) of real systems has been classified into three
groups [6]: scale-free (pure power-law), broad scale (power-law with a truncation), and single scale (exponential).
Many mechanisms, such as aging [6, 8, 9], cost [6], and information filtering [10], have been introduced into network
growth to explain these distributions. Here, the results of Fig. 2 indicate that a modified version of growth rule can
lead to all the three kinds of p(k) in reality, and it provides another explanation for the origin of the diversity of
degree distribution in real-world: such diversity may be a natural result of network growth.
0.0 2.0x104 4.0x104 6.0x104 8.0x104 1.0x105
-0.12
-0.10
-0.08
-0.06
-0.04
-0.02
 pa=1       pa=0.9
 pa=0.8    pa=0.7
 pa=0.6    pa=0.55
FIG. 3: Assortativity coefficient r plotted with network size N , for different Pa in the model. In the simulation, m0 = m = 5.
Result of each curve is based on 10 independent realizations.
IV. DEGREE CORRELATION
It has been recently realized that, besides the degree distribution, structure of real networks are also characterized
by degree correlations [19, 35, 36, 37, 38]. This translates into the fact that degrees at the end of any given edge in real
networks are not usually independent, but are correlated with one another, either positively or negatively. A network
in which the degrees of adjacent nodes are positively (negatively) correlated is said to show assortative (disassortative)
mixing by degree. An interesting observation emerging from the comparing of real networks of different types is that
most social networks appear to be assortatively mixed, whereas most technological and biological networks appear to
be disassortative. The level of degree correlation can be quantified by the assortativity coefficient r lying in the range
−1 6 r 6 1, which can be written as
i jiki −
(ji + ki)
(j2i + k
(ji + ki)
for practical evaluation on an observed network, where ji, ki are the degrees of the vertices at the ends of the ith edge,
with i = 1, . . . ,M [35]. This formula gives r > 0(r < 0) when the corresponding network is positively (negatively)
correlated, and r = 0 when there is no correlation [45].
Recently, Maslov et al [39] and Park et al [40] have proposed a possible explanation for the origin of such correlation.
They show for a network the restriction that there is at most one edge between any pair of nodes induces negative
degree correlations. This restriction seems to be an universal mechanism (indeed, there is no double edges in most
real networks), therefore, the authors of Ref. [40] conjecture that disassortativity by degree is the normal state of
affairs for a network. Although only a part of the measured correlation can be explained in the way of Ref. [40], this
universal mechanism does give a promising explanation for the origin of degree correlation observed in real networks
of various types.
It will be of great interest to discuss the effect of node deleting on degree correlation. In Fig. 3, we give the
assortativity coefficient r as a function of network size N , for different Pa in our model, for m = 5. As one sees
from Fig. 3, for each value of Pa, after a transitory period with finite-size effect, each r of networks tends to reach
a steady value. When Pa = 1, r → 0 as N becomes large. This result indicates that networks in the BA model are
uncorrelated, in agreement with results obtained in previous studies [35, 38]. When Pa < 1, nontrivial negative degree
correlations spontaneously develop as networks evolve. One can see from Fig. 3 that the steady value of r in the model
decreases with the decreasing Pa. In particular, when Pa 6 0.6, the value of r is about −0.1. These results indicate
that node deleting leads to disassortative mixing by degree in evolving networks. To make such relation more clear,
in Fig. 4, we plot r of networks in our model as a function of Pa, for different m. As the Fig. 3 indicates, when the
network size is larger than 40000, the assortativity coefficient r is nearly stable. So all results in Fig. 4 are obtained
from networks with N = 40000. Fig. 4 gives us the same relation between r and Pa shown in Fig. 3. What is more,
it tells us that for a given Pa, r will increase with the increasing m. The increment gets its maximum between m = 1
1.0 0.9 0.8 0.7 0.6 0.5
-0.20
-0.16
-0.12
-0.08
-0.04
 m=14
 m=15
FIG. 4: Assortativity coefficient r as a function of Pa, for different m in the model. In the simulation, N = 40000. Result of
each curve is based on 10 independent realizations.
0.0 2.0x104 4.0x104 6.0x104 8.0x104 1.0x105
-0.06
 pa=1      pa=0.9
 pa=0.8    pa=0.7
 pa=0.6    pa=0.55
FIG. 5: Assortativity coefficient r plotted with network size N , for different Pa in the randomly growing network model. In
the simulation, m0 = m = 5 and each curve is based on 10 independent realizations.
and other values. We point out that this is because when m = 1, the network has been broke up into small separate
components (see the following section). We can also find from Fig. 4 that the gap between different curves decreases
with the increasing m and the curves tend to merge at large m.
Now we give some explanations to the above observations. In the BA model, the network being uncorrelated is
the result of a competition between two factors: the growth and the preferential attachment (PA). On the one hand,
networks with pure growth is positively correlated. This is because the older nodes, also tending to be higher degree
ones, have a higher probability of being connected to one another, since they coexisted earlier. In Fig. 5, we compute
the assortativity coefficient r of a randomly growing network, which grows by the growth rule of BA-type, while the
newly added nodes connect to randomly chosen existing ones. As one can see from Fig. 5 that pure growth leads to
positive r. On the other hand, the introduction of PA makes the connection between nodes tend to be negatively
correlated, since newly added nodes (usually low degree ones) prefer to connect to highly connected ones. Then
degree correlation characteristic of the BA model is determined by this two factors. In Fig. 6, we plot the average
degree of the nearest neighbor < k >nn as a function of k in the BA model. It is found that nodes with large k show
no obvious biases in their connections. But there is a short disassortative mixing region when k is relatively small
(also reported in Ref. [41], see Fig.1a therein). Such phenomenon can be explained by the effect of these two factor:
10 20 30 40 50 60 70 80 90 100
FIG. 6: Average degree of the nearest neighbor as a function of k for the BA model. In the simulation, N = 10000 and
m = m0 = 5. Result of each curve is based on 1000 independent realizations.
1.0 0.9 0.8 0.7 0.6 0.5
1.0 0.9 0.8 0.7 0.6 0.5
FIG. 7: The relative size of the largest component S as a function of Pa for m = 2, 3, 4, 5. Inset gives the same curve for m = 1.
In the simulations, N = 100000. All results are based on 10 independent realizations.
Growth together with PA makes nodes with large k equally connect to both large and small degree nodes, and the
latter makes nodes with small degree be disassortatively connected. Now, we introduce node-deletion. According to
Eq. (4), depression of the growth of large-degree nodes also decreases the connections between them, therefore makes
the correlation negative. We also investigate the effect of node deleting on the r of the randomly growing network,
and obtained similar results. As one sees from Fig. 5, depression of connections between higher degree nodes causes
the network less positively correlated, and with stronger node-deletion, negatively correlated. Finally, with regard to
the effect of m in this relation (Fig. 4), larger m means more edges are established according to the PA probability
Eq. (1). We conjecture that the orderliness of newly added nodes connecting to large degree nodes will be weakened
by the increasing randomness as m becomes larger, thus leading to a less negative correlation. Such randomness can
not always increase and, as we see from Fig. 4, for large m, e.g., m ≥ 14, the curves tend to merge together.
V. SIZE OF GIANT COMPONENT
In a network, a set of connected nodes forms a component. If the relative size of the largest component S in a
network approaches a nonzero value when the network is grown to infinite size, this component is called the giant
component of the network [1, 2, 3]. In most previously studied growing models [1, 2, 3], due to the BA-type growth
rule they adopted, there is only one huge component in the network, i.e., S ≡ 1. In this extreme case the network
gains a perfect connectedness. The opposite case of S = 1 is the extreme of S = 0, in which case the network,
made up of small components, exhibits no connectedness. Experiments indicate that some real networks seem to
lie in somewhere between these two extreme: they contain a giant component as well as many separate components
[2, 3, 42, 43]. For example, According to Ref.[42], in May of 1999, the entire WWW, containing 203 × 106 pages,
consisted of a giant component of 186× 106 pages and the disconnected components (DC) of about 17× 106 pages. In
general, the introduction of node deletion in our model will cause the emergence of separate components even isolated
nodes in the network. What we interest here is the connectedness of the network. In Fig. 7 we plot the relative size
of the largest component S in the model, as a function of Pa, for m = 2, 3, 4, 5, where m is the number of edges
generated with the adding of a new node. One sees from Fig. 7 that for any 0.5 < Pa ≤ 1, a giant component can be
observed in the model if m > 1. In addition, for the same Pa, S increase as the increase of m. While when m = 1, the
network is found to be broke up into separate components if Pa < 1. For example, when Pa = 0.9, S of the network
with N = 100000 rapidly drops to 0.034. Inset of Fig. 7 gives the S Vs Pa curve for m = 1. These results indicate
that node deleting does not destroy the connectedness of a growing network so long as the increasing rate of edges is
not excessively small.
VI. AVERAGE DISTANCE BETWEEN NODES
Now we study the effect of node deletion on networks’ average distance L between nodes. Here the distance between
any two nodes is defined as the number of edges along the shortest path connecting them. It has been revealed that,
despite their often large size, most real networks present a relatively short L, showing the so-called small-world effect
[1, 2, 3, 4]. Such an effect has a more precise meaning: networks are said to show the small-world effect if the value
of L scales logarithmically or slower with network size for fixed mean degree. This logarithmic scaling can be proved
for a variety of network models [1, 2, 3]. As we have demonstrated in Section V, node deleting does not destroy the
connectedness of the network in our model for any m > 1, since there is always a giant component exists. Here in
our simulation, we calculate L of the giant component of the network in our model using the burning algorithm [3].
In Fig. 8, we plot L as a function of network size N , for different Pa in our model. As one can see from the figure,
for any 0.5 < Pa ≤ 1, a logarithmic scaling L ∼ lnN is obtained, while the proportional coefficient increases with
the decrease of Pa. Furthermore, for a given N , L increases with the decrease of Pa. These results tell us that node
deleting will weaken but not eliminate the small-world effect of a growing network.
VII. CLUSTERING
Finally, we investigate the effect of node deletion on network’s cluster coefficient C, which is defined as the average
probability that two nodes connected to a same other node are also connected. For a selected node i with degree ki
in the network, if there are Ei edges among its ki nearest neighbors, the cluster coefficient Ci of node i is defined as
ki (ki + 1)
. (22)
Then the clustering coefficient of the whole network is the average of all individual Ci. In Fig. 9, we plot C of the
giant component in the network as a function of network size N , for different Pa. As one sees from Fig. 9, for each Pa,
the clustering coefficient C of our model decreases with the network size, following approximately a power law form.
Such size-dependent property of C is shared by many growing network model [1, 2, 3]. Moreover, as Fig. 9 shows,
for the same network-size N , C decreases as Pa decreases. The results of Fig. 9 indicate that node deleting weakens
network’s clustering.
VIII. CONCLUSION
In summary, we have introduced a new type of network growth rule which comprises of adding and deleting of nodes,
and proposed an evolving network model to investigate effects of node deleting on network structure. It has been
102 103 104 105
 Pa=1
 Pa=0.9
 Pa=0.8
 Pa=0.7
 Pa=0.6
 Pa=0.55
 Pa=0.51
FIG. 8: Average distance L of the giant component in the network as a function of network size N , for different Pa in the
model. The chose of some parameters: m0 = m = 5. These curves are results of 10 independent realizations.
102 103 104 105
 Pa=1
 Pa=0.9
 Pa=0.8
 Pa=0.7
 Pa=0.6
 Pa=0.55
FIG. 9: Cluster coefficient C of the giant component in the network as a function of network size N , for different Pa. In the
simulation we set m0 = m = 5. These curves are results of 10 independent realizations.
found that, with the introduction of node deleting, network structure was significantly transformed. In particular,
degree distribution of the network undergoes a transition from scale-free to exponential forms as the intensity of node
deleting increased. At the same time, nontrivial disassortative degree correlation spontaneously develops as a natural
result of network evolution in the model. We also have demonstrated that node deleting introduced in our model does
not destroy the connectedness of a growing network so long as the increasing rate of edge is not excessively small. In
addition, it has been observed that node deleting will weaken but not eliminate the small-world effect of a growing
network. Finally, we have found that generally node deleting will decrease the clustering coefficient in a network.
These nontrivial effects justify further studies of the effect of node deleting on network function [3], which include
topics such as percolation, information and disease transportation, error and attack tolerance, and so on.
Acknowledgments
The authors thank Doc. Ke Hu for useful discussions. This work is supported by the National Natural Science
Foundation of China, Grant No. 10647132, and Natural Science Foundation of Hunan Province, China, Grant No.
00JJY6008.
APPENDIX: THE CALCULATION OF S(T )
To get S(t), we multiply both sides of Eq. (5) by D′(i′, t) and sum up all i′ between 0 and t:
∂k(i′, t)
D′(i′, t) = Pa(m− 1)−
1− Pa
(2Pa − 1)t
S(t) + 1. (A.1)
To get the above equation we have used the definition of S(t) [Eq. (6)] and the following equation:
D′(i′, t) =
D(i, t)di. (A.2)
The left-hand side of Eq. (A.1) can be simplified as:
∂ {[k(i′, t) + 1]D′(i′, t)}
[k(i′, t) + 1]
∂D′(i′, t)
[k(i′, t) + 1]D′(i′, t)
− [k(t, t) + 1]D(t, t)
[k(i′, t) + 1]D′(i′, t)
Pa − 1
(2Pa − 1)t
Substituting the above expression in Eq. (A.1), and noting that k(t, t) = m and D(t, t) = Pa, we get
∂S(t)
2(Pa − 1)
(2Pa − 1)t
S(t) + 2Pam+ 1.
The solution to the above equation is
S(t) = (2Pa − 1) (2Pam+ 1) t.
[1] R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002).
[2] S. N. Dorogovtsev, and J. F. F. Mendes, Adv. Phys. 51, 1079 (2002).
[3] M. E. J. Newman, SIAM Review 45, 167 (2003).
[4] D. J. Watts and S.H. Strogatz, Nature (London) 393, 440 (1998).
[5] A.-L. Barabási and R. Albert, Science, 286, 509 (1999).
[6] L. A. N. Amaral, A. Scala, M. Barthélémy and H. E. Stanley, Proc. Natl. Acad. Sci. U.S.A. 97, 11149 (2000).
[7] R. Albert and A.-L. Barabási, Phys. Rev. Lett. 85, 5234 (2000).
[8] S. N. Dorogovtsev and J. F. F. Mendes, Phys. Rev. E 62, 1842 (2000).
[9] K. Klemm and V. M. Egúıluz, Phys. Rev. E 65, 036123 (2002).
[10] S. Mossa, M. Barthélémy, H. E. Stanley and L. A. N. Amaral, Phys. Rev. Lett. 88, 138701 (2002).
[11] Z. Liu, Y.-C. Lai and N. Ye, Phys. Rev. E 66, 036112 (2002).
[12] S. Fortunato, A. Flammini and F. Menczer, Phys. Rev. Lett. 96, 218701 (2006).
[13] W. Jeżewski, Phys. Rev. E 66, 067102 (2002).
[14] R. Xulvi-Brunet and I. M. Sokolov, Phys. Rev. E 66, 026118 (2002).
[15] A. Vázquez, Phys. Rev. E 67, 056104 (2003).
[16] Tao Zhou, Gang Yan and B.-H. Wang, Phys. Rev. E 71, 046141 (2005).
[17] Wen-Xu Wang, Bo Hu, Tao Zhou, Bing-Hong Wang, and Yan-Bo Xie, Phys. Rev. E 72, 046140 (2005).
[18] J. A. Dunne, R. J. Williams and N. D. Martinez, Proc. Natl. Acad. Sci. U.S.A. 99, 12917 (2002).
[19] K.-I. Goh, B. Kahng and D. Kim, Phys. Rev. Lett. 88, 108701 (2002).
[20] Q. Chen et al., The origins of power laws in Internet topologies revisited, in Proceedings of the 21st Annual Joint Conference
of the IEEE Computer and Communications Societies, IEEE Computer Society (2002).
[21] A. Vázquez, R. Pastor-Satorras1 and A. Vespignani, Phys. Rev. E 65, 066130 (2002).
[22] S. Lawrence and C. Lee Giles, Science, 280, 98 (1998).
[23] B. A. Huberman and L. A. Adamic, Nature (London), 401, 131 (1999).
[24] R. Albert, H. Jeong and A.-L. Barabási, Nature (London) 406, 378 (2000).
[25] S. N. Dorogovtsev and J. F. F. Mendes, EuroPhys. Lett. 52, 33 (2000).
[26] J. L. Slater, B. D. Hughes and K. A. Landman, Phys. Rev. E 73, 066111 (2006).
[27] N. Sarshar and V. Roychowdhury, Phys. Rev. E 69, 026101 (2004).
[28] S. N. Dorogovtsev, J. F. F. Mendes and A. N. Samukhin, Phys. Rev. Lett. 85, 4633 (2000).
[29] S. N. Dorogovtsev and J. F. F. Mendes, Phys. Rev. E 63, 056125 (2001).
[30] A.-L. Barabási, R. Albert and H. Jeong, Physica A 272, 173 (1999).
[31] M. E. J. Newman, Computer Physics Communications 147, 40 (2002).
[32] J. Camacho, R. Guimerà and L. A. N. Amaral, Phys. Rev. Lett. 88, 228102 (2002).
[33] M. E. J. Newman, S. Forrest and J. Balthrop, Phys. Rev. E 66, 035101 (2002).
[34] H. Jeong, S. P. Mason, A.-L. Barabási and Z. N. Oltvai, Nature (London), 411, 41 (2001).
[35] M. E. J. Newman, Phys. Rev. Lett. 89, 208701 (2002).
[36] R. Pastor-Satorras1, A. Vázquez and A. Vespignani, Phys. Rev. Lett. 87, 258701 (2001).
[37] S. Maslov and K. Sneppen, Science, 296, 910 (2002).
[38] M. E. J. Newman, Phys. Rev. E 67, 026126 (2003).
[39] S. Maslov, K. Sneppen and A. Zaliznyak, e-print cond-mat/0205379.
[40] J. Park and M. E. J. Newman, Phys. Rev. E 68, 026112 (2003).
[41] Huang Zhuang-Xiong, Wang Xin-Ran and Zhu Han, Chinese Physics 13, 273 (2004).
[42] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener, in Proceedings of
the 9th WWW Conference (Elsevier, Amsterdam, 2000), p. 309.
[43] S. N. Dorogovtsev, J. F. F. Mendes and A. N. Samukhin, Phys. Rev. E 64, 025101(R) (2001).
[44] It seems that this is not a very good approximation, since investigations indicate that values of (∂D(i, t)/∂i) |i=ik are large
and increase rapidly with the decrease of Pa. Thus the analysis here is a qualitative one and only suit for the condition of
slight node deletion in the model.
[45] Another way to represent degree correlation is to calculate the mean degree of the nearest neighbors of a vertex as a function
of the degree k of that vertex. Although such way is explicit to characterize degree correlation for highly heterogeneously
organized networks, for less heterogeneous networks (this is the case in the proposed model when the intensity of node
deleting increases, see Fig. 2), it may be very nosy and difficult to interpret. So here we adopt the assortativity coefficient
r to characterize degree correlation in the model.
http://arxiv.org/abs/cond-mat/0205379
	INTRODUCTION
	THE MODEL
	DEGREE DISTRIBUTION
	DEGREE CORRELATION
	SIZE OF GIANT COMPONENT
	AVERAGE DISTANCE BETWEEN NODES
	CLUSTERING
	CONCLUSION
	Acknowledgments
	THE CALCULATION OF S(T)
	References
