來(lái)源：《中國計算機學(xué)會(huì )通訊》2016年第4期《專(zhuān)題》
作者：呂琳媛 任曉龍 周濤
引言
在網(wǎng)絡(luò )科學(xué)發(fā)展早期，研究主要聚焦在發(fā)掘不同網(wǎng)絡(luò )所遵循的普適規律，如小世界規律、無(wú)標度現象、社團結構等。隨著(zhù)研究的深入，人們發(fā)現宏觀(guān)指標以及基于宏觀(guān)量的運算使得個(gè)體的特征被“平均化”，一些關(guān)鍵個(gè)體的表現被淹沒(méi)了，導致得到的結論僅在統計上有意義，卻難以進(jìn)行精細的定量化描述。譬如說(shuō)知道一個(gè)網(wǎng)絡(luò )的稀疏程度、平均距離或者平均簇系數，并不代表就知道了某個(gè)具體節點(diǎn)的度和局部結構，因為不同節點(diǎn)之間相差甚遠。因此，要想獲得真正精細可靠的解釋?zhuān)捅仨氝M(jìn)行微觀(guān)層面的深入分析。近年來(lái)，網(wǎng)絡(luò )科學(xué)研究逐漸從發(fā)掘不同網(wǎng)絡(luò )宏觀(guān)上的普適規律，轉為更多地從介觀(guān)層面（如網(wǎng)絡(luò )的社團結構、層級、群組結構等）和微觀(guān)層面（如節點(diǎn)和鏈路）研究各類(lèi)網(wǎng)絡(luò )的特征。
鏈路預測(link prediction)作為網(wǎng)絡(luò )科學(xué)研究中一個(gè)重要且有趣的問(wèn)題，本質(zhì)上是從網(wǎng)絡(luò )鏈路的微觀(guān)層面解釋網(wǎng)絡(luò )結構生成的原因，進(jìn)而幫助我們更好地理解網(wǎng)絡(luò )所對應的復雜系統的結構生成和演化規律。
什么是鏈路預測？
作為連接網(wǎng)絡(luò )科學(xué)與信息科學(xué)的重要橋梁之一，鏈路預測處理的是信息科學(xué)中最基本的問(wèn)題——缺失信息的還原與預測。該問(wèn)題從已觀(guān)察到的網(wǎng)絡(luò )結構入手，預測存在但未被觀(guān)察到，或者未來(lái)可能會(huì )出現的鏈路——可以說(shuō)，鏈路預測探討的是復雜網(wǎng)絡(luò )中的“哈姆雷特”問(wèn)題：連，還是不連？鏈路預測不僅能推動(dòng)網(wǎng)絡(luò )科學(xué)理論的發(fā)展，而且具有巨大的實(shí)際應用價(jià)值。
鏈路預測有著(zhù)廣泛的應用場(chǎng)景（如圖1所示）。例如，用于指導生物實(shí)驗以提高實(shí)驗成功率，對社交網(wǎng)絡(luò )中的朋友推薦和敵友關(guān)系進(jìn)行預測，電子商務(wù)網(wǎng)站上的商品推薦，以及通過(guò)識別隱藏的鏈邊和虛假的鏈邊對信息不完全或含有噪音的網(wǎng)絡(luò )進(jìn)行重構。這些應用場(chǎng)景都是顯而易見(jiàn)的。然而有趣的是，鏈路預測的算法和思想通過(guò)一些變換還可以用來(lái)解決一些看似沒(méi)有太大關(guān)系的問(wèn)題。例如，對疾病信號和股票指數的預測?；阪溌奉A測的思想和方法，我們還可以設計基于節點(diǎn)相似性的社團劃分以及對網(wǎng)絡(luò )演化模型的定量化評估方法。鏈路預測還可以幫助提高節點(diǎn)標簽預測的精度，特別是在已知標簽節點(diǎn)稀疏的情況下效果顯著(zhù)。這一方法可以應用于判斷一篇學(xué)術(shù)論文的類(lèi)型，判斷一本書(shū)的政治態(tài)度（中立、自由派或保守派），或者判斷一個(gè)手機用戶(hù)是否產(chǎn)生了更換電信運營(yíng)商的念頭。
衡量鏈路預測算法精確度最常見(jiàn)的指標是AUC（Area Under ROC Curve，ROC曲線(xiàn)下面積）和準確率。AUC是從整體上衡量算法的精確度，可以理解為在測試集中隨機選擇一條邊的分數值比隨機選擇一條不存在的邊的分數值高的概率。這里，一條邊的分數值由預測算法給出，分數值越高表示這條邊出現的概率越高。準確率主要考慮預測列表中排在前L位的邊的預測正確率。AUC實(shí)際上是指ROC （Receiver Operating Characteristic，受試者工作特征）曲線(xiàn)下的面積。在實(shí)際計算中，可以采用抽樣比較的方法得到近似值，即每次從測試集中隨機選取一條邊，再從“不存在的邊”集合中隨機選擇一條，如果前者分數值大于后者就加1分，如果兩者分數值相等就加0.5分。這樣獨立比較多次后，求得的平均分數就是AUC。顯然，如果所有分數都是隨機產(chǎn)生的，則AUC約等于0.5，因此AUC大于0.5的程度衡量了該算法在多大程度上比隨機選擇的方法更精確。
在有些文獻中也經(jīng)常使用召回率(Recall)、假陽(yáng)性率(False Positive Rate, FPR)、F1等指標評價(jià)算法的性能。召回率指存在的連邊中被預測準確的比例，假陽(yáng)性率等于把不存在的連邊誤判為存在的連邊的比例，F1指標又稱(chēng)為平衡F分數，定義為準確率和召回率的調和平均數。
鏈路預測的方法
基于節點(diǎn)屬性相似性的鏈路預測??
物以類(lèi)聚，人以群分。兩個(gè)節點(diǎn)的屬性越相似，就越可能產(chǎn)生聯(lián)系。由于在線(xiàn)社交數據相對容易獲取，所以目前這方面的研究主要集中在社交網(wǎng)絡(luò )上，但這些方法都能夠很容易地推廣到其他網(wǎng)絡(luò )的鏈路預測中。在社交網(wǎng)絡(luò )中，刻畫(huà)節點(diǎn)的屬性相似性，最簡(jiǎn)單直接的方法就是使用標簽。例如，考察兩個(gè)節點(diǎn)之間的年齡、職業(yè)、教育、興趣、地理位置、性別、信仰等屬性的相似程度，對節點(diǎn)對之間產(chǎn)生聯(lián)系或者節點(diǎn)對之間關(guān)系的演化做出預測。例如，對一所大學(xué)中4萬(wàn)多名師生一年內電子郵件的交流情況（包括發(fā)送者、接收者、時(shí)間戳）、個(gè)人信息（年齡、性別、科系、年級）以及每名學(xué)生/教師的上課情況的研究發(fā)現，屬性相似的學(xué)生/教師之間有更多交流。這一結論在含有1.8億人和13億條無(wú)向邊的MSN在線(xiàn)社交網(wǎng)絡(luò )上也得到了驗證——人們更愿意和與自己年齡相仿、使用相同的語(yǔ)言、地理位置相近的人聊天。當用戶(hù)標簽不全、存在大量缺失時(shí)，可以用局部社交網(wǎng)絡(luò )結構來(lái)補充用戶(hù)的標簽。在節點(diǎn)的標簽并非顯而易見(jiàn)時(shí)，可以分析描述節點(diǎn)屬性的文本相似性。例如，用網(wǎng)絡(luò )上用戶(hù)收藏/發(fā)表的內容、參與的話(huà)題等信息計算用戶(hù)之間的話(huà)題相似性并進(jìn)行好友預測。
基于網(wǎng)絡(luò )結構相似性的鏈路預測
很多時(shí)候，我們很難獲得網(wǎng)絡(luò )中真實(shí)可信的節點(diǎn)屬性信息。此時(shí)，根據所觀(guān)察到的網(wǎng)絡(luò )結構來(lái)計算節點(diǎn)相似性是一個(gè)可行且可信的方法?；诰W(wǎng)絡(luò )結構相似性的方法假設：在網(wǎng)絡(luò )中，兩個(gè)節點(diǎn)之間相似性（或者相近性）越大，它們之間存在連邊的可能性就越大。與節點(diǎn)屬性的相似性不同的是，這里的相似性?xún)H依賴(lài)于網(wǎng)絡(luò )結構。
基于局部信息的最簡(jiǎn)單的相似性指標是優(yōu)先連接(Preferential Attachment, PA)。應用優(yōu)先連接的方法可以產(chǎn)生無(wú)標度網(wǎng)絡(luò )結構。在該網(wǎng)絡(luò )中，一條即將加入的新邊連接到節點(diǎn)x的概率正比于節點(diǎn)x的度，因此，新邊連接節點(diǎn)x和y的概率正比于兩節點(diǎn)度的乘積。因為需要的信息量非常少，所以該算法的計算復雜度較低。
另一個(gè)基于局部信息的相似性指標是共同鄰居(Common Neighbor, CN)，即兩個(gè)節點(diǎn)如果有更多的共同鄰居，則它們更傾向于連邊。在共同鄰居的基礎上考慮兩端節點(diǎn)度的影響，從不同的角度又產(chǎn)生6種相似性指標，分別是索爾頓(Salton)指標（也叫余弦相似性）、雅卡爾(Jaccard)指標、索倫森(Sorenson)指標、大度節點(diǎn)有利指標(Hub Promoted Index）、大度節點(diǎn)不利指標(Hub Depressed Index)和LHN-I指標。這一類(lèi)指標統稱(chēng)為“基于共同鄰居的相似性指標”。
在這些指標中，共同鄰居對節點(diǎn)對之間產(chǎn)生連邊都有促進(jìn)作用，且不同的共同鄰居的貢獻是相等的。然而，一般情況下我們會(huì )覺(jué)得大度的共同鄰居比小度的共同鄰居貢獻小。舉個(gè)直觀(guān)的例子，兩個(gè)人都喜歡看同一部熱門(mén)電影，這并不能說(shuō)明兩個(gè)人的興趣品味有多相似。相反，如果這兩個(gè)人同時(shí)喜歡一部冷門(mén)電影，那么可以說(shuō)他們至少在這方面具有相似的品味?；谶@樣的考慮，阿達密克(Adamic)和阿達爾(Adar)提出了AA指標，他們根據共同鄰居節點(diǎn)的度為每個(gè)節點(diǎn)賦予一個(gè)權重值，該權重等于該節點(diǎn)的度的對數分之一。于是AA指標就等于兩個(gè)節點(diǎn)的所有共同鄰居的權重值之和。巧合的是，資源分配指標(Resource Allocation, RA)最終的形式與AA指標如出一轍，而不同在于權重的形式變成了節點(diǎn)的度分之一。大量的實(shí)驗結果以及后期學(xué)者在網(wǎng)絡(luò )社團挖掘等領(lǐng)域的應用顯示，資源分配指標與AA指標表現相近，在精確性上略微勝過(guò)AA指標。在共同鄰居指標的基礎上，一些改進(jìn)算法可以進(jìn)一步提高預測精度。例如，局部樸素貝葉斯模型可以區分共同鄰居對于兩個(gè)節點(diǎn)之間產(chǎn)生連邊的作用是正的（促進(jìn)連接）還是負的（抑制連接）。
本質(zhì)上，共同鄰居指標可以看成是考慮兩個(gè)節點(diǎn)間的二階路徑數目的方法。如果在二階路徑基礎上再考慮節點(diǎn)間的三階路徑數，就可以得到局部路徑指標(Local Path, LP)。顯然，局部路徑指標可以繼續擴展到更高階的情形。當然，隨著(zhù)路徑階數的增加，計算復雜度也會(huì )越來(lái)越高，當階數趨于無(wú)窮的時(shí)候，這一指標就相當于考慮全部路徑的卡茨(Katz)指標。上述的相似性指標大都是基于結構等價(jià)(structure equivalence)原則的，萊希特(Leicht)、霍姆(Holme)和紐曼(Newman)基于一般等價(jià)性(regular equivalence)提出了LHN-II指標，假設兩個(gè)節點(diǎn)的鄰居節點(diǎn)之間相似（不要求是同一個(gè)節點(diǎn)），則這兩個(gè)節點(diǎn)也相似。
基于全局信息的指標除了卡茨指標和LHN-II外，還包括一組基于網(wǎng)絡(luò )隨機游走過(guò)程的指標，如平均通勤時(shí)間(Average Commute Time, ACT)、Cos+指標（或稱(chēng)“余弦相似性”）、有重啟的隨機游走(Random Walk with Restart, RWR)、SimRank指標等。半局部指標包括局部隨機游走指標(Local Random Walk, LRW)和有疊加效應的局部隨機游走指標(Superposed Random Walk, SRW)，其中SRW比LRW更強調網(wǎng)絡(luò )連接的局域性特征。其他全局指標還包括基于網(wǎng)絡(luò )拉普拉斯矩陣的矩陣森林指數以及考慮節點(diǎn)間相似性的可傳遞性的自洽轉移相似性指標等。
基于似然分析的鏈路預測
基于似然分析的鏈路預測的基本思路是：根據網(wǎng)絡(luò )結構的產(chǎn)生和組織方式以及目前已經(jīng)觀(guān)察到的鏈路計算網(wǎng)絡(luò )的似然值，并認為真實(shí)的網(wǎng)絡(luò )使得網(wǎng)絡(luò )似然值最大，然后再根據網(wǎng)絡(luò )似然最大化計算每一對未連接的節點(diǎn)產(chǎn)生連邊的可能性。層次結構模型(Hierarchical Structure Model, HSM)假設真實(shí)的網(wǎng)絡(luò )都存在某種層次性，網(wǎng)絡(luò )的連接則可看作是這種內在層次結構的反映。一個(gè)N個(gè)節點(diǎn)的網(wǎng)絡(luò )可以用一個(gè)包含N個(gè)葉子節點(diǎn)的族譜樹(shù)表示，這N個(gè)葉子節點(diǎn)將由N-1個(gè)非葉子節點(diǎn)連接起來(lái)，其中每個(gè)非葉子節點(diǎn)都有一個(gè)概率值，則兩個(gè)葉子節點(diǎn)連接的概率就等于他們最近共同祖先節點(diǎn)的概率值。給定一個(gè)族譜樹(shù)，將網(wǎng)絡(luò )的似然值最大化，就可以得到非葉子節點(diǎn)的概率值，并由此計算出這一個(gè)族譜樹(shù)所對應的網(wǎng)絡(luò )最大的似然值。文獻使用馬爾科夫鏈蒙特卡洛方法對網(wǎng)絡(luò )不同的族譜樹(shù)進(jìn)行抽樣，使得每個(gè)族譜樹(shù)出現的頻次正比于該樹(shù)對應的最大的網(wǎng)絡(luò )似然值。兩個(gè)節點(diǎn)連邊的概率就等于所有抽樣出來(lái)的族譜樹(shù)中兩個(gè)節點(diǎn)連邊概率的平均值。該方法在處理具有明顯層次結構的網(wǎng)絡(luò )（如恐怖襲擊網(wǎng)絡(luò )和草原食物鏈）時(shí)具有較高的精確度，但在處理一般性網(wǎng)絡(luò )時(shí)效果并不一定突出。
基于類(lèi)似的思想，隨機分塊模型(Stochastic Block Model, SBM)假設網(wǎng)絡(luò )中的節點(diǎn)可以被分為若干集合，兩個(gè)節點(diǎn)間連接的概率只與相應的集合有關(guān)。隨機分塊模型的效果要好于層次結構模型。同時(shí)，該方法還可以剔除網(wǎng)絡(luò )的錯誤連邊，如糾正蛋白質(zhì)相互作用網(wǎng)絡(luò )中的錯誤連邊。
似然分析的更一般的框架是：給定一個(gè)網(wǎng)絡(luò )系統，特定網(wǎng)絡(luò )哈密頓量的負指數被統計分配函數歸一化后，就得到這個(gè)網(wǎng)絡(luò )出現的似然，一條未被觀(guān)察到的連邊存在的可能性就等于添加這條連邊后網(wǎng)絡(luò )的似然值。閉路模型(Loop Model)考慮網(wǎng)絡(luò )結構形成中的“局部性原則”，并由此定義了網(wǎng)絡(luò )的哈密頓量。實(shí)驗表明，閉路模型的預測精度大于層次結構模型和隨機分塊模型。雖然基于最大似然估計的方法計算復雜度高，但這類(lèi)方法除了應用于鏈路預測以外，還帶給我們關(guān)于網(wǎng)絡(luò )結構的深刻洞見(jiàn)，比如層次結構模型給出了研究網(wǎng)絡(luò )層次組織形態(tài)的定量化方法。
基于機器學(xué)習的鏈路預測
用機器學(xué)習的思路進(jìn)行鏈路預測，主要分為基于特征分類(lèi)方法、基于概率圖模型方法和基于矩陣分解方法三大類(lèi)。網(wǎng)絡(luò )中的鏈路預測問(wèn)題可以看成機器學(xué)習中的分類(lèi)問(wèn)題，其中每個(gè)數據點(diǎn)對應一對節點(diǎn)之間關(guān)系的標記，假定兩個(gè)節點(diǎn)之間存在連邊，則數據點(diǎn)的值為+1，否則為-1。特征選取是分類(lèi)問(wèn)題中最重要的問(wèn)題之一，目前研究較多的主要包括基于節點(diǎn)與邊的屬性特征和基于節點(diǎn)所處網(wǎng)絡(luò )的拓撲結構特征（如CN、AA、Katz、最短路徑）等。哈桑(Hasan)等人[45]提取合著(zhù)網(wǎng)絡(luò )中科學(xué)家研究領(lǐng)域的關(guān)鍵詞作為特征，用監督學(xué)習中一些常用的分類(lèi)算法（如決策樹(shù)、K近鄰法、多層感知器、支持向量機、徑向基網(wǎng)絡(luò )）對缺失的連邊進(jìn)行較為精準的預測，其中以支持向量機方法表現最佳。文獻分析了2012年美國大選期間推特用戶(hù)發(fā)送的推文，定義了一個(gè)基于情感特征的特征集合來(lái)預測兩個(gè)用戶(hù)成為朋友的可能性。
基于概率圖模型的鏈路預測方法使用圖模型來(lái)表達節點(diǎn)之間的連邊概率，根據模型中概率依賴(lài)關(guān)系，可分為有向無(wú)環(huán)的貝葉斯網(wǎng)絡(luò )和無(wú)向的馬爾科夫網(wǎng)絡(luò )。隨機分塊模型和層次結構模型分別是典型的基于貝葉斯網(wǎng)絡(luò )和基于馬爾科夫網(wǎng)絡(luò )的鏈路預測方法?；诟怕蕡D模型的鏈路預測方法有很多，典型的還有文獻提出的有監督隨機游走鏈路預測算法，將網(wǎng)絡(luò )結構信息與節點(diǎn)和連邊的屬性信息結合起來(lái)，給每條邊分配不同的轉移概率。與其他有監督的機器學(xué)習方法相比，該算法無(wú)須知道網(wǎng)絡(luò )的特征和相關(guān)的領(lǐng)域知識。
在基于矩陣分解的方法方面，文獻提出了一種基于網(wǎng)絡(luò )鄰接矩陣的代數譜變換的方法，來(lái)預測網(wǎng)絡(luò )中鏈路的存在性和鏈路的權值。相比其他幾種機器學(xué)習方法，該方法要學(xué)習的參數少很多，但計算復雜度較高。鏈路預測問(wèn)題可以視為鄰接矩陣填充問(wèn)題，并可以通過(guò)雙線(xiàn)性回歸模型將節點(diǎn)和鏈路的顯特征和隱特征結合起來(lái)用矩陣分解方法解決。邊緣去噪模型將根據給定關(guān)系矩陣求未知邊或丟失邊的問(wèn)題變成一個(gè)矩陣降噪去噪問(wèn)題。文獻從機器學(xué)習視角對網(wǎng)絡(luò )鏈路預測進(jìn)行了詳細的介紹。
在真實(shí)系統中，個(gè)體間的關(guān)系非常復雜，有時(shí)難以用簡(jiǎn)單無(wú)向圖精準刻畫(huà)。比如食物鏈網(wǎng)絡(luò )、微博關(guān)注網(wǎng)絡(luò )、交通運輸網(wǎng)絡(luò )、社交關(guān)系演化網(wǎng)絡(luò )等，需要用有向、含權、含時(shí)、多層等更加復雜的網(wǎng)絡(luò )來(lái)描述。這些復雜類(lèi)型網(wǎng)絡(luò )上的鏈路預測往往與應用緊密結合，也因此吸引了越來(lái)越多研究者的關(guān)注。
在有向網(wǎng)絡(luò )的鏈路預測中，不僅要考慮連接的存在性還要關(guān)注連接的方向。對于方向的預測是極具挑戰性的。除了可以簡(jiǎn)單地將以往無(wú)向網(wǎng)絡(luò )中的方法拓展到有向網(wǎng)絡(luò )，還可以設計出專(zhuān)門(mén)針對有向網(wǎng)絡(luò )的方法?；诰植孔訄D結構的預測是常用的方法，例如可以基于社交網(wǎng)絡(luò )的9種三角形閉合結構進(jìn)行好友推薦。萊昂(Leung)等人對局部結構做了統計，不僅包含三個(gè)節點(diǎn)的子圖，還含有四個(gè)節點(diǎn)的子圖，此外還考慮了異質(zhì)邊（即性質(zhì)不同的連邊，如敵友關(guān)系）的情況。文獻提出了有向網(wǎng)絡(luò )鏈路預測的“勢理論”，認為如果一條連邊的出現能夠產(chǎn)生更多的可定義勢的子圖，那么它出現的概率就越大。在一個(gè)有向子圖中，任選一個(gè)節點(diǎn)給定初始的勢能，順邊的方向，鄰居的勢能降低1；逆邊的方向，鄰居的勢能增加1。如果此結構內每個(gè)節點(diǎn)的勢能都是可定義的，那么就稱(chēng)此結構為“可定義勢的子圖”。實(shí)驗發(fā)現，如果一條有向邊的加入可以產(chǎn)生的含有四個(gè)節點(diǎn)的雙風(fēng)扇結構越多，那么這條邊出現的概率就越大。除了基于局部子圖的預測方法，還有一些基于有向網(wǎng)絡(luò )中局部隨機游走過(guò)程的方法也可以得到較好的預測效果。此外，基于網(wǎng)絡(luò )結構信息和節點(diǎn)標簽信息的機器學(xué)習方法也可以進(jìn)一步提升預測的精度，例如把基于結構的節點(diǎn)相似性作為此節點(diǎn)對的一個(gè)特征，并結合其他結構特征構成此節點(diǎn)對的特征向量，然后進(jìn)行訓練學(xué)習。
含權網(wǎng)絡(luò )鏈路預測的研究主要分為兩個(gè)方面，(1)權重對于預測連邊存在性的作用；(2)對權重本身的預測。顯然，原有的無(wú)權網(wǎng)絡(luò )的相似性指標（如局部指標CN、AA、RA、PA）和基于路徑的指標（如LP、Katz和LHN-II）都可以很自然地擴展為含權的形式。文獻應用含權的CN、AA、PA指標在日本的雅虎問(wèn)答公告板1數據中進(jìn)行實(shí)驗，發(fā)現含權指標的預測效果要好于無(wú)權的預測方法。但是在另外一些研究中，研究人員發(fā)現了不同的結果。例如，在一些科學(xué)家合作網(wǎng)絡(luò )中含權的Katz指標比不含權的Katz指標預測效果要差。鏈路預測的“弱連接”效應表明：在有些含權網(wǎng)絡(luò )中，權重較弱的邊在鏈路存在性預測中起到的作用比權重高的邊還大。含權網(wǎng)絡(luò )的鏈路預測同樣可以用極大似然模型進(jìn)行研究。
含時(shí)網(wǎng)絡(luò )預測最容易讓人想到的是轉化為含權網(wǎng)絡(luò )的鏈路預測問(wèn)題，另一種方法是根據網(wǎng)絡(luò )中的閉合頻繁子圖以及這些子圖之間出現的時(shí)間規律進(jìn)行預測?？鐣r(shí)間片/跨層的多層網(wǎng)絡(luò )鏈路預測問(wèn)題也取得了一些進(jìn)展。這類(lèi)預測方法將有助于解決網(wǎng)絡(luò )的節點(diǎn)匹配問(wèn)題。
可預測性
鏈路的可預測性是鏈路預測的一個(gè)基本問(wèn)題。鏈路預測的精度在一定程度上反映了算法對于網(wǎng)絡(luò )鏈路形成的可解釋力。然而，不同算法在不同網(wǎng)絡(luò )中的表現不盡相同。當我們獲得一個(gè)很差的預測結果的時(shí)候，是選擇了不恰當的算法造成的，還是因為網(wǎng)絡(luò )的鏈路本身就很難預測？好的預測算法會(huì )給出網(wǎng)絡(luò )演化可能機制的暗示。遺憾的是，我們并不知道一個(gè)算法是否“足夠精確”。比如，針對一個(gè)完全隨機的網(wǎng)絡(luò )，“什么都預測不到”可能已經(jīng)是最好的結果了，然而針對一個(gè)非常規則的網(wǎng)絡(luò )，足夠聰明的方法可以達到100%的精確預測。知道了一個(gè)網(wǎng)絡(luò )的鏈路“能夠被預測出來(lái)”的程度，可以幫助我們判斷算法是否已經(jīng)接近甚至達到預測的上界，是否還有提升的空間?！翱杀活A測的程度”本身也可以看作是網(wǎng)絡(luò )的一種重要性質(zhì)。
然而，衡量網(wǎng)絡(luò )鏈路的可預測性并非易事。許小可等人通過(guò)分析網(wǎng)絡(luò )演化過(guò)程中形成連邊的兩個(gè)節點(diǎn)之間的拓撲距離分布，提出了一種基于此分布概率的方法來(lái)刻畫(huà)基于共同鄰居相似性指標的預測上限。這一上界是依賴(lài)于算法的。如何計算不依賴(lài)特定算法的鏈路可預測性上界，目前還沒(méi)有一個(gè)好的方法?！敖Y構一致性”指標可以用來(lái)衡量網(wǎng)絡(luò )可被預測的難易程度。其假設網(wǎng)絡(luò )越是具有某些規律性，就越容易被預測。如果從網(wǎng)絡(luò )中隨機抽取出一小部分連邊，網(wǎng)絡(luò )的特征向量空間受到的影響很小，就說(shuō)明網(wǎng)絡(luò )是具有規律性的。在這種思路的基礎上，應用類(lèi)似于量子力學(xué)中對哈密頓量做一階微擾的方法，假定減少或者加入少量連邊所產(chǎn)生的微擾只對特征值有影響，而對特征向量沒(méi)有影響，這樣就可以觀(guān)察微擾后通過(guò)這種辦法重構的鄰接矩陣和真實(shí)鄰接矩陣之間的差異。結構一致性指標刻畫(huà)的就是這種差異。實(shí)驗發(fā)現，網(wǎng)絡(luò )隨機性越高，結構一致性就越差，也就越難被預測，但是隨機性并不完全等同于可預測性。此外，結構一致性越強的網(wǎng)絡(luò )，其丟失的邊也越容易被準確地預測出來(lái)。
借鑒結構一致性的思想，產(chǎn)生了一種名為結構微擾法(Structural Perturbation Method，SPM)的鏈路預測方法。實(shí)驗表明，這個(gè)方法在預測丟失的鏈路以及甄別虛假連邊兩方面都優(yōu)于當前主流的方法，包括層次結構[6]和隨機分塊模型。
展望
2011年我們曾在《物理學(xué)A》(Physica A)上發(fā)表了一篇關(guān)于鏈路預測的英文綜述，得到來(lái)自計算機科學(xué)、生物學(xué)、藥物學(xué)、物理學(xué)、數學(xué)、社會(huì )科學(xué)等多學(xué)科的引用。這些論文不僅從理論上推動(dòng)了鏈路預測的發(fā)展，還給出了各種各樣的可以應用的實(shí)際場(chǎng)景。過(guò)去提出的一些挑戰性問(wèn)題如今都得到了不同程度的推進(jìn)。例如，各種算法對不同網(wǎng)絡(luò )預測能力的深度比較，利用鏈路預測建立網(wǎng)絡(luò )演化機制的比較平臺，揭示網(wǎng)絡(luò )演化的規律，對網(wǎng)絡(luò )鏈路的可預測性問(wèn)題進(jìn)行探討以及鏈路預測在其他網(wǎng)絡(luò )類(lèi)型中的理論和應用研究等。
盡管近幾年鏈路預測方向取得了一系列成果，但是仍然存在很多有意思、具有挑戰性的問(wèn)題值得進(jìn)一步深入研究，包括：
計算網(wǎng)絡(luò )鏈路可預測性的上界 盡管文獻給出了刻畫(huà)網(wǎng)絡(luò )鏈路可預測性的方法，但是文中提出的結構一致性指標僅能幫助我們比較兩個(gè)網(wǎng)絡(luò )的鏈路可預測性的高低，并不能給出一個(gè)可預測性的上界。如何得到一個(gè)不依賴(lài)于預測算法的鏈路可預測上界仍是一個(gè)懸而未決的問(wèn)題。
復雜類(lèi)型網(wǎng)絡(luò )的鏈路預測 現有的研究并不系統，如何在復雜結構的網(wǎng)絡(luò )（例如含時(shí)網(wǎng)絡(luò )、多層網(wǎng)絡(luò )、相互依賴(lài)網(wǎng)絡(luò )、超網(wǎng)絡(luò )等）中進(jìn)行鏈路預測，還有很大空間可供挖掘。對于含時(shí)網(wǎng)絡(luò )的研究仍屬鳳毛麟角，我們知道如何應用時(shí)間的信息提高存在性的預測精度，但是如何準確預測兩節點(diǎn)再次接觸的時(shí)間仍是一個(gè)挑戰，人類(lèi)動(dòng)力學(xué)的研究在這方面會(huì )起到重要的作用。
大規模網(wǎng)絡(luò )的快速算法設計 信息技術(shù)的發(fā)展使得我們獲取數據越來(lái)越容易，然而大數據所具有的海量復雜的特征也對信息處理技術(shù)提出了更高的要求。如何在超大規模網(wǎng)絡(luò )上有效利用多維的豐富信息進(jìn)行快速、準確的鏈路預測，設計局域化或并行化的算法具有重要意義。
鏈路預測的應用問(wèn)題 鏈路預測已廣泛應用于社交網(wǎng)絡(luò )、生物網(wǎng)絡(luò )、推薦系統、股市預測等多個(gè)領(lǐng)域。相信隨著(zhù)研究的不斷推進(jìn)，會(huì )發(fā)現更多可以應用的場(chǎng)景，從而體現鏈路預測在解決實(shí)際問(wèn)題中的價(jià)值。值得注意的是，用戶(hù)的個(gè)人隱私保護是實(shí)際應用中一個(gè)不可回避的問(wèn)題，如何在分散式在線(xiàn)社交網(wǎng)絡(luò )中進(jìn)行鏈路預測，使得既不侵犯用戶(hù)的隱私又能得到精度較高的預測效果，這也是一個(gè)值得探討的問(wèn)題。
評價(jià)指標體系的建設 目前大多數的算法評價(jià)都是基于離線(xiàn)的數據測試，但是真實(shí)系統中的用戶(hù)行為往往受到多種因素的影響，因此獲得真實(shí)系統中用戶(hù)的反饋對于評價(jià)算法的性能更加重要。在復雜類(lèi)型網(wǎng)絡(luò )的研究進(jìn)展中，如何針對這些網(wǎng)絡(luò )的預測建立更加合理的評價(jià)指標也是亟待解決的問(wèn)題。例如在含權網(wǎng)絡(luò )的鏈路預測中，就權重預測的準確性而言，用一些刻畫(huà)相關(guān)性的指標是否合適，還是值得商榷的。
鏈路預測研究方興未艾。近年來(lái)，涌現出一批具有理論深度的研究成果。特別是一批年輕學(xué)者的加入，促使鏈路預測成為網(wǎng)絡(luò )信息挖掘和預測領(lǐng)域最具活力的研究方向之一。作為一門(mén)典型的交叉學(xué)科，鏈路預測從理念、方法到應用，融合了計算機科學(xué)、統計物理學(xué)、社會(huì )科學(xué)、生物學(xué)、數學(xué)等多個(gè)學(xué)科的精華。未來(lái)希望能在多學(xué)科的交叉融合中碰撞出更多有意義、有價(jià)值的思想火花，共同推動(dòng)鏈路預測在理論和應用方面取得進(jìn)展。
致謝：感謝國家自然科學(xué)基金11205042、61433014和11222543，浙江省自然科學(xué)基金LR16A050001的支持。
作者：
聯(lián)系客服
