TELKOM
NIKA
, Vol. 11, No. 9, September 20
13, pp.
5441
~54
4
7
ISSN: 2302-4
046
5441
Re
cei
v
ed Fe
brua
ry 5, 201
3; Revi
se
d Ju
ne 15, 201
3; Acce
pted Jun
e
25, 2013
Overlapping Communities Detection based on Link
Partition in Directed Networks
Qing
y
u
Zou*
, Fu Liu, Tao Hou, Yihan Jiang
Coll
eg
e of Co
mmunicati
on E
ngi
neer
in
g, Jili
n Un
iv
ersit
y
, C
han
gch
un 13
0
000, Jil
i
n, Chi
n
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
:
3700
857
4@
q
q
.com
A
b
st
r
a
ct
Many c
o
m
p
lex
system
s c
an
be descr
ibed
as
networ
ks to com
p
r
e
hend bot
h
the structure and the
function. C
o
mmu
n
ity structur
e is o
ne of th
e most i
m
p
o
rtant pro
perties
of complex networks. Detecting
overl
app
in
g communiti
es in
netw
o
rks have bee
n mor
e
attentio
n in
recent y
ears,
but the mos
t
of
appr
oach
e
s to
this pro
b
le
m
have
be
en a
p
p
lie
d to th
e un
directe
d
netw
o
rks. T
h
is pap
e
r
prese
n
ts a n
o
ve
l
appr
oach
bas
ed o
n
li
nk p
a
r
t
ition to d
e
tect
overl
app
in
g c
o
mmuniti
es str
u
cture i
n
dir
e
c
t
ed netw
o
rks. In
contrast to
pre
v
ious
rese
arch
es focus
e
d
o
n
grou
pin
g
no
de
s, our
al
gorith
m
defi
nes
co
mmu
n
iti
e
s as
gr
ou
p
s
o
f
d
i
re
cted
li
nks ra
th
e
r
tha
n
n
o
d
e
s
wi
th
th
e
pu
rpo
s
e
o
f
n
o
d
e
s
na
tu
ral
l
y
be
l
o
n
g
to
m
o
re
th
an
one
community. T
h
is appro
a
ch ca
n ide
n
tify a suitabl
e nu
mb
er of overla
ppi
ng
commu
n
ities
w
i
thout any pri
o
r
know
led
ge
ab
out the co
mmunity i
n
di
r
e
cte
d
netw
o
rks. W
e
eva
l
uate
our
alg
o
rith
m o
n
a si
mpl
e
artific
i
al
netw
o
rk an
d s
e
vera
l re
al-n
etw
o
rks. Experi
m
e
n
tal r
e
sults
de
mo
nstrate
that t
he a
l
g
o
ri
thm
prop
ose
d
is
efficient for det
ecting ov
erla
pp
ing co
mmuniti
e
s
in directe
d
ne
tw
orks.
Ke
y
w
ords
:
dir
e
cted netw
o
rk, overl
app
in
g co
mmu
n
it
ies, transform
,
link, modularity
Copy
right
©
2013 Un
ive
r
sita
s Ah
mad
Dah
l
an
. All rig
h
t
s r
ese
rved
.
1. Introduc
tion
Re
cently ma
ny compl
e
x system
s in n
a
tu
re a
nd so
ciety have b
een represe
n
ted as
netwo
rks to u
nderstan
d st
ructure, dyna
mic, rob
u
st,
and evolut
io
n
[1-3]. Comm
unity stru
cture is
one
of the
most im
porta
nt feature
s
o
f
many comp
lex networks [1, 4, 5]. Th
e dete
c
tion
a
n
d
analysi
s
of community structures
have
been attrac
t
ed mu
ch atte
ntion in man
y
applicatio
n
s
[6-
11], becau
se
comm
unitie
s
reve
al top
o
logi
cal relat
i
onship
s
bet
wee
n
sy
ste
m
eleme
n
ts and
rep
r
e
s
ent fun
c
tion [12, 13].
So far, there are mainly two kind
s of clu
s
terin
g
algo
rithms have be
en pro
p
o
s
ed to detect
comm
unitie
s
in co
mplex
netwo
rks,
one i
s
opti
m
ization
alg
o
rithm, an
d
the othe
r i
s
the
hiera
r
chi
c
al clusteri
ng met
hod. One ap
proa
ch
es
of the first sche
me are ba
se
d on a measure
named b
e
twe
enne
ss. It calculate
s
on
e of several me
a
s
ures [14, 15
] of the flow of traffic acro
ss
the links of a
netwo
rk
and t
hen remove
s those li
nk
s
with the most t
r
affic fro
m
th
e network. T
w
o
other related
approa
che
s
a
r
e the use of fluid-flo
w
and
curre
n
t-flow a
nalogi
es [16]
to identify links
for rem
o
val. A different cl
ass of optimi
z
ation
m
e
tho
d
s i
s
whose
based o
n
informatio
n-the
o
reti
c
idea
s, su
ch
as the mini
m
u
m de
scriptio
n l
ength met
hod
s of Ro
svall and Bergstro
m [17]. The
basi
c
ide
a
is
to define a q
uantity that is high for
`go
o
d' divisio
n
s of
a netwo
rk a
nd low fo
r `b
ad'
one
s, an
d th
en to
se
arch
throug
h
possi
ble divi
sion
s f
o
r th
e o
ne
wi
th the
highe
st
sco
r
e. Va
rio
u
s
different mea
s
ures fo
r a
s
signi
ng sco
r
e
s
have b
een
prop
osed, such a
s
the li
kelih
ood
-ba
s
ed
measures [1
8] and others [19], but the
most wi
dely
use
d
app
roa
c
h is the mo
dularity [20]. The
hiera
r
chi
c
al cl
usteri
ng al
gorithms in
clud
e
agglom
erativ
e and divi
sive
method
s to find communit
y
stru
cture in
n
e
tworks. Th
e
y
first comput
e the
stre
ngt
h of lin
k bet
ween e
a
ch p
a
ir node
s
ba
sed
on
different
m
e
thod
s,
such a
s
lin
k
bet
we
enne
ss
[21], link clu
s
te
rin
g
coefficie
n
t [22], information
centrality [23], similarity ba
sed
on rand
o
m
wal
ks
[2
4], clu
s
terin
g
ce
ntrality [25], and so on. Th
en,
mergi
ng the two no
de
s wit
h
the highe
st
stren
g
th
of link repeate
d
ly (aggl
o
m
erative method),
or
removing the link
with the
lowes
t
s
t
rength repe
atedly
(divisive met
hod
s), the p
a
r
tition re
sult
s of
the netwo
rks
are obtai
ned.
Nea
r
ly all
of
these
metho
d
s
are
ba
se
d
on th
e p
r
op
erties of n
o
d
e
s
and
a
s
su
med e
a
ch
node
belon
g
s
to only o
n
e
com
m
unity
. Yong-Yeol
Ahn
et al [2
6] and T. S. Evans et al
[27]
reinvent com
m
unities a
s
g
r
oup
s of links in undire
cte
d
netwo
rks a
nd sh
ow that
the quality of
a
link p
a
rtition
can
be eval
u
a
ted by the m
odula
r
ity
of its corre
s
po
ndi
ng line
gra
ph.
Ho
wever, m
any
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No
. 9, September 201
3: 544
1 – 5447
5442
of the networks th
at we
would li
ke to
study
are
dire
cted, an
d a
node
may be
long to
seve
ral
comm
unitie
s
, includin
g
the
World
Wide
Web,
food webs, many bi
ologi
cal networks, and ev
en
some
so
cial
netwo
rks. T
h
e commo
ne
st app
roa
c
h
to detectin
g
co
mmunitie
s
in
dire
cted networks
has b
een si
mply to ignore the link di
rectio
ns a
n
d
apply algorit
hms de
sig
n
e
d
for undi
rected
netwo
rks [2
8
]. It is cle
a
r
that we
are
throwi
ng
awa
y
a go
od d
e
a
l of info
rma
t
ion ab
out o
u
r
netwo
rk’
s
structure info
rm
ation that co
uld allo
w
u
s
to make
a m
o
re a
c
cu
rate
determi
nation
o
f
the comm
unit
i
es if discardi
ng
the dire
cti
ons of lin
ks.
In this p
ape
r,
a ne
w al
gorit
hm ba
se
d on
links
si
milarit
y
rather t
han
the nod
e'
s p
r
operty i
s
prop
osed to
d
e
tect the
overlappin
g
com
m
unities st
ru
cture
s
i
n
di
re
cted
netwo
rks. On
the b
a
sis of
links si
milarit
y
of a dire
ct
ed net
wo
rk,
we tran
sform
ed an
un
wei
ghted di
re
cte
d
network int
o
a
weig
hted un
d
i
recte
d
net
wo
rk, who
s
e no
des a
r
e the
li
nks of the ori
g
inal net
work and the weig
ht
of links i
s
the
links
simila
rity of the o
r
igi
nal
net
wo
rk. Then, we used
hie
r
a
r
chical
cl
uste
ring
with
the sh
orte
st
path bet
wee
n
node
s in
the
tran
sform
ed
netwo
rk to id
entify commu
nity stru
cture.
In
orde
r to
me
asu
r
e th
e
st
rength
of th
e commu
nity structu
r
e
a
nd o
b
tain th
e mo
st relev
ant
comm
unitie
s
, a popula
r
alg
o
rithm Newm
an-Gi
rvan mo
dularity
Q
[29] was
us
ed.
We co
mpa
r
e
d
the pe
rformance of
ou
r
algo
ri
thm wit
h
three s
u
ccess
ful
methods
:
c
lique
percolatio
n
[
30], link pa
rtition [27], an
d mod
u
la
rity sp
ectral o
p
timization
[31
]
with a
sim
p
le
artificial
network a
nd th
re
e real-wo
r
ld
netwo
rks incl
uding
Ge
ne
netwo
rk,
Em
ail net
work a
n
d
Amazo
n
.com
netwo
rk.
Cl
ique pe
rcolat
ion is
the
most p
r
omin
ent overla
ppi
ng commu
nities
identifying al
gorithm
in
u
ndire
cted
n
e
tworks, lin
k
p
a
rtition i
s
th
e first dete
c
t
i
ng ove
r
lap
p
i
ng
comm
unitie
s
algorith
m
ba
sed on lin
k property
and m
odula
r
ity maximization
can
be gene
rali
zed
in a
prin
cipl
e
d
fashion t
o
i
n
co
rpo
r
ate
in
formation
co
ntained
in lin
k di
re
ction
s
.
To me
asure
th
e
effectivene
ss of the co
mm
unity detecti
n
g
algo
rithm, the extendi
ng
modula
r
ity
Q
ov
[32] had be
en
use
d
on re
al-worl
d
networks.
2. Rese
arch
Metho
d
2.1. Communit
y
A community, also called cluster o
r
mod
u
le, con
s
i
s
ts
of node
s and
links b
e
twee
n these
node
s. Altho
ugh n
o
com
m
on definitio
n ha
s be
en
agr
e
ed u
pon,
it is wid
e
ly accepte
d
tha
t
a
comm
unity should
have
more
internal
than exte
rn
al co
nne
ction
s
[15, 3
3
]. T
he no
de
s in
the
same
co
mmu
nity often ha
ve comm
on
prop
ertie
s
a
n
d
den
sely int
e
rconn
ecte
d
comp
ared to
th
e
rest of the ne
twork. It is not
ed that two comm
unitie
s
may overlap
each other
while a node
can
con
n
e
c
t with
different
co
mmunitie
s
si
multaneo
usly
[1]. In Figu
re 1, a
n
exa
m
ple of
a di
rected
netwo
rk
with
comm
unitie
s
is sh
own. Th
ere a
r
e
three
commu
nities in this network, d
enote
d
by
circle, sq
ua
re
, pentagon a
n
d
triangle, respective
ly. No
de of pentag
o
n
is a co
mmo
n node
sin
c
e
it
sho
u
ld belo
n
g
to the circle
commu
nity as well a
s
the triangl
e co
mm
unity.
Figure 1. Example network sho
w
ing
com
m
unity stru
cture, the nod
e
s
of this network a
r
e divid
e
d
into three g
r
o
ups; no
de pe
ntagon i
s
the comm
on no
d
e
of both the circle an
d tria
ngle
comm
unitie
s
2.2. The Shortes
t
Path
Let
u
,
v
be t
w
o no
de
s in
a netwo
rk
G
. Then a
se
qu
ence of nod
e
s
from
u
to
v
is a path
from
u
to
v
. T
he geo
de
sic
distan
ce,
d
(
u
,
v
), from
u
to
v
is the length
of the sho
r
test path from
u
to
v
in
G
. If on such p
a
th exists, then we set
d
(
u
,
v
)=
∞
a
nd the sh
orte
st path from
u
to
u
is 0 [34].
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Ove
r
lap
p
ing
Com
m
unities Dete
ction ba
sed on Lin
k
Pa
rtition in Directed Networks
(Qing
y
u Z
ou)
5443
2.3. Modularit
y
In ord
e
r to
q
uantify the community
struct
ure of
a n
e
twork,
Ne
wman a
nd
Girvan [20]
prop
osed the
modula
r
ity
Q
as a mea
s
u
r
e
of a network
partition:
2
1
k
ii
i
i
Qe
a
(1)
Whe
r
e
e
ii
is t
he fra
c
tion
of links bel
ongi
ng to commu
nity
i
in the total weights of
all links
and
a
i
is the f
r
actio
n
of links co
nne
cting
comm
unity
i
with other
co
mmunitie
s
.
2.4. Link Sim
ilarit
y
The link
simil
a
rity is a me
asu
r
e of clo
s
ene
ss b
e
twe
en a pair of li
nks. It is clea
r that in
the sam
e
co
mmunity of network the n
o
de-n
ode
c
o
n
nectio
n
s a
r
e
more d
e
n
s
ely
and the sho
r
test
paths
betwee
n
pairs
of no
des
are
short
e
r tha
n
in
diff
erent com
m
u
n
ities.
In
ac
co
r
d
an
ce
w
i
th
th
e
this prin
cipl
es, the similarity betwee
n
links
e
il
and
e
jk
is:
2
(,
)
(,
)
(,
)
il
jk
il
jk
il
jk
We
e
Se
e
De
e
(2)
Whe
r
e
S
(
e
ik
,
e
jk
) mean
s lin
k simila
rit
y
value,
D
(
e
il
,
e
jk
) is the shorte
st paths bet
ween links
e
il
an
d
e
jk
. As
sho
w
n
in Fi
gure 2, t
here
a
r
e
eigh
t sho
r
te
st pat
hs
amon
g fo
ur n
ode
s,
rep
r
esented
by
d
lk
,
d
ik
, d
lj
, d
ij
, d
kl
, d
jl
, d
ki
, d
ji
re
s
p
ec
tively.
D
(
e
il
,
e
jk
)=mi
n(
d
lk
, d
ik
, d
lj
, d
ij
, d
kl
, d
jl
, d
ki
, d
ji
)+1, if
e
il
and
e
jk
have a com
m
on nod
e,
D
(
e
il
,
e
jk
)=1.
Figure 2. The
Shortest Pat
h
s bet
wee
n
Node
s of a Pair of Links
W
(
e
ik
,
e
jk
) i
s
th
e compa
c
tne
s
s bet
wee
n
li
nks
e
il
an
d
e
jk
. After found
t
he
sho
r
test
p
a
th no
de
s, th
ere
are fou
r
simil
a
rity measure
s
sh
own in Figure 3.
Figure 3. Fou
r
ca
se
s of the
link com
p
a
c
tness mea
s
u
r
e
W
(
e
ik
,
e
jk
) b
e
twee
n link
e
ik
and
e
jk
The co
mpa
c
t
ness bet
wee
n
links in Figu
re 3 is:
A:
(,
)
il
jk
nl
n
k
Se
e
nl
n
k
(3
)
B:
(,
)
il
jk
nl
n
k
Se
e
nl
n
k
(4
)
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No
. 9, September 201
3: 544
1 – 5447
5444
C:
(,
)
il
jk
nl
n
k
Se
e
nl
n
k
(5
)
D:
(,
)
il
jk
nl
n
k
Se
e
nl
n
k
(6
)
Whe
r
e
n
+
(
i
) i
s
the nei
ghbo
rs of a
nod
e
i
whi
c
h di
re
ctin
g it,
n
-
(
i
) i
s
th
e neig
hbo
rs o
f
a nod
e
i
whi
c
h
it directing.
2.5. Algorith
m
Our alg
o
rithm
comp
rises th
e followin
g
ph
ase
s
:
a) Cal
c
ul
ate the link simil
a
rities
S
(
e
ik
,
e
jk
) for link ei
k and
e
jk
an
d transfo
rm
origin
al
netwo
rk into
a new weigh
t
ed undirecte
d
netwo
rk
, whose node
s
are the lin
ks of the origin
al
netwo
rk a
nd the wei
ght of links is lin
ks
si
milarity of the original n
e
twork.
b)
Cal
c
ulate t
he sho
r
test p
a
th between
eac
h pai
r of
node
s in th
e
transfo
rme
d
netwo
rk.
Acco
rdi
ng to
the sho
r
test
path, hie
r
a
r
chical
cl
uste
ri
ng al
gorith
m
[35] is
used t
o
find
co
mm
unity
st
ru
ct
ur
es.
c)
Using m
o
d
u
larity on th
e
tran
sform
ed
netwo
rk
to fin
d
mea
n
ingful
comm
unitie
s
rathe
r
than just the
hiera
r
chi
c
al o
r
gani
zatio
n
p
a
ttern of com
m
unities.
3. Results a
nd Analy
s
is
To evalu
a
te t
he pe
rfo
r
man
c
e
of the p
r
o
posed m
e
tho
d
a
simpl
e
a
r
tificial n
e
two
r
k
and
three real-ne
t
works
contai
ning Gen
e
n
e
twork,
Emai
l network an
d Amazon.
co
m netwo
rk a
r
e
use
d
to be the test netwo
rks.
3.1. Simple
Artifici
al Netw
o
r
k
To make our
method cl
ear
to reade
rs, we sho
w
a sm
all-scal
e exa
m
ple dire
cted
network
con
s
i
s
ted of
five node
s a
nd
six links,
as
sho
w
n
in
Figu
re 4A.
There a
r
e t
w
o communiti
es,
sha
r
ing the
No. 5 node, in this network. Acco
rdi
ng to
Equation (2), the simila
ritie
s
of the links in
Figure 4A
are comput
ed
and t
r
an
sform to a
ne
w
we
ighted
un
directed
net
work
com
p
o
s
ed
of six
node
s
and t
en lin
ks a
s
sho
w
n
in Fi
g
u
re
4B. Usin
g hie
r
a
r
chi
c
a
l
clu
s
teri
ng
a
l
gorithm
on t
he
network
shown in Figure 4B with
the shortest path, the results pr
esented in Figure 1C illustrates
two overl
appi
ng commu
nities, on
e conta
i
n No. 1,
2
a
nd 5 n
ode
s a
nd the oth
e
r
contai
n No. 3
,
4
and 5 no
de
s, detecte
d by our metho
d
.
Figure 4. Det
e
cting
Comm
unity Structure in t
he Example Net
w
ork u
s
ing the Prop
ose
d
Method
(A) ori
g
inal n
e
twork (B
) tra
n
sformed n
e
tw
ork (C) hi
erarchical clu
s
t
e
ring
re
sult.
3.1. Application to Real
-n
et
w
o
r
k
We have ru
n
the cliqu
e
percol
a
tion
algo
rith
m,
li
nk partition
algorith
m
,
m
odula
r
ity
spe
c
tral o
p
timization lin
k
algorith
m
an
d our alg
o
rith
m on three real-wo
r
ld net
works. In ord
e
r to
evaluate algo
rithm quality we mu
st be a
s
sesse
d
in
a different way.
The most co
mmon metho
d
is
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Ove
r
lap
p
ing
Com
m
unities Dete
ction ba
sed on Lin
k
Pa
rtition in Directed Networks
(Qing
y
u Z
ou)
5445
modula
r
ity, which
mea
s
u
r
e
s
the
rel
a
tive
numbe
r
of int
e
rcommu
nity and i
n
tra
c
om
munity links.
A
high mo
dula
r
i
t
y indicate
s that there
are
more i
n
tra
c
o
mmunity links than
wo
uld
be expe
cted
by
cha
n
ce. However the mo
dularity mea
s
ure,
Q
, is de
fined only for non-inte
rsect communitie
s
.
Nicosi
a et al.
[32] pro
p
o
s
ed p
r
op
osed
a ne
w m
o
d
u
larity mea
s
ure,
Q
ov
, whic
h is
defined for
dire
cted networks with
ove
r
lappi
ng
com
m
unities stru
cture
s
. In
a n
e
twork i
n
cl
udi
ng n
nod
es
a
nd
m links,
k
i
an
d
k
j
i
s
the th
e
numb
e
r
of links of
i
a
nd
j
,
re
spe
c
tively. Modul
arity,
Q
ov
, was defi
ned
as:
,
1
out
i
n
ij
O
V
ijc
ij
ijc
cC
i
j
V
kk
Qr
A
s
mm
(7
)
Whe
r
e
r
ijc
and
s
ijc
are the portion of the contributio
n
to modula
r
ity given by comm
unity
c
beca
u
s
e
of link
l
(
i
,
j
) a
nd
A
ij
are the
terms of the
adja
c
en
cy m
a
trix.
Q
ov
=0 when all verti
c
es bel
ong to
one
comm
unity, a
nd hig
h
e
r
val
ues of
Q
ov
in
dicate
strong
er
comm
unity
stru
ctu
r
e.
We u
s
e m
odula
r
ity,
Q
ov
, here to
evaluate
som
e
well-kno
w
n
algo
rithm
s
a
nd o
u
r algo
rit
h
m o
n
real
-world
networks.
Figure 5 sh
o
w
s the m
odul
arity,
Q
ov
, of
the networks li
sted in Tabl
e 1.
Table 1. Prop
erties of
Real
-networks
Net
w
ork nam
e
Nodes
Links
Degree
Shorte
st path len
g
th
Clustering coefficient
Gene n
e
t
w
ork
1860
4150
4.796
2.715
0.313
Email netw
o
rk
1
133
5451
19.245
3.606
0.297
Amazon.com netw
o
rk
409687
2464630
12.03
3.865
0.171
Figure 5.
Q
ov
of each
Real
-netwo
rk
Cal
c
ulated by
Four Community Detec
t
ing Algorithm
O:Our alg
o
rit
h
m; C:Cliqu
e
percolatio
n
al
gor
ithm; L:Lin
k
partition al
g
o
rithm; M:Mo
dularity
spe
c
tral o
p
timization al
go
rithm.
The g
ene
tra
n
scriptio
nal
regulato
r
y net
work
(T
RN) o
f
Escheri
c
hi
a coli
i
s
one of the
mo
st
elabo
rate
re
constructio
n
s
curre
n
tly available. In o
r
d
e
r to
evaluat
e ou
r meth
o
d
, we
use t
h
e
method
pre
s
ented in
arti
cl
e [36] to b
u
il
d the T
R
N
of
E. coli that
were o
r
ga
nized in
Re
gulo
n
DB
[37]. Removi
ng du
plicate
intera
ction
s
,
the
re
sultin
g TRN invol
v
ing 168
0 n
ode
s an
d 4
150
intera
ction
s
, with 186 T
F
s (reg
u
lato
ry gene
s)
co
ntrolling the ex
pre
ssi
on of 1
499 ge
ne
s, some
main pa
rame
ters a
r
e liste
d in Table 1
.
A TRN mo
del rep
r
e
s
e
n
ts the mole
cular regul
atio
n
pro
c
e
s
s by
whi
c
h g
ene
s reg
u
late tra
n
scriptio
n
of
other
gen
es.
A gen
e X di
rectly
regul
ates
a
gene Y, if pro
t
ein that is en
cod
ed by X is a transcri
p
tio
nal factor fo
r Y.
The email co
mmuni
cation
netwo
rk
[38] covers
all
th
e
em
ail com
m
unication
s within a
data set of a
r
oun
d half a million email
s
. The node
s of the network are e
m
ail a
ddre
s
se
s, an
d
there i
s
a lin
k betwee
n
two
node
s if at least one
email
exists bet
we
en them. La
st
ly, this netwo
rk
con
s
i
s
ts of 11
33 nod
es a
n
d
5451 lin
ks.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No
. 9, September 201
3: 544
1 – 5447
5446
The Ama
z
on
.com net
work [39] is a
pur
cha
s
in
g n
e
twork fro
m
the online
vendor
Amazo
n
.com,
colle
cted
in
August
200
3. Amazon
sell
s a va
riety of
pro
d
u
c
ts, p
a
r
ticula
rly bo
o
ks
and mu
si
c, and as
part of
their web
sal
e
s op
eration they list for ea
ch item A the
ten other ite
m
s
most freq
uen
tly purch
ased
by buyers of
A. This
information can b
e
rep
r
e
s
ente
d
as a di
re
cted
netwo
rk i
n
which ve
rtice
s
rep
r
e
s
ent ite
m
s an
d ther
e
is a lin
k from
item A to another item B i
f
B
wa
s frequ
entl
y
purch
ased
by buyers of
A.
4. Conclusio
n
In this pa
per,
we p
r
e
s
ente
d
a ne
w alg
o
r
ithm for d
e
te
cting ove
r
lap
p
ing
comm
un
ities in
dire
cted networks ba
sed o
n
the
lin
k sim
ilarity,
whi
c
h i
n
co
rpo
r
ate
communitie
s
o
v
erlap
and li
n
k
dire
ction. A
n
e
w m
e
a
s
u
r
e
of link simil
a
ri
ty has
bee
n i
n
trodu
ce
d. Using
lin
k
simil
a
rity value
s
,
we
have tran
sfo
r
med an
un
we
ighted di
re
cte
d
network
int
o
a ne
w
weig
hted un
dire
ct
ed net
work a
n
d
detecte
d co
mmunitie
s
u
s
ing hie
r
a
r
chical clu
s
teri
ng
method o
n
t
he tra
n
sfo
r
m
ed net
work.
The
algorith
m
ha
s be
en a
ppli
ed to serve
r
real
-net
work
comp
ared
with seve
ral p
o
pular
co
mmu
nity
stru
cture id
e
n
tify algorith
m
s. Th
e
re
su
lts sho
w
that
it is
rathe
r
eff
i
cient to
di
scover th
e fun
c
tion
comm
unity st
ructu
r
e
of directed
networks. Ho
weve
r its
full
pote
n
tial rem
a
in
s u
nexplored. O
u
r
work
ha
s p
r
i
m
arily fo
cu
sed o
n
the
h
i
ghly ov
erl
a
p
p
ing com
m
u
n
it
ies st
ru
ct
u
r
e
of
co
mpl
e
x
netwo
rks, but
the hierar
ch
y that organi
ze
s the
s
e ov
erlap
p
ing
co
mmunitie
s
ho
lds g
r
eat p
r
o
m
ise
for furthe
r stu
d
y
.
Ackn
o
w
l
e
dg
ements
This
research work i
s
suppor
ted partially
by the Jilin
Prov
ince Sci
ence and Technology
Develo
pment
proje
c
ts
10
1005
05, an
d
partially
by
the Jilin
University G
r
a
duate in
nova
t
ive
resea
r
ch proj
ects 2
012
110
1.
Referen
ces
[1]
Ne
w
m
a
n
MEJ. Commun
i
ties,
modu
les a
nd
larg
e-scal
e
structure i
n
net
w
o
rks.
Nature P
h
ysics
. 2
012;
8(1): 25-3
1
.
[2]
Maslov S. Com
p
le
x n
e
t
w
orks -
Role mo
del for
modul
es.
Nature Physics
. 20
07; 3(1): 18-1
9
.
[3]
Strogatz SH. Exp
l
ori
ng com
p
l
e
x
net
w
o
rks.
Na
tu
re
. 200
1; 41
0(68
25): 26
8-2
76.
[4]
Ne
w
m
an
MEJ.
Modu
larity a
n
d
community structure in
netw
o
rks.
Proceedi
n
g
s of the Nati
o
nal Aca
dem
y
of Sciences of
the Unite
d
States
of America. 200
6; 103(
23): 857
7-85
82.
[5]
Doro
govtsev S
N
, Goltsev AV
, Mendes JF
F
.
Critical
ph
eno
mena
in com
p
le
x n
e
t
w
orks.
Reviews of
Moder
n Physic
s
.
2008; 80(
4): 127
5-13
35.
[6]
Yang B, Ji
n D,
Liu JM, et a
l
. Hierarc
hic
a
l co
mmunit
y
d
e
tec
t
ion
w
i
t
h
ap
plic
ations to r
eal-
w
o
r
ld
net
w
o
r
k
analy
sis.
Data
& Know
led
ge
Engi
neer
in
g.
2013; 83: 2
0
-38.
[7]
W
u
Z
H
, Li
n YF
, W
an HY,
et a
l
. Efficient ov
erl
app
ing
comm
u
n
it
y d
e
tectio
n i
n
h
u
g
e
re
al-
w
o
r
ld
net
w
o
rks.
Physica a-Stati
s
tical Mech
ani
cs and Its Appli
c
ations.
20
12;
391(
7): 247
5-2
490.
[8]
Li K, G
ong
X,
Guan
S,
et
al. Efficie
n
t a
l
gorithm
bas
ed
on
n
e
ig
hb
orh
ood
ov
erla
p f
o
r comm
unit
y
identification in
complex
net
w
o
rks.
Physic
a
a-Statistical
Mecha
n
ics
an
d Its Appl
icati
ons.
201
2;
39
1(4)
:
178
8-17
96.
[9]
Becker E, Ro
bi
sson B, Ch
ap
p
l
e CE, et a
l
. Multifunc
ti
on
al pr
oteins r
e
vea
l
e
d
b
y
ov
erla
ppi
ng cl
usterin
g
in prote
i
n int
e
raction n
e
t
w
ork.
Bioinfor
matics
.
2012; 28(
1): 84-90.
[10]
Hou
L, W
ang
L, Qian MP, e
t
al. Modu
lar
ana
l
y
si
s of th
e
prob
abi
listic
g
enetic
inter
a
cti
on n
e
t
w
ork.
Bioi
nfor
matics.
2011; 2
7
(6): 8
53-8
59.
[11]
Steinh
ae
user
K, Cha
w
l
a
NV
. Identif
y
i
ng a
nd eva
l
u
a
ting
communit
y
str
u
cture in c
o
m
p
le
x n
e
t
w
orks.
Pattern Recognition Letters.
201
0; 31(5): 41
3-42
1.
[12]
Kalten
bac
h H
M
, Stelling J. Modu
lar an
al
ysis of biol
og
ica
l
net
w
o
rks.
Adv Exp Med Biol.
2012; 7
36: 3
-
17.
[13]
F
o
rtunato
S.
Commun
i
t
y
de
tection i
n
gr
ap
hs.
Physics R
eports-R
eview
Section
of P
h
ysics L
e
tters.
201
0; 486(
3-5)
: 75-174.
[14]
Wilkinso
n DM,
Hub
e
rman
BA.
A
meth
od for
findi
ng
co
mmu
n
i
ties of r
e
l
a
ted
gen
es.
Proc
Natl Acad S
c
i
USA
.
2004; 1
0
1
Supp
l 1: 524
1-52
48.
[15]
Radicc
hi F
,
C
a
stell
ano
C,
Cecco
ni F
,
et
al.
Defi
ni
ng
and
id
entifyin
g
co
mmun
ities
in n
e
tw
orks
.
Procee
din
g
s o
f
the Natio
nal
Academ
y
of Scienc
es
of the
United St
ates
of
America. 2
004; 1
01(9)
:
265
8-26
63.
[16]
Z
anja
n
i AA
H,
Daro
one
h A
H.
F
i
nd
ing
comm
uniti
es i
n
l
i
n
e
a
r
time
b
y
d
e
vel
opi
ng th
e s
e
e
d
s
.
Phys Rev
E.
2011; 84(
3).
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Ove
r
lap
p
ing
Com
m
unities Dete
ction ba
sed on Lin
k
Pa
rtition in Directed Networks
(Qing
y
u Z
ou)
5447
[17]
Rosvall M, Bergstrom CT
.
An infor
m
ati
on-t
heor
etic frame
w
ork fo
r resolving co
mmunit
y
structure in
complex networks.
Proc Natl Acad Sci
USA
.
2007; 1
04(1
8
): 7327-
73
31.
[18]
Karrer B, Ne
w
m
an ME. Stochastic bl
ockm
o
dels a
nd com
m
unit
y
struct
ure in net
w
o
rks.
Phys Rev E
Stat Nonlin Sof
t
Matter Phys.
201
1; 83(1 Pt 2): 0161
07.
[19]
Li Z
,
Z
hang S, W
ang RS, et al. Quant
itativ
e function for
communit
y
d
e
tection.
Phys Rev E.
2008
;
77(3).
[20]
Ne
w
m
a
n
MEJ,
Girvan M. F
i
n
d
in
g a
n
d
ev
al
ua
ti
n
g
co
mmun
i
ty
st
ructur
e in
net
w
orks.
Phys
Rev
E.
200
4;
69(2): 1-1
6
.
[21]
Girvan M, N
e
w
m
an MEJ.
C
o
mmu
n
ity struct
ure i
n
soc
i
a
l
a
nd
bio
l
og
ical
n
e
tw
orks.
Proce
edi
ngs of
the
Natio
nal Aca
d
e
m
y
of Scie
nces
of the United
States of America.
200
2; 99(1
2
): 7821-
78
26.
[22]
Radicc
hi F
,
Castell
ano C, C
e
ccon
i
F
,
et al.
Definin
g
and
identifyi
ng co
mmu
n
ities i
n
n
e
tw
orks
. Proc
Natl Acad Sci
USA
.
2004; 1
0
1
(9): 265
8-2
6
6
3
.
[23]
F
o
rtunato S, Latora
V, Mar
c
hiori
M. Met
hod
to fi
nd
c
o
mmunit
y
stru
ctures b
a
se
d
on
informati
on
central
i
t
y
.
Phys
Rev E Stat N
onlin Soft Matter Phys.
2004; 7
0
(5 Pt 2): 0561
04.
[24]
Pons P, Latap
y M. Computing
communiti
es in
large n
e
t
w
orks
using ra
nd
om w
a
lks.
Lect Not
e
s Co
mp
u
t
Sc.
2005; 37
33
: 284-29
3.
[25]
Yang
B, Li
u
JM. Discover
i
ng Gl
oba
l N
e
t
w
ork
Comm
u
n
ities
Base
d
on
Loca
l
C
e
n
t
ralities.
Ac
m
T
r
ansactio
n
s o
n
the W
eb.
200
8; 2(1).
[26]
Ahn YY, Bagr
o
w
JP, L
ehma
n
n
S. Link com
m
uni
ties reveal multiscale
complex
i
t
y
in net
w
o
rks.
Nature.
201
0; 466(
730
7): 761-U
7
1
1
.
[27]
Evans T
S
, Lambiotte R. Li
ne
grap
hs
, link p
a
rtitions, a
nd o
v
erla
ppi
ng com
m
uniti
es.
Phys
Rev E.
2
0
09;
80(1).
[28]
Rese
ndis-A
n
to
nio O, F
r
e
y
re-
G
onzal
ez JA, Menc
hac
a-Mend
ez R, et
al. Modul
ar a
nal
ysis of th
e
transcripti
ona
l regu
lator
y
n
e
tw
o
r
k of E-coli.
T
r
ends in Gen
e
tics.
2005; 2
1
(
1): 16-20.
[29]
Ne
w
m
a
n
MEJ.
Detectin
g c
o
m
m
unit
y
structur
e in
net
w
o
rks.
Europ
e
a
n
Phy
s
ical J
our
nal
B
.
200
4; 38(
2):
321-
330.
[30]
Palla G, Dereny
i I, Farkas I,
et al. Unc
o
v
e
rin
g
the
over
lap
p
in
g comm
unit
y
structure
of compl
e
x
net
w
o
rks i
n
nat
ure an
d soci
et
y.
Nature.
200
5; 435(7
0
4
3
): 81
4-81
8.
[31]
Leic
h
t EA, Ne
w
m
a
n
MEJ.
C
o
mmuni
t
y
structure in directed net
w
orks.
Physical Review
Letters
. 2
008;
100(
11).
[32]
Nicosi
a
V, Ma
ngi
oni G, C
a
rc
hiol
o V, et
al.
Exte
ndi
ng th
e
defin
ition
of m
odu
larit
y
to
dir
e
cted
grap
hs
w
i
t
h
over
lap
p
i
n
g commun
i
ties.
Journa
l of Statistical Mec
han
i
cs-T
heory an
d Experi
m
ent.
20
09.
[33]
Lanc
ichi
netti
A, F
o
rtunato S,
Kertesz J. Detecting th
e overl
a
p
p
in
g
and h
i
erarc
h
i
c
al commu
nit
y
structure in complex
net
w
ork
s
.
New
Journal
of Physics.
2009; 11.
[34]
Mason
O, Ver
w
o
e
r
d
M. Grap
h the
o
r
y
a
nd
n
e
t
w
o
r
ks i
n
Bi
ol
og
y.
Iet System
s B
i
ology.
20
07; 1(
2): 89-
119.
[35]
Da
y
W
E
, Ede
l
sbrun
ner H. Efficient alg
o
rith
ms
for agglo
m
erative h
i
era
r
chical cl
usteri
ng metho
d
s
.
Journ
a
l of Clas
s
ificatio
n.
198
4
;
1(1): 7-24.
[36]
Salg
ado
H, M
a
rtinez-F
l
o
res I
,
Lop
ez-F
ue
ntes A,
et
al. E
x
tracting r
e
g
u
lat
o
r
y
n
e
t
w
orks
o
f
Escheric
h
i
a
coli from Re
gul
onDB.
Methods Mol Biol.
20
1
2
; 804: 17
9-19
5.
[37]
Gama-Castro
S, Salg
ad
o H,
Pe
ralta-Gi
l M,
et al.
Reg
u
l
o
n
D
B versi
o
n
7.0
:
transcripti
ona
l reg
u
l
a
tion
o
f
Escheric
hia co
l
i
K-12 inte
grat
ed
w
i
thi
n
ge
ne
tic sensor
y
r
e
s
pons
e units (Gensor U
n
its).
Nucleic Acids
Research.
20
1
1
; 39: D98-D
1
0
5
.
[38]
Guimera
R, D
ano
n
L, Di
az-
G
u
iler
a
A,
et a
l
. Self-simi
l
ar
c
o
mmuni
t
y
stru
cture
i
n
a
n
e
tw
o
r
k of
h
u
man
interactions.
Phys Rev E.
200
3; 68(6).
[39]
Claus
et A. F
i
ndin
g
loca
l com
m
unit
y
struct
ur
e in net
w
o
rks.
Phys Rev E.
2005; 72(
2).
Evaluation Warning : The document was created with Spire.PDF for Python.