鏈路預(yù)測問題研究現(xiàn)狀文獻綜述復(fù)雜網(wǎng)絡(luò)的研究距今已有20年的歷史。在這20年里，科學(xué)家們幾乎在每個領(lǐng)域里都進行了鏈路預(yù)測的研究。不同的領(lǐng)域所形成的網(wǎng)絡(luò)特點總是有所差別的，而面對這些特點不一的網(wǎng)絡(luò)結(jié)構(gòu)，學(xué)者們也對此提出了適用不同網(wǎng)絡(luò)結(jié)構(gòu)的算法，方法分類如圖1.1。圖1.1鏈路預(yù)測方法分類圖最早的鏈路預(yù)測采用的方法比較簡單，主要是通過利用網(wǎng)絡(luò)中節(jié)點的屬性信息進行預(yù)測。這種方法取得了較好的預(yù)測效果，但存在一個弊端。因為在大多數(shù)情況下，節(jié)點的屬性信息是很難獲取到的。正是由于這樣的原因，很多學(xué)者不得不去尋找一種更容易實現(xiàn)的方法進行鏈路預(yù)測，而通過不斷的思考，學(xué)者們想到了通過網(wǎng)絡(luò)的結(jié)構(gòu)去進行預(yù)測。網(wǎng)絡(luò)結(jié)構(gòu)是一個比較宏觀的東西，相比于節(jié)點信息不那么具體，但這也意味著更容易獲得到，并且一個網(wǎng)絡(luò)的結(jié)構(gòu)一般不輕易改變，具有更好的可靠性，同時這一類方法能夠非常好的適用于那些具有相似結(jié)構(gòu)的網(wǎng)絡(luò)。在進行鏈路預(yù)測時我們通常會嘗試去獲取到網(wǎng)絡(luò)節(jié)點和網(wǎng)絡(luò)的拓撲結(jié)構(gòu)信息，如果將這兩種信息都利用上的預(yù)測算法一般我們稱之為基于相似性的算法。按研究范圍大小來劃分，這類算法大致可以分為三類REF_Ref4107\r\h[11]，基于局部、全局以及準局部三類?；诰W(wǎng)絡(luò)局部結(jié)構(gòu)的預(yù)測算法是比較簡單的，但也是最直觀并且相對有效的。這類算法考慮的信息非常少，僅僅是利用了網(wǎng)絡(luò)節(jié)點的鄰居信息，不考慮額外的因素，計算復(fù)雜度很低，因此非常適合在大規(guī)模網(wǎng)絡(luò)中應(yīng)用。但是受到信息量的限制，它的預(yù)測精度往往不太理想，比如主要考慮共同鄰居數(shù)量的共同鄰居指標REF_Ref3611\r\h[2]REF_Ref4176\r\h[12]、主要考慮節(jié)點度乘積信息的偏好連接指標REF_Ref3611\r\h[2]REF_Ref4254\r\hREF_Ref5890\r\h[13]、主要考慮共同鄰居度值信息的Adamic-Adar指標REF_Ref4381\r\h[14]、主要考慮共同鄰居相似性的Jaccard指標REF_Ref3611\r\h[2]REF_Ref4434\r\h[15]、被稱為余弦相似性指標的SaltonREF_Ref3611\r\h[2]REF_Ref4476\r\h[16]和從資源角度出發(fā)的資源分配指標REF_Ref4538\r\h[17]等相似性指標。相比之下，基于全局結(jié)構(gòu)的相似性算法考慮了整個的網(wǎng)絡(luò)結(jié)構(gòu)信息，因此在進行預(yù)測時能有更多的參考信息，使得預(yù)測精度有了較大的提升，但由于需要計算全局的節(jié)點，因此計算時間也大大增加了，時間復(fù)雜度較高。這類算法的代表有考慮網(wǎng)絡(luò)所有路徑的Katz指標REF_Ref3611\r\h[2]REF_Ref6311\r\h[19]，與其相似的LHN-II指標REF_Ref3611\r\h[2]REF_Ref4604\r\h[18]，通過引入隨機游走粒子的重啟的隨機游走指標REF_Ref6341\r\h[20]、SimRank指標REF_Ref3611\r\h[2]REF_Ref6452\r\h[22]，以及考慮時間因素的平均通勤時間指標REF_Ref3611\r\h[2]REF_Ref6396\r\h[21]等。而基于準局部結(jié)構(gòu)的預(yù)測算法，則是可以看作是以上兩種算法的中和，它考慮了比局部指標更多的因素，但又不需要考慮與全局指標一樣多的信息量，具備了較好的算法精度同時時間復(fù)雜度也較低。這類算法的代表有只考慮局部的局部隨機游走指標REF_Ref6573\r\h[23]和只考慮局部路徑的局部路徑相似性指標REF_Ref4538\r\h[17]以及存在疊加效應(yīng)的局部游走指標REF_Ref6452\r\h[22]等。一直以來對基于相似性算法的研究從未間斷過，經(jīng)過學(xué)者們的努力，一些優(yōu)秀成果也相繼出現(xiàn)。在引用網(wǎng)絡(luò)方面，賈等人通過對大量的網(wǎng)絡(luò)實驗進行總結(jié)，提出了一個全新的指數(shù)：H指數(shù)REF_Ref6703\r\h[24]，并將網(wǎng)絡(luò)中度的概念清除了，改為用H指數(shù)表示。與先前的研究方式不同，他們對每條引文都設(shè)置了權(quán)重，通過權(quán)重來區(qū)分引文的重要性，然后再在Sorenson指標REF_Ref3611\r\h[2]REF_Ref6749\r\h[25]、Salton指標REF_Ref3611\r\h[2]REF_Ref6801\r\h[26]和AA指標REF_Ref4381\r\h[14]三種鏈路預(yù)測方法的基礎(chǔ)上進行了改進。大量的實驗結(jié)果表明他們的改進方法很有效，在引文網(wǎng)絡(luò)中擁有優(yōu)秀的表現(xiàn)。經(jīng)典相似性指標一般都與共同鄰居節(jié)點有著聯(lián)系，Cannistraci等人REF_Ref6876\r\h[27]將這種聯(lián)系進行了增強，成功設(shè)計出了一種新的鏈路預(yù)測算法：資源分配相似性預(yù)測算法CAR。周等人REF_Ref6922\r\h[28]提出了在復(fù)雜網(wǎng)絡(luò)中知識是依靠路徑進行傳播的假設(shè)，定義了知識在復(fù)雜網(wǎng)絡(luò)中的傳播機制。在這個假設(shè)的基礎(chǔ)上，呂等人REF_Ref6968\r\h[29]又提出了KDLP全路徑預(yù)測指標。高等人REF_Ref7017\r\h[30]將網(wǎng)絡(luò)分成一個一個的局部結(jié)構(gòu)，并以網(wǎng)絡(luò)中最小的局部結(jié)構(gòu)三元閉包為單位，單獨考慮節(jié)點在相鄰的三元閉包中的權(quán)重，并把這個權(quán)重作為節(jié)點相似性指標的一個影響因素，由于這樣做使獲得的節(jié)點信息更精確，極大的提高了算法的預(yù)測精度，但同時也令算法的時間復(fù)雜度大幅上升。劉等人REF_Ref7063\r\h[31]提出了擴展資源分配指標，如果一個端點與另一個端點的共同鄰居與非共同鄰居有著很大的資源交互，那么這兩個端點就具有很高的相似性，反之則很小。孫等人REF_Ref7102\r\h[32]通過節(jié)點親密關(guān)系這一角度出發(fā)，提出了局部親和結(jié)構(gòu)指標。武等人REF_Ref7151\r\h[33]設(shè)計了一個考慮網(wǎng)絡(luò)節(jié)點聚類系數(shù)的預(yù)測指標CCLP，并在該指標上進行擴展，在計算相似性時不僅將節(jié)點聚類信息考慮進來，同時也把邊聚類信息也加以考慮，提出了NLC算法REF_Ref7239\r\h[34]，最大似然估計類算法是通過模型與現(xiàn)實結(jié)構(gòu)進行對比來進行預(yù)測，不斷更改模型的參數(shù)，讓其與已知的結(jié)構(gòu)能進行最大概率的結(jié)合，以此來尋找網(wǎng)絡(luò)中缺失的鏈接。目前，這類算法主要存在兩種，一種是在網(wǎng)絡(luò)的層次結(jié)構(gòu)信息基礎(chǔ)上進行研究的，由Clauset等人REF_Ref7285\r\h[35]在2008年提出。這類方法對兩節(jié)點之間是否存在連接進行判斷時，不是考慮節(jié)點本身，而是通過節(jié)點的共同祖先的存在概率值來判斷。兩節(jié)點存在共同祖先的概率越高，它們之間越有可能存在連接，類似于一種家庭關(guān)系。另外一種是隨機塊模型方法，是由GuimeràREF_Ref3875\r\h[9]提出的。如圖1.2所示，在這個模型中，如果集群具有很高的密切度，那么兩個節(jié)點之間將有很大的概率進行連接。另一種最大似然方法是閉路模型方法，是由呂等人REF_Ref7425\r\h[36]提出的。尋找出網(wǎng)絡(luò)中的閉合回路，并將其看成是一種局部性，網(wǎng)絡(luò)中的似然值通過閉合環(huán)路的多少來進行定義，如果我們想要知道某一條缺失邊存在的概率，那么向該網(wǎng)絡(luò)添加這條邊后計算出網(wǎng)絡(luò)的似然值，這個值就是我們想知道的缺失邊存在的概率。總而言之，這種基于最大化網(wǎng)絡(luò)似然函數(shù)的預(yù)測算法通過模擬網(wǎng)絡(luò)的最大結(jié)構(gòu)，可以很清楚的將缺失的連接表示出來，并且還能讓我們看到網(wǎng)絡(luò)更深層次的特征，但存在的問題是這類算法一般都具有較高的時間復(fù)雜度，因為它對網(wǎng)絡(luò)頂點的個數(shù)非常敏感。還有一種是基于矩陣分解的預(yù)測算法REF_Ref7467\r\h[37]REF_Ref7474\r\h[38]，一般網(wǎng)絡(luò)數(shù)據(jù)中會存在著許多潛在的特征，這種方法是先將這些潛在特征尋找出來并且對其進行學(xué)習(xí)，利用潛在特征的信息去對網(wǎng)絡(luò)連接進行預(yù)測。每個節(jié)點都會有一定數(shù)量的潛在特征，通過節(jié)點的潛在特征相似程度來對節(jié)點的相似性進行衡量REF_Ref7536\r\h[39]。圖1.2網(wǎng)絡(luò)（a）與隨機塊模型（b）除了以上提到的算法，在對網(wǎng)絡(luò)的噪音過濾以及對網(wǎng)絡(luò)進行重構(gòu)方面還存在一些特定的鏈路預(yù)測方法。這類方法考慮到了網(wǎng)絡(luò)可能存在噪音等情況，在算法邏輯中進行了特殊的處理，使得算法具備良好的健壯性。如Zhang等人REF_Ref7588\r\h[40]為了彌補局部路徑上路徑提供的參考區(qū)分度不大的缺點提出了加權(quán)的局部路徑鏈路預(yù)測指標。為了解決在進行網(wǎng)絡(luò)重構(gòu)后網(wǎng)絡(luò)的結(jié)構(gòu)特性很難保持與原網(wǎng)絡(luò)一致的難題，Zeng等人REF_Ref7634\r\h[41]提出了一種預(yù)測模型，該模型由共同鄰居和網(wǎng)絡(luò)中邊的中心性混合生成。實驗表明，這個模型很好的解決了上述問題。呂等人REF_Ref7680\r\h[42]又從鄰接矩陣的擾動因素出發(fā)，提出了結(jié)構(gòu)一致性預(yù)測指標。類似的工作還有對于存在噪音的網(wǎng)絡(luò)環(huán)境下，然后對算法的健壯性進行評價的評價方法REF_Ref7722\r\h[43]，還有研究能將網(wǎng)絡(luò)中出現(xiàn)的噪音過濾的鏈路預(yù)測方法REF_Ref7765\r\h[44]等。在目前的鏈路預(yù)測算法研究中，由于設(shè)備與技術(shù)的限制，研究對象更多是規(guī)模較小的小型網(wǎng)絡(luò)，對于大規(guī)模網(wǎng)絡(luò)的研究還是比較稀缺的。同時，現(xiàn)在網(wǎng)絡(luò)的表現(xiàn)形式大都是以離散鄰接矩陣來進行表示的，學(xué)術(shù)界目前主流的研究方向也是對該種表現(xiàn)形式網(wǎng)絡(luò)的研究。然而，隨著科學(xué)技術(shù)的飛速發(fā)展，大規(guī)模信息的網(wǎng)絡(luò)時代即將來臨，這種網(wǎng)絡(luò)表示方式也出現(xiàn)了越來越多的問題。一方面來說，離散鄰接矩陣表示的網(wǎng)絡(luò)能獲取到的信息較少，只能夠獲取到頂點之間的相鄰關(guān)系，在這種情況下，當(dāng)需要構(gòu)建當(dāng)下復(fù)雜網(wǎng)絡(luò)中更復(fù)雜的高階網(wǎng)絡(luò)結(jié)構(gòu)關(guān)系的時候，比如路徑、頻繁的子結(jié)構(gòu)等，則會因信息不足而導(dǎo)致構(gòu)建出來的子結(jié)構(gòu)不是很完整，同時在這種網(wǎng)絡(luò)表現(xiàn)形式下，如果我們想要獲取到節(jié)點除屬性外所攜帶的外部的信息也會存在較大的困難。另一方面，當(dāng)系統(tǒng)需要處理的網(wǎng)絡(luò)規(guī)模非常巨大時，網(wǎng)絡(luò)的離散鄰接矩陣將也會變得非常巨大，因此想要完成鏈路預(yù)測就需要對處理器的性能和存儲有較高的要求。由于以上兩個原因，部分學(xué)者們意識到想要克服今后網(wǎng)絡(luò)鏈路預(yù)測所可能遇到的困難，就需要從網(wǎng)絡(luò)表示的方式尋找突破口，讓其對于未來更多多樣化的鏈路預(yù)測需求能提供更好的幫助。遺憾的是，該方向的研究進展并不是很順利，到目前為止，網(wǎng)絡(luò)表示算法的數(shù)量仍然是很少，而其中大部分又都是和任務(wù)無關(guān)的實現(xiàn)。參考文獻LüLY,ZhouT.Linkpredictionincomplexnetworks:Asurvey[J].PhysicaAStatisticalMechanics&ItsApplications,2010,390(6):1150-1170.張斌,馬費成.科學(xué)知識網(wǎng)絡(luò)中的鏈路預(yù)測研究述評[J].中國圖書館學(xué)報,2015,41(3):99-113LeiC,RuanJ.Anovellinkpredictionalgorithmforreconstructingprotein–proteininteractionnetworksbytopologicalsimilarity[J].Bioinformatics,2012,29(3):355-364.BoucherB,JennaS.Geneticinteractionnetworks:betterunderstandtobetterpredict[J].Frontiersingenetics,2013,4:290.R?ttgerR,RückertU,TaubertJ,etal.Howlittledoweactuallyknow?Onthesizeofgeneregulatorynetworks[J].IEEE/ACMtransactionsoncomputationalbiologyandbioinformatics,2012,9(5):1293-1300PanL,ZhouT,LüLY,etal.Predictingmissinglinksandidentifyingspuriouslinksvialikelihoodanalysis[J].Scientificreports,2016,6:22955Al-HalahZ,TapaswiM,StiefelhagenR.Recoveringthemissinglink:Predictingclass-attributeassociationsforunsupervisedzero-shotlearning[C].ProceedingsoftheIEEEConferenceonComputerVisionandPatternRecognition.2016:5975-5984.KleinbergJ.Analysisoflarge-scalesocialandinformationnetworks[J].Philosophicaltransactions.SeriesA,Mathematical,physical,andengineeringsciences.2013,371(1987):20120378.LiaoH,ZengA.Reconstructingpropagationnetworkswithtemporalsimilarity[J].Scientificreports,2015,5:11404.DasD.PositiveandNegativeLinkPredictionAlgorithmBasedonSentimentAnalysisinLargeSocialNetworks[J].WirelessPersonalCommunications,2018(2):1-16.ChenB,ChenL,LiB.Afastalgorithmforpredictinglinkstonodesofinterest[J].InformationSciences,2016,2016(329):552-567.Newman,M.E.Clusteringandpreferentialattachmentingrowingnetworks[J].PhysicalRe