TELKOM
NIKA
, Vol. 11, No. 10, Octobe
r 2013, pp. 6
232 ~ 6
239
ISSN: 2302-4
046
6232
Re
cei
v
ed Ap
ril 20, 2013; Revi
sed
Jul
y
1
6
, 2013; Acce
pted Jul
y
25,
2013
Efficiency
Analy
s
is of Scal
e-free Network Cascading Failures
under Different T
y
pes of Attacks
Yuanni Liu*, Hong Ta
ng, Guofeng Zh
ao, Yunpeng
Xiao, Chuan
Xu
T
he School of Commun
i
cati
o
n
and Inform
ati
on Eng
i
n
eeri
n
g
of ChongQi
ng
Univers
i
t
y
of Posts and
T
e
lecommunic
a
tions
No. 2, Chon
g
w
e
n
R
oad,N
a
n
an district, 400
065, Ch
on
gQin
g, Chin
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: liu
yn@c
qu
pt.edu.cn
A
b
st
r
a
ct
Netw
ork casca
din
g
fail
ure c
a
n resu
lt in
a c
ong
es
tio
n
reg
i
me
w
i
th de
gra
datio
n i
n
the
netw
o
rk
perfor
m
a
n
ce. W
hen casca
d
i
ng fai
l
ure
oc
curring,
the
netw
o
k traffic w
ill be rero
uted to byp
a
ss
ma
lfuncti
oni
ng
routers, eve
n
t
ually
l
e
a
d
in
g
to an av
al
anc
he of ov
erlo
ad
s on oth
e
r ro
uters that are
no
t
equ
ipp
ed to
ha
ndl
e extra traffi
c, w
h
ich Lots o
f
failure
mod
e
l
s
have
be
en c
onstructed t
o
i
n
vestig
ate h
o
w
a
sm
all shock can trigger avalanches
mecha
n
i
sms
affecting
a cons
ider
ab
le
fraction of the
netw
o
rk. In thi
s
pap
er, based o
n
our AHP netw
o
rk cascadin
g
mo
del, w
e
have esti
mated
how
the efficiency w
ill be affected
w
hen coefficie
n
ts of K, S, T chang
ed, w
e
find the
fact
that the network e
fficiency
of BA netw
o
rk is
deter
mi
ned
by its attacked types, and the efficiency is
l
a
rg
ely infl
uenc
ed
by the attacked
types of K and
S,
and u
n
d
e
r the
same
nu
mb
er
of failure no
d
e
, the efficienc
y under attack
s of types T
a
nd I are relativ
e
l
y
hig
her than that of
the efficiency und
er attacks of
types
S
and
K
, a
nd th
e i
m
p
o
rtance I
is l
a
rg
el
y
deter
mi
ned
by
the pro
portio
n
of T
,
w
hen the
nod
e fail
ur
e n
u
mber is
equ
al
, the high
er pr
oporti
on of T
,
the
hig
her efficienc
y it is
under I
type attacks.
We also
tabled
some pro
posa
l
s for reducing
the da
mag
e
tha
t
the netw
o
rks suffered fro
m
the cascad
i
n
g
fai
l
ures.
Ke
y
w
ords
:
no
de de
gre
e
distr
i
buti
on, compl
e
x n
e
t
w
ork, attack, net
w
o
rk efficienc
y
Copyrig
h
t ©
2013
Univer
sitas Ahmad
Dahlan. All rights res
e
rv
ed.
1. Introduc
tion
In many real netwo
rks, on
e or a few no
des
o
r
edg
es
failure
s, cau
s
ed by rand
om
failures
or delibe
r
ate
attacks, will eventually l
eadin
g
to a
con
s
id
era
b
le
number of node
s or net
wo
rk
cra
s
h
e
s, which is call
ed ca
scadin
g
failures, and
the
r
e
have bee
n a lot of resea
r
ch
about network
attacks an
d the prote
c
tion
appro
a
che
s
[1]. The ty
pical example is the No
rth American Blacko
ut.
A great d
eal
of efforts h
a
d
been
devote
d
into t
he im
provem
ent of
netwo
rk reli
a
b
ility, but larg
e-
scale ca
scad
ing netwo
rk failure
s o
c
cur const
antly
.
Therefore, it is nec
essa
ry
to prevent and
control the cascadi
ng failure
s in the networks,
and explore the e
fficiency of the netwo
rk un
der
different types of attacks.
Curre
n
t networks
su
ch a
s
the Wo
rld
Wi
de Wed
[1-2], the Internet
,
airpla
ne
s co
nne
cti
o
n
netwo
rks
, an
d some bi
olo
g
ical sy
stem
s, are different
from rand
om
networks an
d all share the
same
prope
rty of having a
pow
er-la
w
d
egre
e
di
strib
u
tion
k
k
P
~
)
(
with a
n
expone
nt
λ
that
rang
es
betwe
en 2 a
nd 3.
Networks
wit
h
po
we
r-la
w
degree di
strib
u
tion have b
e
en nam
ed
scale-
free networks, which carry with
them a well-recogni
zed
stren
g
th-toleran
ce of random failu
res.
But they are particula
rly susceptibl
e
to failure of
sp
e
c
ific no
de
s that are highly
con
n
e
c
ted an
d if
such rem
o
val
s
occur,
the network will
disint
egrate rapidly[3-5].
In
fact, although most failures
emergen
ce a
nd dissolve locally, largel
y unnoticed
by the rest of the world, a few trigger
avalan
che m
e
ch
ani
sms th
at can have
e
ffects over th
e entire net
works.
In this pa
per, we an
alyze
d
the efficie
n
c
y
of the BA netwo
rk und
er different types o
f
attacks a
s
th
e alteratio
n
o
f
node failu
re
rate. Based
on the initial
experim
ent, we explo
r
e
d
how
the efficiency
of BA network will be in
fluenced
by different types of attacks
whe
n
the node
importa
nce
I
wa
s cal
c
ul
ate
d
by
K, S
,
T
u
nder fou
r
cases of co
efficie
n
t.
The re
main
d
e
r of this p
a
per i
s
organi
zed a
s
follo
ws: In the n
e
xt section,
we will
introduce the related work; in section 3,
we will
show how to set up the elements coefficients in
our AHP m
o
del [6]; in secti
on 4, we
will
present t
he
si
mulation results. Finally, the conclusion is
dra
w
n in secti
on 5.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
6233
Efficiency An
alysis of Scal
e-fre
e
Net
w
ork Ca
scadi
ng
Failures u
nde
r Differe
nt … (Yuan
ni Liu)
2. Related
w
o
rk
Lots of inte
re
st ha
s bee
n focu
se
d on th
e studi
e
s
of t
he consequ
e
n
ce
s of different types
of failure
s b
o
th on scale
-
free m
odel
s and on real
-wo
r
ld n
e
two
r
ks [7–9] to prote
c
t existi
ng
netwo
rks, an
d to locate th
e mo
st criti
c
a
l
node
s in
order to
red
u
ce
their
criticality. The rob
u
st
of
netwo
rks to the rem
o
val o
f
nodes o
r
arcs, du
e eith
e
r
to rand
om brea
kd
owns
or to intentio
nal
attacks, ha
s been
studie
d
in [10–13], whi
c
h have f
o
cu
se
d only on the static
prop
ertie
s
of the
netwo
rk
sho
w
ing that th
e removal o
f
a
group o
f
nodes alto
gether
can
have impo
rtant
con
s
e
que
nce
s
. In [11], Pa
olo pro
p
o
s
ed
a ca
scadin
g
netwo
rk m
o
d
e
l to sho
w
ho
w the network is
influen
ced by
network failu
res.
In Ref. [11],
Cru
c
itti propo
sed a ca
scad
ing
netwo
rk model to sho
w
how the network is
influen
ced by
netwo
rk failu
res. In hi
s m
odel ea
ch
no
de is
cha
r
a
c
terized by a g
i
ven cap
a
city
C
i
according to t
he toleran
c
e
para
m
eter
, and every n
o
d
e
ha
s the sa
me toleran
c
e
para
m
eter
whi
c
h i
s
det
e
r
mine
d by th
e nod
e imp
o
rtance.
He
also appli
ed the
model to
the
Italian ele
c
tri
c
power grid [6].
In Crucitti’s
ca
scadin
g
model, a gene
ric
co
mmuni
cation/ tran
sport netwo
rk can be
rep
r
e
s
ente
d
by a weighte
d
undirecte
d
grap
h
G
, with
N
node
s and
M
arcs, and
G
is described by
an
N
×
N
adj
ace
n
cy matri
x
[
e
ij
]
.
If there is an a
r
c b
e
t
ween n
ode
i
and no
de
j
, the entry
e
ij
is t
h
e
value, rangin
g
in (0,1], attach
ed to the
arc; othe
rwi
s
e
e
ij
=0. The
e
ij
is a value
of the path along
the arc, an
d
the sm
aller
e
ij
is, the lon
g
e
r it takes to
excha
nge
a
unitary pa
cke
t
of informati
o
n
along the arc between
i
and
j
. Initially
,
at time
t
=0, for all the existing arcs, the
e
ij
=1, mean
ing
that all the transmi
ssion li
nes a
r
e fun
c
tioning e
qually
. The model
con
s
i
s
ts of a rule for the ti
me
evolution of [
e
ij
] that mimics the dyn
a
m
ics of flow
redi
strib
u
tion
following the
brea
kdo
w
n
of a
node.
In ord
e
r to
de
fine the n
e
twork efficie
n
cy
[10
], it assu
mes th
at any
cou
p
le of
nod
es ta
ke
s
the most efficient path to
communi
cate
with ea
ch
oth
e
r, and th
e e
fficiency of a
path is th
e so-
calle
d harmo
nic compo
s
iti
on of the effi
cien
cie
s
of the com
pone
nt arcs. The
ij
is
defined a
s
th
e
efficien
cy of the mo
st efficient path bet
wee
n
i
and
j
, and matrix [
ij
] is cal
c
ulate
d
by means of
the algo
rithm
s
u
s
ed i
n
Ref. [14]. With the kn
ow
l
edg
e
of the path ef
ficien
cy between a
n
y co
up
le
of the node
s
i
and
j
, we ca
n cal
c
ulate th
e averag
e efficien
cy of the netwo
rk by
G
j
i
ij
N
N
G
E
)]
1
(
/[
)
(
, which i
s
a m
easure of the
perfo
rman
ce
of
G
at a given time.
C
i
: the cap
a
ci
ty defined as
the ma
ximum
load that nod
e can h
andl
e.
L
i
(t)
: the load
on node
i
at time
t
, which is the total numbe
r of most efficient pa
ths pa
ssi
ng
throug
h
i
at ti
me
t
[11].
The cap
a
ci
t
y
C
i
of node
i
is proportional to its initial load:
L(0)
,
N
i
L
C
i
i
,...,
2
,
1
),
0
(
, where
1
is th
e tolera
nce p
a
ram
e
ter of t
he net
work.
The initial
removal of a
node, simul
a
ting the bre
a
kd
own of
an Internet ro
uter, start
s
the dynami
c
s of
redi
strib
u
tion
of flows o
n
the netwo
rk. Th
e initia
l remo
val of a node,
simulatin
g
the bre
a
kdo
w
n
of
an Internet ro
uter, start
s
the dynamics o
f
redist
ri
butio
n of flows on
the netwo
rk.
The rem
o
val of a
node
will ch
ange the m
o
st efficient
paths b
e
twe
en the nod
e
pairs
and
consequ
ently the
redi
strib
u
tion
of the loads, resultin
g overl
oad
s on som
e
node
s. At each time
t
the
efficiency of an
arc i
s
chang
e
d
by the following iterative rule:
i
i
ij
i
i
i
i
ij
ij
C
L
e
C
t
L
C
t
L
e
t
e
);
0
(
)
(
;
)
(
)
0
(
)
1
(
(1)
whe
r
e
j
i
s
all
the first n
e
igh
bors of
i
. Foll
owing rul
e
(1), if at time
t
a nod
e
i
wa
s c
o
ng
es
te
d
,
th
e
efficiency of all the edge
s
passing through it will be reduced,
as a
result, the traffic (informati
on)
will take the
new m
o
st eff
i
cient p
a
ths
as the
altern
ative one, which i
s
a
softer, and i
n
so
me
degree, a mo
re re
alisti
c sit
uation. But his model h
a
s
some limit
s:
1) It will be
a waste to assi
gn every node with the same tolerance param
e
t
er
, when the
network
res
o
urce is
finite.
Evaluation Warning : The document was created with Spire.PDF for Python.
6234
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 10, Octobe
r 2013 : 623
2
– 6239
2)
Node
impo
rtance
shoul
d
take a
c
cou
n
t to multi-
ele
m
ent inste
ad of
the sin
g
le el
ement of n
o
d
e
degree.
In [6], we pro
posed a
n
imp
r
oved
re
sou
r
ce all
o
cation
model b
a
sed
on AHP
[15]
to analy
sis
the efficien
cy of the netwo
rk
whe
n
it is unde
r casca
d
i
ng failures
caused by different type
s o
f
attacks.
The contri
bution
s
of
our
model are mostly as follows:
1) We all
o
cated node
s wit
h
different toleran
c
e p
a
ra
meter
α
ba
se
d on the nod
e importan
c
e
I to
allocate the Ci
2) The impo
rtance I of a n
ode is determined by
three element
s: node de
gre
e
K; the number of
the sho
r
te
st paths S throu
g
h
a node; the
numbe
r
of the sho
r
te
st paths T thou
gh the neig
hbo
r
of a node.
3) We fixed every element
a weig
ht to compute I by AHP theory.
In our impro
v
ed model, first we
will assume that the netwo
rk reso
urce
C
all
is
finite
,
whi
c
h i
s
a
re
alistic
assu
m
p
tion in th
e
desi
gn of
an
infra
s
tru
c
ture network, si
nce th
e
cap
a
c
ity
can
not be infi
nitely large b
e
ca
use it is limited
by the co
st. Secondl
y, we will assign every nod
e
with the capa
city by
its importan
c
e
I
i
determin
ed by three eleme
n
ts, and in th
is way, different
node will be chara
c
te
rized by different to
leran
c
e pa
ra
meter
. The
more impo
rta
n
t of the node,
the more re
source i
s
allo
cated, whi
c
h i
s
con
s
iste
nt with the a
c
tu
al situatio
n in
the network. The
corre
c
tne
s
s of the model
has be
en p
r
oved in Cru
c
itti’s pap
er.
Since we o
n
ly altered the
para
m
eter
by changi
ng th
e way of the resou
r
ce allo
ca
tion in thi
s
model, which
will not affect
the validity of
the origin
al cascadi
ng mo
del.
In our model, we have con
s
ide
r
ed thre
e
diffe
rent elements to determine the imp
o
rtan
ce
I
i
of a node
i
:
1) The d
egre
e
K
i
, i.e., the
numbe
r of ed
ges the n
ode
has.
2)
S
i
: the nu
mber
of the
shorte
st
path
s
(over
all pairs of node
s
of the network) t
hat pa
ss th
ro
ugh
node
i
.
3)
T
i
: the num
ber of the sho
r
test path
s
th
at
pass throu
gh all the nei
ghbo
rs of no
d
e
i
.
Weig
hts of th
e three
elem
ents too
k
a
c
count to dete
r
mine the
Ii
are cal
c
ulate
b
y
AHP.
With the preferen
ce of alt
e
rnative on
e
a
ch
crit
e
r
ion,
AHP can d
e
r
ive the app
ropriate
weig
h
t
fo
r
every eleme
n
t, and calcula
t
e the overall importa
nce
I
i
of node
i
in Eq.(2).
i
i
i
i
T
w
S
w
K
w
I
3
2
1
(2)
Then the
C
i
o
f
every node can b
e
cal
c
ul
ated by
Eq.
(2) and
(3), an
d the toleran
c
e
para
m
eter of
a node i
s
Eq.
(4)
)
)
0
(
(
)
0
(
j
j
all
N
j
j
i
i
i
L
C
I
I
L
C
(3)
)
0
(
i
i
i
L
C
(4)
Based
on ou
r AHP netwo
rk cascadi
ng
model, we ha
ve investigat
ed ho
w the tolera
nce
para
m
eter
influenced the
efficien
cy in BA and ER networks, and
dra
w
co
ncl
u
si
ons a
s
follo
ws:
(1) In
order to
prote
c
t net
work from
ran
d
o
m attack
, th
e nod
es
sh
ou
ld be di
strib
u
ted with
different
to
le
r
a
nc
e
pa
ra
me
te
r
.
(2) As the
real netwo
rk follows the power-la
w
in BA network, assig
n
different tole
ran
c
e
para
m
eter
to the node ma
y improve the
efficiency of the network.
(3)
The impo
rtan
ce of node
i
in Ref. [6] is
c
a
lc
ulated by
i
i
i
i
T
S
K
I
2583
.
0
6370
.
0
1047
.
0
,
and the sim
u
lation re
sult
s sh
ows tha
t
the
maximum dama
g
e
to the network is the
delibe
r
ately attack of node
removal ba
se
d on type
K
,
whi
c
h is large
r
than the typ
e
s of
T
and
S
. In addition, under the n
ode rem
o
val based on
I
, the netwo
rk efficien
cy will be highe
r than
that of Crucitt
i’s model
if o
n
ly the weigh
t
of
K
will not be equal to 1. Therefo
r
e, in our mod
e
l,
the network e
fficiency affe
cted by the
ch
ange
of
the e
l
ements’
wei
g
hts will
be al
ways
high
er
than that of the origin
al mo
del.
In this pape
r, we will find h
o
w the effici
e
n
cy will be
affected
whe
n
coefficient
s of
K, S, T
c
h
an
g
ed
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
6235
Efficiency An
alysis of Scal
e-fre
e
Net
w
ork Ca
scadi
ng
Failures u
nde
r Differe
nt … (Yuan
ni Liu)
3. Computin
g the coe
ffic
i
ents
We have described the AHP conf
iguration process
in [6], in
this section , first we will
give a
sho
r
t d
e
scriptio
n ag
ain, and
then
we
will se
t up
four g
r
o
u
p
s
of different p
a
r
amete
r
s for t
he
corre
s
p
ond
en
t
K
,
S
,
T
to calculate the n
o
de impo
rtan
ce
I
.
3.1 The AHP configur
atio
n proces
s
AHP is a
well
-studi
ed, wi
d
e
ly-appli
ed te
c
hni
que i
n
m
u
lti-criteria
de
cisi
on a
nalysi
s
[15], a
field in deci
s
i
on theory. According to th
e deci
s
io
n make
r’s p
r
efe
r
ences
with re
gard to indivi
dual
element
[1
5],
the AHP can provide a sim
p
le, yet syst
ematic way to find the overall best weig
ht
for all eleme
n
t
s.
First, AHP
wil
l
model th
e d
e
ci
sion
probl
em a
s
a
de
ci
sion
hie
r
arch
y. Then, it wil
l
perfo
rm
pair-wi
se
co
mpari
s
o
n
s
of all eleme
n
ts,
and it will
s
p
e
c
ific the
pref
e
r
en
ce of o
ne
element ove
r
the
other u
s
ing a
numbe
r for each com
p
a
r
i
s
on. The
sc
a
l
e from 1 to 9 has p
r
oven
to be the most
approp
riate
[1
5], in which, whe
n
com
paring crite
r
ia
r
to
q
, 1 means
r
and
q
are e
qually pre
f
e
rre
d
,
3 mean
s
wea
k
preferen
ce
for
r
ove
r
q
, 5
m
ean
s st
ron
g
prefe
r
en
ce,
7 mean
s d
e
m
onstrated
(ve
r
y
stron
g
)prefe
rence, 9 mea
n
s extr
em
e p
r
eferen
ce. Th
e inverse va
l
ues1/3, 1/5, 1/7 and 1/9
are
use
d
in the reverse order
of the compa
r
iso
n
(
q
vs
.
r
). Intermediat
e values (2, 4, 6, 8) may be
use
d
whe
n
compromise is in order. As we do in Tabl
e 1, where el
ements a
r
e compa
r
ed ba
sed
on their imp
o
rtance.
Although
the
entire
m
a
trix contai
ns of
9
prefe
r
en
ce
s, to co
mputed
the
I
,
we only need
to
spe
c
ify 3 of them–
‘
K
vs.
S
’,
‘
K
vs.
T
’, and ‘
S
vs.
T
’. the weights of all elem
ents, whi
c
h a
r
e
comp
uted fro
m
the pri
n
ci
pal eig
envector of the p
r
eferen
ce
mat
r
ix. With the
prefe
r
en
ce
of
alternative o
n
each criteri
on, AHP can
derive
the a
ppro
p
ri
ate weight for eve
r
y element, a
nd
cal
c
ulate the
overall imp
o
rt
ance
I
i
of node
i
in Eq.(2).
Then the
Ci
of every nod
e ca
n be
cal
c
ulate
d
by
Eqs. (2
) an
d (3), and th
e tolera
nce
para
m
eter of
a node i
s
Eq. (4).
3.2 Compu
t
ing the co
efficients
In order to find out how the alteration of t
he
coefficient
s will affect
the network efficiency
unde
r differe
nt types of attacks, first, we will set
K
,
S
,
T
with equal importan
c
e
to determine
the
node imp
o
rta
n
ce
I
as in
co
mpari
s
o
n
matrix 1
.
Table 1
.
Co
m
pari
s
on m
a
tri
x
1
Elements
K S
T
w
e
ights
K
1 1
1
0.3333
S
1 1
1
0.3333
T
1 1
1
0.3333
In comp
ari
s
o
n
matrix 1, we assum
e
th
at a
ll the ele
m
ents a
r
e e
q
ually prefe
r
re
d, so the
corre
s
p
ond
en
t value of
I
can be cal
c
ul
ated as
I
=0.333
3
K
+0.
3
3
3
3
S
+0.3333
T
.
S
e
con
d
,
we make
K
is the most important element
to determine the node importan
c
e
I
,
and
S
is the less importa
n
t
element, wh
ile
T
is the lest importa
nt element. The
corre
s
pon
de
nt
value are
set in comp
ari
s
o
n
matrix 2.
In comp
ari
s
o
n
matrix 2, first, we wea
k
ly prefer
K
ove
r
S
, which m
e
ans the val
u
e
of
K
vs
.
S
is 3, and
S
vs
.
K
is 1/3.
In addition, we strongly prefers
S
over
T
, whic
h means
S
vs
.
T
is
5,
and
T
vs
.
S
i
s
1/5. Fu
rther more
we
extremely p
r
efe
r
K
over
T
, wh
ich me
an
s
K
vs
.
T
is 9, an
d
T
vs
.
K
is 1/9. Finally, the node impo
rtan
ce can b
e
cal
c
ulated a
s
I
=0.671
6
K
+0.
2654
S
+
0
.0
629
T
.
Table 2.
Com
pari
s
on m
a
tri
x
2
Elements
K S
T
w
e
ights
K
1 3
9
0.6716
S
1/3
1
5
0.2654
T
1/9
1/5
1
0.0629
Evaluation Warning : The document was created with Spire.PDF for Python.
6236
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 10, Octobe
r 2013 : 623
2
– 6239
Similarly, we
make
S
is th
e
most impo
rta
n
t element to determi
ne the
node imp
o
rt
ance
I
,
and
T
is less impo
rtant element, whil
e
K
is the lest importa
nt element. The
corre
s
pon
de
nt
values a
r
e se
t in compa
r
ison matrix 3.
In comp
ari
s
o
n
matrix 3, first, we extrem
ely prefer
S
ove
r
K
, which mean
s the va
lue of
S
vs
.
K
is 9, and
K
vs
.
S
is 1/9. In addition, we stro
ngly prefe
r
s
S
ove
r
T
, which me
ans
S
vs
.
T
is 5
,
and
T
vs
.
K
is 1/5. Further
more
we we
a
k
ly prefe
r
T
over
K
, which
mean
s
T
vs
.
K
is 3, and
K
vs
.
T
is 1/3. Final
ly, the node importa
nce ca
n be cal
c
ul
ated as
I
=
0
.062
7
K
+0.7
596
S
+0.
1
7
7
7
T
.
Table3. Com
pari
s
on m
a
tri
x
3
Elements
K S
T
w
e
ights
K
1
1/9 1/3 0.0704
S
9
1 5 0.7514
T
3 1/5
1
0.1782
Finally, we make
T
is the
most impo
rta
n
t element to determine th
e node impo
rtance
I
,
and
K
is the
less importan
t
element, while
S
is
the le
st important element. The
corresp
ond
e
n
t
value are
set in comp
ari
s
o
n
matrix 4.
In comp
ari
s
o
n
matrix 4, first, we wea
k
ly prefer
K
ove
r
S
, which me
ans the val
u
e
of
K
vs
.
S
is 3, and
S
vs
.
K
is 1/3.
In addition, we strongly prefers
T
over
K
, whic
h means
T
vs
.
K
is
5,
and
S
vs
.
T
i
s
1/5. Fu
rthe
r more
we
st
rong
ly prefer
T
over
S
, whi
c
h m
ean
s
T
vs
.
S
is 7, an
d
S
vs
.
T
is 1/7. Finally, the node impo
rtan
ce can b
e
cal
c
ulated a
s
I
=0.
1884
K
+
0
.0
810
S
+0.
7
3
0
6
T
Table 4. Co
m
pari
s
on m
a
tri
x
4
Elements
K S
T
w
e
ights
K
1 3
1/5
0.1884
S
1/3 1
1/7
0.0810
T
5
7 1 0.7306
The rea
s
on
we
set the
element valu
es in
co
mpa
r
iso
n
matrix
1 to 4 is th
at , in
comp
ari
s
o
n
matrix 1 all th
e element are equal impo
rtance, whi
c
h i
s
a refere
nce
to
the values in
comp
ari
s
o
n
s
of 2, 3, 4. In
com
pari
s
o
n
s 2, 3, 4, the i
m
porta
nce of
K
,
S
,
T
are
all ch
ang
ed i
n
different ra
ng
es from
small
values to large value
s
.
In this way, we set four different group
s of
paramete
r
s to determin
e
the weights in Eq.2
to compute fo
ur differe
nt ca
se
s of the node impo
rtan
ce
I
i
s
as
follows
:
ca
se1:
I
=
0
.333
3
K
+0.3
333
S
+0.
3
3
3
3
T
, cas
e
2:
I
=0.671
6
K
+0.
2
6
5
4
S
+0.0629
T
,
ca
se3:
I
=
0
.062
7
K
+0.7
596
S
+0.
1
7
7
7
T
,
ca
se4:
I
=0.1
884
K
+0.081
0
S
+0
.7306
T
,
In order to find out how
the efficiency
will be affe
cted when coefficients of
K
,
S
,
T
changed, we will estim
a
te the net
work
effi
ciencies under differ
ent types
of attacks
corre
s
p
ond
en
t to the four case
s of
I
i
in s
e
c
t
ion IV.
4. Simulation results
In this section, we will find out how the e
fficiency will be affected when coeffici
ents of
K,
S, T
altered.
Our Scale
-
free network topolo
g
ies,
i.e
., graph
s wit
h
an alg
ebrai
c dist
ributio
n
o
f
degree
k
k
P
~
)
(
,
with
3
[16], is generated a
r
tifici
ally acco
rdin
g to the
BA
model
[2]. In
both
cases we
have con
s
tructed networks with
N
=50
0
, and
M
=14
94. In ou
r ex
perim
ents,
we set
i
i
all
L
C
)
0
(
3
.
1
. In the simul
a
tion we will
observe the rati
o of E/E(0) to expl
ore the efficiency
influen
ced by
different types of failure, whe
r
e
E(0)
is the initial efficiency
E(G)
of the netwo
rk,
and
E
is the
efficiency of the net
wo
rk on a certain point. We will
f
i
nd out how t
he efficiency
will
be affected
when coefficie
n
ts of
K
,
S
,
T
cha
nge
d.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
6237
Efficiency An
alysis of Scal
e-fre
e
Net
w
ork Ca
scadi
ng
Failures u
nde
r Differe
nt … (Yuan
ni Liu)
0
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
p
E/
E(
0
)
ca
se
1
ca
se
2
ca
se
3
ca
se
4
Figure.1 The
efficiency of BA network u
nder
ran
dom
failure
s in fou
r
ca
se
s
In Figure. 1,
we sh
ow the results of the
simulatio
n
s of
E/E(0)
as the function
s of
p
under
rand
om f
a
ilur
e
s in f
o
u
r
ca
se
s.
I
n
dif
f
e
rent
ca
se
s,
t
he
I
is cal
c
ulat
ed by differe
nt coefficie
n
ts of
the eleme
n
ts
K, S, T
in the four cases th
at we h
a
ve set in
se
ction
3. In Figure.1
,
the four curves
are ove
r
lap
p
e
d
, which mea
n
s that the efficien
cy
of the BA network is less influe
n
c
ed by the
way
of the resource allocation u
nder
ran
dom
failure
s.
Figure.2 (a
), (b), (c), (d
) are the efficien
cy of BA netwo
rk u
n
der different
types of
delibe
r
at
e at
t
a
c
ks
in
ca
se
s 1,
ca
se 2,
c
a
se
3,
an
d ca
se 4
re
sp
ecti
vely. From Fi
g.2 we
can d
r
aw
the c
o
nc
lus
i
on that:
1)
The efficie
n
cy of the network i
s
red
u
ce
d as
th
e in
crement of the
failure n
ode
numbe
r. Whe
n
the failure
no
de nu
mbe
r
is equal, the
ef
fici
en
cy of the network u
n
der th
e types of
K
and
S
attacks are lower tha
n
that of the types of
T
and
I
, an
d the type of
I
is lower tha
n
that of the
type
T
.
2)
In the ca
se
o
f
the sam
e
nu
mber
of
failure nod
e, the g
r
eate
r
propo
rt
ion of
I
de
cid
ed by
T
, the
highe
r efficie
n
cy of the network
than the
same situ
ation und
er
I
type attacks, a
nd the clo
s
e
r
of the curve
s
from
T
type attac
k
to
I
type attac
k
.
3)
Efficiency of the BA netwo
rk with diffe
re
nt to
leran
c
e
p
a
ram
e
ter i
s
d
e
termin
ed by
its attacked
types, in whi
c
h, the effici
ency is l
a
rg
el
y influence
d
by the attacked types of
K
and
S
, and
unde
r the sa
me prop
ortio
n
of the
failure
node, is lower the attacked types of
T
and
I
. While,
I
is mo
stly determin
ed by th
e pro
portio
n
of
T
, in the same situ
ation
,
the highe
r p
r
opo
rtion of
T
,
the higher eff
i
cien
cy und
er
I
type attacks.
0
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
p
E/
E(
0
)
K
S
T
I
(a) T
he efficie
n
cy of BA network un
de
r di
ffer
ent types
of deliberate attacks in ca
se 1
Evaluation Warning : The document was created with Spire.PDF for Python.
6238
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 10, Octobe
r 2013 : 623
2
– 6239
0
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
p
E/
E(
0
)
K
S
T
I
(b)
Th
e efficie
n
cy of BA network un
de
r di
fferent
types
of deliberate attacks in ca
se 2
0
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
p
E/
E(
0
)
K
S
T
I
(c) The effici
e
n
cy of BA network un
de
r di
ffe
rent types
of deliberate attack in
ca
se
3
0
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
0.
1
0.
2
0.
3
0.
4
0.
5
0.
6
0.
7
0.
8
0.
9
1
p
E/
E(
0
)
K
S
T
I
(d)
Th
e efficie
n
cy of BA network un
de
r di
ffer
ent types
of deliberate attack in
ca
se
4
Figure.2
The
efficien
cy of BA network u
nder diffe
rent
types of deliberate atta
cks in four
ca
se
s
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
6239
Efficiency An
alysis of Scal
e-fre
e
Net
w
ork Ca
scadi
ng
Failures u
nde
r Differe
nt … (Yuan
ni Liu)
5. Conclusio
n
In this pap
er,
we have e
s
ti
mated ho
w th
e effi
cien
cy will be affected
when
co
effici
ents of
K
,
S
,
T
chang
ed. The concl
u
sio
n
s
can b
e
derived a
s
:
1) Th
e re
mov
a
ls b
a
sed on
K
and
S
influen
ced the
n
e
twork effici
e
n
cy are large
r
than the
ca
se,
whe
r
e the re
movals ba
se
d on the
T
and
I.
As a
resu
lt, in
order to improve network efficie
n
cy,
we ca
n red
u
ce the wei
ghts of these two
elem
ents too
k
account in d
e
termini
ng the
importa
nce of a node.
2) Th
e effici
e
n
cy of BA ne
twork i
s
dete
r
mine
d by
its attacked typ
e
s. Th
e effici
ency i
s
la
rgel
y
influen
ced by
the attacked
types of
K
an
d
S
, and und
er the same
numbe
r of fail
ure n
ode, the
efficien
cy under attacks o
f
types
T
and
I
are relatively higher. The importa
n
c
e
I
is largely
determi
ned b
y
the proportion of
T
, when the nod
e failure nu
mber is eq
u
a
l, the higher
prop
ortio
n
of
T
, the higher
efficien
cy it is under
I
type attac
k
s
.
Ackn
o
w
l
e
dg
ements
This
work
was
supp
orte
d
by the CQ
UPT Dr. Start-up F
und
Re
sea
r
ch (A
2011
-48
)
,
Natural Scien
c
eFo
und
ation
of CQUPT
(
A
2012
-83
)
, Na
tional Progra
m
on Key Ba
sic Proje
c
t(97
3
prog
ram: 20
12CB3
158
03
), National
Natural Scie
nce Fo
und
a
t
ion of China(6
410
400
4
4
,
6087
3079
), the Natu
ral Science Foun
da
tion of Chon
g
Q
ing(CST
C
2
009BA20
89).
Referen
ces
[1]
Z
h
a
n
g
Yu.
C
o
mp
ut
er
Net
w
o
r
k Att
a
ck
D
e
t
e
cti
o
n
B
a
s
e
d O
n
Q
u
a
n
t
u
m
P
s
o
An
d
R
e
l
e
v
a
nc
e V
e
ct
or
Mac
h
i
ne.
AISS
.
2
01
2; 4(
5): 2
6
8
-
2
7
3
.
[2
]
R
é
ka
Albe
rt, Ha
w
oong
Jeong & Alb
e
rt-L
ászló
Ba
ra
bási
.
D
i
a
m
e
t
e
r
o
f
the
w
o
rld
-
w
i
de
-
w
eb
.
Nat
u
r
e
.19
99;
40
1(6749
):1
3
0
-
13
1
.
[3
]
Albe
rt-Lá
s
zló
Ba
rabá
si
, Ré
ka
Al
be
rt.
Eme
r
ge
nce
o
f
sca
ling
in
ra
ndom ne
t
w
orks.
Sc
ie
nce
.
1999
;
28
6(5439
): 5
09-512
[4]
Musirin Ser
w
an.
C
a
sc
a
d
i
n
g
co
ll
a
p
s
e
a
s
s
e
ss
ment
co
ns
i
d
er
in
g
hi
d
d
en f
a
i
l
u
r
e
. IEEE Proceedings o
n
In
fo
rma
t
ics
an
d C
o
mpu
t
a
t
i
onal In
te
ll
igen
ce
(IC
I
) , Bandu
ng
,
2011
: 318
-32
3
.
[5
]
Wa
ng
Guo
-
ho
ng
,
Xin
g
Rui
,
T
a
ng
Liy
an.
T
he
ri
sk of
c
a
sc
a
d
i
n
g
br
e
a
k
dow
n
in
i
n
du
str
i
a
l
c
l
ust
e
r i
n
no
vat
i
o
n
networ
ks: a
c
o
mplex netw
ork
s
pers
pect
iv
e
. IEEE Proceedi
ng
on
Ma
nage
me
nt Scien
c
e
an
d
Engi
nee
ri
ng.
Mel
bou
rne
,
VIC, 20
10
:
14
45
-145
5
.
[6
]
Yuan
ni
Li
u
,
XinL
i
,
Sh
anzhi
C
hen
, Zhen
Qi
n
.
Mode
l
fo
r Ca
scad
i
ng
Ne
t
w
ork
Fa
ilu
re
s
Based
on
the
No
de
s
w
i
t
h
Diff
e
r
e
nt T
o
l
e
r
a
nc
e P
a
r
a
met
e
r.
T
he j
o
u
r
n
a
l of
C
h
i
na u
n
i
v
e
rs
it
ie
s
of p
o
s
t
s
a
nd
t
e
l
e
c
o
mmu
ni
c
a
ti
o
n
s
.
20
11
; 18
,(5
)
:9
5-101
.
[7]
Ho
lm
e Pett
er,
Be
om Ju
n Ki
m
.
Ed
g
e
ov
er
lo
a
d
br
ea
k
d
o
w
n
i
n
ev
ol
vi
n
g
n
e
t
w
o
r
ks.
P
h
ys. Rev.E
.
2002;
66
(3
) :0
3611
9
.
[8
]
Adi
l
so
n
E.
Mo
tte
r
, Yin
g
cheng L
a
i
.
Ca
sca
d
e
-
ba
se
d
a
t
ta
cks on
complex
net
w
o
rks.
Phys. Rev.E.
2
002
;
66
(6
):0
6510
2
.
[9]
Crucitti Paolo,
Latora,
Vi
to
, Ma
r
c
hio
r
i
.
Mod
e
l
fo
r
c
a
s
c
ad
in
g
f
a
ilur
e
s in complex net
w
or
ks.
P
h
ys.
Rev.
E
.
20
02
; 69
(4
), p
p
.04
5104
.
[10
]
H
o
l
m
e Pe
tter,
Beo
m
Ju
n Kim, Chan
g
N
o
Yo
on
, Se
ung Ke
e
H
a
n
.
Atta
ck vul
n
e
r
abi
li
ty
of co
mple
x
ne
t
w
orks.
Ph
ys
. Re
v
.
E
. 200
2
;
65
(5
):0
5610
9
.
[1
1]
Pa
o
l
o Cr
uc
itt
i
, Vit
o
Lat
or
a, M
a
ss
im
o Ma
rc
hi
or
i,
A
n
dr
ea
R
a
pi
sa
r
da. Effi
ci
e
n
c
y
of Sc
a
l
e
-
F
r
e
e
N
e
t
w
o
r
ks
:
Err
o
r an
d Atta
c
k
T
o
le
ra
n
c
e.
Ph
y
s
i
c
a
A
. 2003
, 32
0(11
):622
-642
.
[12]
Girvan Michelle,
M.E.J Ne
w
m
a
n
.
Commun
i
ty structure i
n
so
ci
al
and
bi
olog
ica
l
n
e
t
w
o
rks
. Pro
c
ee
din
g
s of
the
Na
ti
ona
l
Acad
emy
o
f
Scie
nce
.
20
02
; 99
:7821
-7
826
.
[13
]
Ja
me
s
E.
Smi
t
h
.
Ch
aracterizing
co
mpu
t
er pe
rfo
r
man
c
e
w
i
th
a
sing
le
numbe
r.
C
o
mmun. ACM
. 19
88
;
31
(1
0):1202
-1
206
.
[1
4]
Erd
o
¨
s
P
a
ul,
Alf
r
é
d
R
é
n
y
i
.
O
n
r
a
nd
om
gr
a
p
h
s I
.
Ma
thema
t
ics
.
1
95
9; 1
1
(
6
):
29
0-
2
97.
[1
5]
T
homa
s
L. S
a
a
t
y
.
T
h
e
F
u
nd
am
e
n
ta
ls
of
De
ci
si
o
n
M
a
k
i
ng
an
d
Pri
o
r
i
t
y
T
h
e
o
r
y
w
i
t
h
th
e A
n
a
l
yt
i
c
H
i
e
r
a
rc
h
y
Process.
AHP
Se
rie
s
.F
ou
rth
Ed
i
t
ion
.
Ne
w
Yo
rk: R
W
S
Publ
icati
o
n
s
, 2000
.
[16
]
Geo
r
g
o
s Sigano
s, Falou
t
so
s
Mi
cha
l
i
s
, F
a
loutso
s
Pe
tros, Fal
o
u
t
sos Ch
ri
stors. Po
w
e
r la
w
s
a
n
d
the
AS-
l
e
vel
In
te
rn
e
t
topo
logy
,
N
e
t
w
orkin
g
.
IEEE/ACM Transact
io
n
s
on
Ne
tworki
ng
.
2
00
3; 1
1
(
4
): 51
4-
5
24.
Evaluation Warning : The document was created with Spire.PDF for Python.