PHYSICAL REVIEW RESEARCH 2, 042029(R) (2020)
Rapid Communica ions
Link p edic ion in mul iplex ne wo ks ia iadic closu e
Albe o Ale a ,1Ma a Tunine i,1Daniela Paolo i,1Yami Mo eno,2,3,1and Michele S a nini1,*
1ISI Founda ion, ia Chisola 5, 10126 To ino, I aly
2Ins i u e o Biocompu a ion and Physics o Complex Sys ems (BIFI), Uni e si y o Za agoza, 50018 Za agoza, Spain
3Depa men o Theo e ical Physics, Uni e si y o Za agoza, 50018 Za agoza, Spain
(Recei ed 11 May 2020; e ised 30 Sep embe 2020; accep ed 27 Oc obe 2020; published 16 No embe 2020)
Link p edic ion algo i hms can help o unde s and he s uc u e and dynamics o complex sys ems, o
econs uc ne wo ks om incomple e da a se s, and o o ecas u u e in e ac ions in e ol ing ne wo ks.
A ailable algo i hms based on simila i y be ween nodes a e bounded by he limi ed amoun o links p esen
in hese ne wo ks. In his Rapid Communica ion, we educe his la e in insic limi a ion and show ha di e en
kinds o ela ional da a can be exploi ed o imp o e he p edic ion o new links. To his aim, we p opose a
link p edic ion algo i hm by gene alizing he Adamic-Ada me hod o mul iplex ne wo ks composed by an
a bi a y numbe o laye s, ha encode di e se o ms o in e ac ions. We show ha his me ic ou pe o ms he
classical single-laye ed Adamic-Ada sco e and o he s a e-o - he-a me hods, ac oss se e al social, biological,
and echnological sys ems. As a by-p oduc , he coe icien s ha maximize he mul iplex Adamic-Ada me ic
indica e how he in o ma ion s uc u ed in a mul iplex ne wo k can be op imized o he link p edic ion ask,
e ealing which laye s a e edundan . In e es ingly, his e ec can be asymme ic wi h espec o p edic ions in
di e en laye s. Ou wo k pa es he way o a deepe unde s anding o he ole o di e en ela ional da a in
p edic ing new in e ac ions and p o ides ano he algo i hm o link p edic ion in mul iplex ne wo ks ha can be
applied o a ple ho a o sys ems.
DOI: 10.1103/PhysRe Resea ch.2.042029
Ne wo k science has been es ablished as a pi o al ool o
cha ac e ize he s uc u e o eal-wo ld complex sys ems, ha
in ol es mul iple ypes o ela ions among hei undamen al
componen s [1]. One o he mos impo an challenges wi hin
he complex sys ems amewo k is o elucida e which en i ies
a e ela ed o which o he s and wha a e he ypes o hese
ela ionships [2]. Wi hin he ne wo k science domain, his
scien i ic ask ansla es in o a link p edic ion p oblem, ha
a emp s o es ima e he likelihood o he exis ence o a link
be ween wo nodes, based on he obse ed links and a ibu es
o nodes [3,4]. Link p edic ion algo i hms a e ex emely help-
ul in a leas wo di ec ions: o econs uc ne wo ks om
incomple e da a se s and o o ecas u u e in e ac ions in
e ol ing ne wo ks. Examples o he i s applica ion can be
ound in biological ne wo ks, such as p o ein in e ac ion ne -
wo ks, whe e many links a e s ill unknown and hei exis ence
mus be demons a ed by expensi e expe imen s [5]. P edic-
ion algo i hms help in ocusing expe imen al e o s owa d
hose links mos likely o exis . The second ask, link o e-
cas ing, is ou inely applied in online social ne wo ks, such as
Facebook. New iendships a e indeed ecommended based on
*Co esponding au ho : [email p o ec ed]
Published by he Ame ican Physical Socie y unde he e ms o he
C ea i e Commons A ibu ion 4.0 In e na ional license. Fu he
dis ibu ion o his wo k mus main ain a ibu ion o he au ho (s)
and he published a icle’s i le, jou nal ci a ion, and DOI.
link p edic ion algo i hms, so ha indi iduals can e icien ly
ind pee s hey a e in e es ed in [6,7].
The link p edic ion p oblem is a long-s anding challenge
a he in e sec ion be ween compu e science and s a is-
ical physics communi ies. T adi ional algo i hms include
Ma ko chains and s a is ical models [8], while ecen ap-
p oaches om he physics communi y, such as andom walk
p ocesses and maximum-likelihood me hods, ha e been con-
side ed [9,10]. Link p edic ion algo i hms can be classi ied
mainly in o wo ca ego ies: simila i y-based me hods and
p obabilis ic models [11,12]. Since he la e can be compu-
a ionally un easible o la ge ne wo ks, a lo o a en ion has
been de o ed o he c ea ion o good simila i y sco es. Many
o hese simila i y me hods a e based on he same basic idea,
ha wo nodes a e likely o be linked i hey sha e a com-
mon neighbo [13,14]. Despi e i s simplici y, his concep has
p o en o be qui e use ul o highly asso a i e ne wo ks, such
asscien i iccollabo a ionne wo ks[15]. Howe e , as signaled
by Jia e al. [16], he p edic ion powe o any simila i y-based
link p edic ion algo i hm is bounded due o helimi ed amoun
o links p esen in he ne wo k.
In ne wo k science, ichly s uc u ed da a can be ep e-
sen ed by mul ilaye ed ne wo ks, in which each laye accoun s
o a di e en ype o in e ac ion [17,18]. Fo ins ance, social
in e ac ions can ha e di e en pu poses (e.g., leisu e e sus
wo k) and happen h ough a ious communica ion channels,
including ace- o- ace in e ac ions, e-mail, Facebook, phone
calls, and so on. The idea o p edic ing links in mul ilaye
ne wo ks has been explo ed du ing he las decade om se -
e al di e en poin s o iew. Fo ins ance, Da is e al. [19]
2643-1564/2020/2(4)/042029(6) 042029-1 Published by he Ame ican Physical Socie y
ALBERTO ALETA e al. PHYSICAL REVIEW RESEARCH 2, 042029(R) (2020)
p oposed a echnique o include mul i ela ional da a o link
p edic ion om a p obabilis ic poin o iew. Simila ly, se -
e al ex ensions o p obabilis ic models o mul ilaye ne wo ks
ha e been p oposed [20–25]. O he wo ks, a he han ocus-
ing on inco po a ing new da a o al eady exis ing ne wo ks,
used mul ilaye s uc u es o ocus on he empo al e olu ion
o he ne wo ks [26,27]. Se e al s udies ex ended he no ion
o neighbo hood o mul ilaye ne wo ks [28–31], ocusing on
ne wo ks o wo laye s. Howe e , a undamen al ques ion is
s ill unanswe ed: How can di e en kinds o ela ional da a
be exploi ed o imp o e he p edic ion o new in e ac ions?
Fo ins ance, o which ex en a e ace- o- ace in e ac ions
p edic i e o new Facebook iendships? In e es ingly, i has
been ecen ly shown ha he mul iplex ne wo k ep esen-
a ion can be edundan in some cases, as he in o ma ion
encoded in some laye s can be e ec i ely included in o he s,
educing he numbe o laye s [32]. The e o e, how can link
p edic ion algo i hms op imize he in o ma ion s uc u ed in
a mul iplex ne wo k ep esen a ion, ha can be subop imally
o ganized?
In his Rapid Communica ion, we add ess hese ques ions
by p oposing a me ic o link p edic ion in mul iplex ne -
wo ks, based on a gene aliza ion o he Adamic-Ada me hod
o single-laye ed ne wo ks [14]. Ou me ic ully exploi s
he complexi y o he ela ionships ha migh be es ablished
ac oss he undamen al componen s o complex sys ems, by
conside ing all possible iadic closu es in he co esponding
mul iplex ep esen a ion. We show ha his sco e, ha can be
applied o any mul iplex opology composed by an a bi a y
numbe o laye s, is able o ou pe o m o he me ics based on
single-laye ed simila i y be ween nodes, ac oss se e al social
and biological sys ems. We show ha he in o ma ion encoded
in di e en laye s can be asymme ic wi h espec o he link
p edic ion p oblem: Fo example, ace- o- ace in e ac ions
can be pa ially p edic i e o new Facebook iendships, bu
no ice e sa.
We conside eigh di e en da a se sspanning se e al ypes
o social, biological, and echnological sys ems, ep esen ed
as mul iplex ne wo ks: (i) Copenhagen ne wo ks s udy (CNS),
whe e ou laye s ep esen physical p oximi y, phone calls,
ex messages, and Facebook iendships among uni e si y
s uden s [33]. (ii) C. elegans gene ic (CEG): Gene ic and p o-
ein in e ac ions o he C.elegans, whe e h ee laye s ep esen
di ec , physical, and addi i e gene ic in e ac ions [34]. (iii) C.
elegans neu al (CEN): A neu al ne wo k o he C. elegans,
whe e h ee laye s ep esen elec ic, chemical monoadic, and
chemical polyadic in e ac ions [35], (i ) CS-Aa hus (CSA):
A social ne wo k o employees o he Compu e Science
Depa men a Aa hus, whe e i e laye s ep esen Facebook,
leisu e, wo k, coau ho ship, and lunch in e ac ions [36]. ( )
CKM physicians (CKM): A social ne wo k o physicians,
whe e h ee laye s ep esen who hey ask o ad ice, who
hey discuss cases wi h, and who a e hei iends [37]. ( i)
EU ai (EUA): An ai anspo a ion ne wo k o Eu ope,
whe e 27 laye s ep esen ai lines ou es [38]. ( ii) Lazega
(LAZ): A social ne wo k o pa ne s and associa es o a co -
po a e law pa ne ship, whe e h ee laye s ep esen cowo k,
iendship, and ad ice [39]. ( iii) Vicke s (VIC): A social
ne wo k o s uden s in a school in Vic o ia, Aus alia, whe e
h ee laye s ep esen who hey ge on wi h, who a e hei
bes iends, and who hey p e e o wo k wi h [40]. See
Table S1 o he Supplemen al Ma e ial (SM) [41] o de ails
abou he da a se s.
In he ollowing, we will con as di e en algo i hms o
link p edic ion on hese da a se s. The quali y o link p edic-
ion algo i hms can be e alua ed by wo me ics: he ecei e
ope a ing cha ac e is ics (ROC) cu e, wi h he co esponding
a ea unde he cu e (AUC) alue, and he p ecision. The
p ecision can be compu ed as n∗/n, whe e nis he numbe
o new links ha we wan o p edic and n∗is he amoun o
co ec p edic ions among he op nlinks. Thus, i p o ides
complemen a y in o ma ion o he one gi en by he AUC. I
is impo an o highligh ha , due o he limi ed amoun o
links p esen in a ne wo k, he AUC o any simila i y-based
link p edic ion algo i hm is bounded [16]. Fo ins ance, i
simila i y is based on common neighbo s, wo nodes wi hou
any neighbo in common will ha e a sco e equal o ze o. The
numbe o sco eless links bounds he maximum and mini-
mum alues o he AUC o AUCmin =1
2(1 +p1)(1 −p2) and
AUCmax =AUCmin +p1p2, whe e p1(p2) is he ac ion o
links wi h a sco e di e en om 0 among hose links ha will
(will no ) exis in he u u e (see Sec. 2 o he SM [41] o
de ails). No e ha only when p1=p2=1, i.e., he e a e no
sco eless links, i holds AUCmin =0 and AUCmax =1.
We p opose a gene aliza ion o he Adamic-Ada (AA)
sco e [14], one o he mos common and success ul me hods
o link p edic ion in social ne wo ks. The AA sco e be ween
nodes uand is gi en by he numbe o common neighbo s
weigh ed by hei deg ee,
AA(u, )=
w∈(u)∩( )
1
ln(kw),(1)
whe e (u) ep esen s he se o neighbo s o node uand
kw=|(w)|is he deg ee o node w. In a mul iplex ne wo k,
he AA sco e can be applied o di e en laye s, depending
on which laye α he se o neighbo s w∈α(u)∩α( )is
conside ed, whe e α(u) ep esen s he se o neighbo s o
node uin laye α.
Fo example, le us conside ha we a e in e es ed in p e-
dic ing u u e phone calls among he pa icipan s in he CNS.
The classic AA me hod conside s he se o neighbo s in he
same phone calls laye . I he AA sco e is applied o he laye
ep esen ing Facebook iendship, ins ead, he a ionale is ha
wo indi iduals a e mo e likely o in e ac o line (phone
call) i hey sha e many iends on Facebook (i.e., common
neighbo s in he Facebook laye ). The same easoning ap-
plies o o he laye s. Table Ishows he p ecision and AUC
alues ( oge he wi h i s heo e ical bounds) o p edic phone
calls, ob ained o he AA me hod applied o each laye o
he CNS (excluding physical p oximi y in e ac ions o being
much dense han o he s). In e es ingly, while he maximum
p ecision (0.04) is ob ained by applying he AA sco e o he
same calls laye , he maximum AUC (0.69) is ob ained by
conside ing he Facebook laye . This implies ha his kind o
in e ac ions (Facebook iendship) include use ul in o ma ion
o p edic new links no encoded in he phone calls laye . This
is also e lec ed in a la ge maximum heo e ical bound o
he AUC o he Facebook laye wi h espec o he phone
calls laye . No e also ha by using he agg ega ed ne wo k, in
042029-2
LINK PREDICTION IN MULTIPLEX NETWORKS VIA … PHYSICAL REVIEW RESEARCH 2, 042029(R) (2020)
TABLE I. P ecision and AUC o p edic new phone calls in he
CNS da a se , ob ained by using he classical Adamic-Ada me ic on
each laye (calls, Facebook, ex s), and on he agg ega ed ne wo k.
Theo e ical bounds o he AUC a e showed. P edic ions a e es ed
o e he se o nono e lapping links o e all laye s (7% o he o al).
Bes esul s among he laye s a e highligh ed in bold.
Me hod P ecision AUC AUC [wo s -bes ]
Random 0 0.50 [0-1]
AAcalls 0.04 0.60 [0.60-0.60]
AA acebook 00.69 [0.59-0.70]
AAsms 0 0.60 [0.60-0.60]
AAagg ega ed 0 0.76 [0.65-0.80]
which all laye s a e p ojec ed on o a single one, one ob ains
maximum AUC bu ze o p ecision.
This obse a ion shows he need o go beyond single-
laye ed sco es and combine hem in o a mo e gene al me ic
ha ully exploi s he mul iplex na u e o he ne wo ks aken
in o accoun . No e, indeed, ha single-laye ed me ics con-
side ed iadic ela ions among h ee nodes u, , and w,
in which he wo links u-wand -wbo h lie in he same
laye . Howe e , iadic ela ions in mul iplex ne wo ks can
be a iche [42,43]. Figu e 1shows di e en kinds o i-
adic ela ions in mul iplex ne wo ks. Le us indica e as x
he laye on which he link u- is o be p edic ed. One can
dis inguish ou ypes o iadic ela ions depending on he lo-
ca ion o he (u,w) and ( ,w) links: (i) Txx ={(u, ,w)|w∈
x(u)∩x( )}, whe e bo h links lie in laye x; (ii) Txα=
{(u, ,w)|w∈x(u)∩α( )}and Tαx, whe e one link lies
in he laye xand he o he lies in ano he laye α; (iii)
Tαα ={(u, ,w)|w∈α(u)∩α( )}, whe e bo h links a e
in he same laye α, di e en om laye x; and (i ) Tαβ =
{(u, ,w)|w∈α(u)∩β( )}and Tβα, whe e one link is in
laye αand he o he in laye β, bo h di e en om laye x.
(a) (b) (c) (d)
T
xx T
xTT
FIG. 1. T iadic ela ionships in a mul iplex ne wo k. Gi en wo
nodes uand o which we wan o p edic he u u e exis ence o
a link ( ed dashed line) in he op laye x(g een), based on hei
connec ions wi h ano he node w(pink) ia iadic closu e, we can
dis inguish ou ypes o iadic ela ionships: (a) uand a e bo h
connec ed o win he p edic ion laye x; (b) he link be ween uand
wis in he p edic ion laye x,bu and wa e connec ed in a di e en
laye α, o ice e sa; (c) bo h uand a e connec ed o win a laye
αdi e en om he p edic ion laye x;(d)uand wa e connec ed
in a laye αdi e en om he p edic ion laye x,and and wa e
connec ed in a hi d laye βdi e en om laye s αand x.
Wi hin his o malism, one can conside a sco e ha coun s
he common neighbo s closing iads o each ype, and weigh
each con ibu ion by he loga i hm o he deg ee, as in he
Adamic-Ada sco e,
MAA(u, )=
α,β 
w∈Tαβ
ηxαηxβ
kαkβ
1
lnkα
wlnkβ
w
.(2)
This exp ession is he gene aliza ion o he Adamic-Ada
sco e o mul iplex ne wo ks (MAA) wi h an a bi a y numbe
o laye s, in which he links o be p edic ed all lay in he same
laye x. Se e al conside a ions a e in o de .
Fi s , he con ibu ion o each iad (u, ,w)∈Tαβ is
weigh ed by he squa e oo o he loga i hm o he deg ee
o node win he wo laye s in ol ing αand β.Wi h his
choice, he o iginal weigh 1/ln(kw) is na u ally eco e ed
o α=β=x. Second, no e ha di e en laye s o a mul-
iplex ne wo k may show e y di e en densi ies, as shown in
Table S1 o he SM [41]. In case o simila i y sco es based
on he numbe o common neighbo s, as in his case, dense
laye s will ha e mo e iads and hus will be less in o ma i e.
We ake his in o accoun by weigh ing he con ibu ion o
each ype o iadic ela ion by he squa e oo o he a e age
deg ee o he laye s in ol ed, √kα. Thi d, he coe icien s
ηxαbe o e each e m allow us o con ol he ela i e weigh o
each ype o iadic closu e in he o al sco e o he link. We
choose hem in a way ha ηxαco esponds o he weigh o
laye α. Wi hou lack o gene ali y, we choose αηxα=1.
Fou h, he applica ion o he AA sco e o laye α, co e-
sponding o iad closu es [Fig. 1(c)], is eco e ed by se ing
ηxα=1. The o iginal AA sco e in single-laye ed ne wo ks
[Fig. 1(a)] is eco e ed by simply se ing ηxx =1.
Figu e 2shows he AUC [Fig. 2(a)] and p ecision
[Fig. 2(b)] o he MAA me ic as a unc ion o he coe icien s
ηxα, o h ee o he eigh da a se s unde conside a ion. O he s
a e shown in Figs. S1 and S2 o he SM [41]. Fo he sake
o con enien isualiza ion, we conside only h ee laye s o
each ne wo k, o isualize he h ee coe icien s in a iangle.
Fo each ne wo k, we conside he p edic ion o links in each
o he h ee laye s. The coe icien ηxαindica es he weigh o
laye αin he p edic ion o new links in laye x. Fo ins ance,
in he CNS da a se , he coe icien η12 indica es he weigh
o Facebook iendship ( ep esen ed in laye 2) in p edic ing
new phone calls (laye 1). One can see ha , in mos cases, he
maximum alue o he AUC and he p ecision is achie ed o
non i ial combina ions o he coe icien s, i.e., di e en om
ηxx =1 which co esponds o he classical AA sco e, showed
in he le co ne o iangles. This is pa icula ly ue o he
p ecision, whose maximum is achie ed in some cases in he
middle o he iangle, i.e., wi h simila con ibu ions o each
laye , as in he case o he CKM o CNS ne wo ks. The exac
alues o he coe icien s maximizing AUC and p ecision o
each da a se a e epo ed in Table S2 o he SM [41].
The e o e, Fig. 2shows ha he p edic ion o a ce ain
kind o links can be imp o ed by exploi ing addi ional, ela ed
in o ma ion, encoded in o he laye s. Fo ins ance, Facebook
iendship can help in p edic ing new calls [i.e., he maximum
AUC o his ask is ob ained o η12 =0.40—see plo (i)
o Fig. 2(a) and Table S2 o he SM [41]], o addi i e ge-
ne ic in e ac ions and physical associa ion can be p edic i e
042029-3
ALBERTO ALETA e al. PHYSICAL REVIEW RESEARCH 2, 042029(R) (2020)
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
13
11
12
0.590
0.628
0.666
0.704
0.742
0.780
AUC
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
23
22
21
0.530
0.608
0.686
0.764
0.842
0.920
AUC
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
31
33
32
0.550
0.586
0.622
0.658
0.694
0.730
AUC
Copenhagen
(i)
(i )
( ii)
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
13
11
12
0.490
0.504
0.518
0.532
0.546
0.560
AUC
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
23
22
21
0.510
0.574
0.638
0.702
0.766
0.830
AUC
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
31
33
32
0.490
0.542
0.594
0.646
0.698
0.750
AUC
Celegans Gene ic
(ii)
( )
( iii)
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
13
11
12
0.590
0.632
0.674
0.716
0.758
0.800
AUC
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
23
22
21
0.61
0.65
0.69
0.73
0.77
0.81
AUC
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
31
33
32
0.630
0.668
0.706
0.744
0.782
0.820
AUC
CKM Physicians
(iii)
( i)
(ix)
(b)
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
13
11
12
0.000
0.018
0.036
0.054
0.072
0.090
P ec.
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
23
22
21
0.060
0.114
0.168
0.222
0.276
0.330
P ec.
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
31
33
32
0.00
0.01
0.02
0.03
0.04
0.05
P ec.
Copenhagen
(i)
(i )
( ii)
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
13
11
12
0.000
0.004
0.008
0.012
0.016
0.020
P ec.
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
23
22
21
0.000
0.052
0.104
0.156
0.208
0.260
P ec.
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
31
33
32
0.00
0.01
0.02
0.03
0.04
0.05
P ec.
Celegans Gene ic
(ii)
( )
( iii)
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
13
11
12
0.000
0.024
0.048
0.072
0.096
0.120
P ec.
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
23
22
21
0.030
0.052
0.074
0.096
0.118
0.140
P ec.
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
0
0. 1
0. 2
0. 3
0. 4
0. 5
0. 6
0. 7
0. 8
0. 9
1
31
33
32
0.010
0.026
0.042
0.058
0.074
0.090
P ec.
CKM Physicians
(iii)
( i)
(ix)
(a)
FIG. 2. (a) AUC and (b) p ecision o he MAA me ic o di e en alues o he coe icien s ηxα, indica ing he weigh o laye αin he
p edic ion o new links in laye x. Va ying he alues o wo coe icien s, he hi d is na u ally ixed. Each column co esponds o a di e en da a
se , ep esen ed as a mul iplex ne wo k o h ee laye s. Each ow co esponds o a p edic ion in a di e en laye x(see Table S2 o he SM [41]
o he co esponding in e ac ions). A c oss indica es he maximum alue o each plo , co esponding o he combina ion o coe icien s
(ηx1,ηx2,ηx3), epo ed in Table S2 o he SM [41], ha maximizes AUC o p ecision o he p edic ion o new links in laye x.
o di ec p o ein in e ac ions in C. elegans [i.e., he maximum
p ecision is ob ained o η13 =0.17 and η12 =0.22—see plo
(ii) o Fig. 2(b) and Table S2 o he SM [41]]. In e es ingly,
his e ec can be asymme ic: New o line in e ac ions (calls
and ex s) a e no p edic i e o Facebook iendships, as he
co esponding coe icien s η21 and η23 o his p edic ion ask
a e ze o. This is shown in plo s ( ii) o Figs. 2(a) and 2(b):
The maximum alue o he p ecision and AUC is ob ained
o η22 ≃1, in he le co ne o he plo s (see also Table S2
o he SM [41]). This implies ha no all laye s add aluable
in o ma ion o a speci ic link p edic ion ask. In his case,
a comple e mul iplex ep esen a ion is edundan and such a
laye can be e ec i ely included in he o he s wi hou missing
ele an in o ma ion.
Fu he mo e, we es i he MAA me ic is able o op i-
mally ex ac in o ma ion om he mul iplex ep esen a ion,
compa ed wi h he AA sco e applied o he agg ega e ne wo k,
ha includes he same amoun o in o ma ion. Table II shows
ha he MAA me ic ou pe o ms he classical AA sco e wi h
espec o bo h AUC and p ecision, in all da a se s unde con-
side a ion. Finally, in Table II we compa e he MAA me ic
wi h o he , s a e-o - he-a me ics o link p edic ion applied
o he agg ega ed ne wo k ep esen a ion, ha includes all
in o ma ion a ailable, in pa icula , common neighbo s (CN),
Jacca d’s coe icien (JC), and p e e en ial a achmen (PA),
which a e based on he one-s ep neighbo hoods o he nodes
such as he AA sco e [44], and he Ka z dis ance [45], which
ins ead is based on pa h leng h. Table II shows he p edic ion
o links in he i s laye o each da a se , and p edic ions in
o he laye s a e shown in Tables SIII and SIV o he SM [41],
wi h simila esul s. One can see ha he MAA me ic ou -
pe o ms he p ecision o all o he me ics in all bu one case
( he Lazega da a se ), while i ou pe o ms he AUC o o he
me hods in i e o eigh da a se s unde conside a ion.
Be o e concluding, we s ess ha he me ic encoded in
Eq. (2) is di e en om p e ious ex ensions o link p edic ion
o mul ilaye ne wo ks. Simila ly, o he app oaches calcula e
he sco e o each laye and agg ega e all o hem (possibly
wi h some weigh s), e ec i ely neglec ing s uc u es o ypes
Txαand Tαβ [25,46–48].
To sum up, we p oposed a gene al me hod o link p e-
dic ion ha ully exploi s di e en kinds o ela ional da a
encoded in se e al social and biological ne wo ks. Ou me ic
is a gene aliza ion o he Adamic-Ada sco e o mul iplex
ne wo ks wi h an a bi a y numbe o laye s, and i is able o
TABLE II. AUC ( op) and p ecision (bo om) o p edic he
i s laye o each da a se , ob ained o di e en me ics: Adamic-
Ada (AA), common neighbo s (CN), Jacca d simila i y (JC), Ka z
dis ance (Ka z), p e e en ial a achmen (PA), and mul iplex Adamic-
Ada (MAA). All me ics excep o he MAA a e applied o he
agg ega ed ne wo k, including all in o ma ion a ailable. The bes
me hod is highligh ed in bold.
Me hod CNS CEG CEN CSA CKM EUA VIC LAZ
AA 0.76 0.55 0.79 0.79 0.80 0.86 0.68 0.66
CN 0.76 0.55 0.78 0.78 0.80 0.86 0.67 0.66
JC 0.76 0.55 0.77 0.88 0.80 0.82 0.68 0.70
Ka z 0.72 0.59 0.77 0.74 0.91 0.89 0.65 0.58
PA 0.58 0.65 0.62 0.39 0.64 0.90 0.61 0.54
MAA 0.77 0.55 0.79 0.91 0.80 0.87 0.71 0.71
AA 0.00 0.00 0.03 0.03 0.09 0.00 0.35 0.14
CN 0.00 0.00 0.03 0.03 0.10 0.00 0.35 0.13
JC 0.00 0.00 0.02 0.32 0.08 0.00 0.40 0.23
Ka z 0.00 0.00 0.00 0.00 0.00 0.00 0.31 0.00
PA 0.00 0.00 0.02 0.00 0.01 0.02 0.27 0.09
MAA 0.09 0.02 0.08 0.39 0.11 0.19 0.46 0.21
042029-4
LINK PREDICTION IN MULTIPLEX NETWORKS VIA … PHYSICAL REVIEW RESEARCH 2, 042029(R) (2020)
ou pe o m single-laye ed AA sco es in all conside ed da a
se s. The MAA me ic also ou pe o ms se e al well-known
link p edic ion algo i hms, such as he Jacca d’s coe icien
o he Ka z dis ance. The coe icien s ηxα ha maximize he
MAA sco e ha e an in e es ing in e p e a ion, as hey co -
espond o he weigh o be assigned o each laye in o de
o op imize he in o ma ion s uc u ed in he ne wo k o he
link p edic ion ask, indica ing which laye s a e edundan .
In e es ingly, his e ec can be asymme ic wi h espec o
p edic ions in di e en laye s. The compu a ional complexi y
o he MAA me ic is simila o o he simila i y-based sco es.
Wi h espec o he classical AA sco e, i inc eases wi h he
numbe o laye s in he mul iplex ne wo k, which is usually
small. No e ha he iadic ela ionships need o be compu ed
jus once and s o ed, hen he whole ange o coe icien s
can be scanned o ob ain he ones ha maximize he MAA
sco e. In u u e wo ks, i would be in e es ing o gene alize
o mul iplex ne wo ks o he me ics based on single laye s,
such as he Ka z dis ance, which is based on pa hs ha can be
econs uc ed ac oss laye s.
We acknowledge suppo om In esa Sanpaolo Inno a ion
Cen e . Y.M. acknowledges pa ial suppo om he Go e n-
men o A agón and FEDER unds, Spain h ough G an No.
E36-20R o FENOL, and by MINECO and FEDER unds
(G an No. FIS2017-87519-P). D.P. and M.S. acknowledge
inancial suppo om he p ojec Casa nel Pa co (POR FESR
14/20 - CANP - Cod. 320 - 16) unded by Regione Piemon e.
The unde s had no ole in s udy design, da a collec ion, and
analysis, decision o publish, o p epa a ion o he manusc ip .
[1] M. Newman, Ne wo ks: An In oduc ion (Ox o d Uni e si y
P ess, Ox o d, 2010).
[2] B. Taska , M. Fai Wong, P. Abbeel, and D. Kolle , in Ad ances
in Neu al In o ma ion P ocessing Sys ems 16,edi edbyS.
Th un, L. K. Saul, and B. Schölkop (MIT P ess, Camb idge,
MA, 2004), pp. 659–666.
[3] L. Lu and T. Zhou, Physica A 390, 1150 (2011).
[4] R. N. Lich enwal e , J. T. Lussie , and N. V. Chawla, in P o-
ceedings o he 16 h ACM SIGKDD In e na ional Con e ence
on Knowledge Disco e y and Da a Mining, KDD ’10 (ACM
P ess, New Yo k, 2010), pp. 243–252.
[5] L. A. N. Ama al, P oc. Na l. Acad. Sci. USA 105, 6795 (2008).
[6] D. Liben-Nowell and J. Kleinbe g, in P oceedings o he
Twel h In e na ional Con e ence on In o ma ion and Knowl-
edge Managemen , CIKM ’03 (ACM P ess, New Yo k, 2003),
pp. 556–559.
[7] M. A. Hasan and M. J. Zaki, in Social Ne wo k Da a Analy -
ics, edi ed by C. C. Agga wal (Sp inge , Bos on, MA, 2011),
pp. 243–275.
[8] B. Taska , P. Abbeel, and D. Kolle , in P oceedings o he
Eigh een h Con e ence on Unce ain y in A i icial In elli-
gence, UAI’02 (Mo gan Kau mann, San F ancisco, CA, 2002),
pp. 485–492.
[9] W. Liu and L. Lu, Eu ophys. Le . 89, 58007 (2010).
[10] R. Guime à and M. Sales-Pa do, P oc. Na l. Acad. Sci. USA
106, 22073 (2009).
[11] M. Ma jan, N. Zaki, and E. A. Mohamed, in P oceedings o he
2018 IEEE 5 h In e na ional Cong ess on In o ma ion Science
and Technology (CiS ) (IEEE, New Yo k, 2018), p. 200.
[12] V. Ma ínez, F. Be zal, and J. C. Cube o, ACM Compu . Su .
49, 69 (2016).
[13] C. A. Bliss, M. R. F ank, C. M. Dan o h, and P. S. Dodds,
J. Compu . Sci. 5, 750 (2014).
[14] L. A. Adamic and E. Ada , Soc. Ne w. 25, 211 (2003).
[15] A. Clause , C. Moo e, and M. E. J. Newman, Na u e (London)
453, 98 (2008).
[16] T. Jia, Y. Ran, and X. Xu, in P oceedings o Ne Sci-X 2020:
Six h In e na ional Win e School and Con e ence on Ne wo k
Science (Sp inge , Be lin, 2020).
[17] M. Ki elä, A. A enas, M. Ba helemy, J. P. Gleeson, Y. Mo eno,
andM.A.Po e ,J. Complex Ne w. 2, 203 (2014).
[18] A. Ale a and Y. Mo eno, Annu. Re . Condens. Ma e Phys. 10,
45 (2019).
[19] D. Da is, R. Lich enwal e , and N. V. Chawla, Soc. Ne w. Anal.
Min. 3, 127 (2013).
[20] K.-K. Kleinebe g, M. Boguñá, M. Ángeles Se ano, and F.
Papadopoulos, Na . Phys. 12, 1076 (2016).
[21] M. Al Hasan, V. Chaoji, S. Salem, and M. Zaki, in P oceedings
o he SDM06: Wo kshop on Link Analysis, Coun e e o ism
and Secu i y (SIAM, Ma yland, 2006), Vol. 30, pp. 798–805.
[22] Z. Lu, B. Sa as, W. Tang, and I. S. Dhillon, in P oceedings o
he2010IEEEIn e na ionalCon e enceonDa aMining (IEEE,
New Yo k, 2010), p. 923.
[23] R. Ma suno and T. Mu a a, in Companion P oceedings o he
TheWebCon e ence2018,WWW’18 (In e na ional Wo ld Wide
Web Con e ences S ee ing Commi ee, Republic and Can on o
Gene a, CHE, 2018), pp. 1261–1268.
[24] M. Puja i and R. Kanawa i, Ne w. He e og. Media 10,17
(2015).
[25] K. So i opoulos, J. W. Bye s, P. P a ikakis, and C. E.
Tsou akakis, in P oceedingso he57 hAnnualAlle onCon e -
ence on Communica ion, Con ol, and Compu ing (IEEE, New
Yo k, 2019), pp. 973–980.
[26] A. Hajibaghe i, G. Suk hanka , and K. Lakka aju, in P o-
ceedings o he 2016 IEEE/ACM In e na ional Con e ence on
Ad ances in Social Ne wo ks Analysis and Mining (ASONAM)
(IEEE, New Yo k, 2016), p. 1079.
[27] L. Yao, L. Wang, L. Pan, and K. Yao, P oc. Compu . Sci. 83,82
(2016).
[28] M. Jalili, Y. O ouskhani, M. Asga i, N. Alipou a d, and M.
Pe c, R. Soc. Open Sci. 4, 160863 (2016).
[29] D. H is o a, A. Noulas, C. B own, M. Musolesi, and C.
Mascolo, EPJ Da a Sci. 5, 1 (2016).
[30] H. Mandal, M. Mi che , S. G ama iko , and I. Mishko ski,
in P oceedings o he 2018 26 h Telecommunica ions Fo um
(TELFOR) (IEEE, New Yo k, 2018), p. 1.
[31] R. R. Junu hula, K. S. Xu, and V. K. De abhak uni,
a Xi :1804.08584.
[32] M. De Domenico, V. Nicosia, A. A enas, and V. La o a,
Na . Commun. 6, 6864 (2015).
[33] P. Sapiezynski, A. S opczynski, D. D. Lassen, and S. Lehmann,
Sci. Da a 6, 315 (2019).
042029-5

