Link prediction in multiplex networks via triadic closure

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