ALBERTO ALETA e al. PHYSICAL REVIEW RESEARCH 2, 042029(R) (2020)
[34] C. S a k, B.-J. B ei k eu z, T. Reguly, L. Bouche , A.
B ei k eu z, and M. Tye s, Nucl. Acids Res. 34, D535 (2006).
[35]B.L.Chen,D.H.Hall,andD.B.Chklo skii,P oc. Na l. Acad.
Sci. USA 103, 4723 (2006).
[36] M. Magnani, B. Micenko a, and L. Rossi, a Xi :1303.4986.
[37] J. Coleman, E. Ka z, and H. Menzel, Sociome y 20, 253
(1957).
[38] A. Ca dillo, J. Gómez-Ga deñes, M. Zanin, M. Romance, D.
Papo, F. del Pozo, and S. Boccale i, Sci. Rep. 3, 1344 (2013).
[39] E. Lazega, The Collegial Phenomenon: The Social Mechanisms
o Coope a ion Among Pee s in a Co po a e Law Pa ne ship
(Ox o d Uni e si y P ess, Ox o d, UK, 2001).
[40] M. Vicke s and S. Chan, Rep esen ing Class oom Social S uc-
u e (Vic o ia Ins i u e o Seconda y Educa ion, Melbou ne,
1981).
[41] See Supplemen al Ma e ial a h p://link.aps.o g/supplemen al/
10.1103/PhysRe Resea ch.2.042029 o Figu es, and Tables.
[42] F. Ba is on, V. Nicosia, and V. La o a, Phys.Re .E89, 032804
(2014).
[43] E. Cozzo, M. Ki elä, M. De Domenico, A. Solé-Ribal a, A.
A enas, S. Gómez, M. A. Po e , and Y. Mo eno, New J. Phys.
17, 073029 (2015).
[44] F. Gao, K. Musial, C. Coope , and S. Tsoka, Sci. P og am. 2015,
172879 (2015).
[45] L. Ka z, Psychome ika 18, 39 (1953).
[46] S. Sha ma and A. Singh, AnE icien Me hod o LinkP edic ion
in Complex Mul iplex Ne wo ks (IEEE, New Yo k, 2015).
[47] Y. Yao, R. Zhang, F. Yang, Y. Yuan, Q. Sun, Y. Qiu, and R. Hu,
In . J. Mod. Phys. C 28, 1750101 (2017).
[48] Z. Samei and M. Jalili, J. Complex Ne w. 7, 641 (2019).
042029-6