呂琳媛

(弗里堡大學(xué)物理系 瑞士 弗里堡 CH-1700)

網(wǎng)絡(luò)中的鏈路預(yù)測(link prediction)，既包含了對未知鏈接(existent yet unknown links)的預(yù)測，也包含了對未來鏈接(future links)的預(yù)測。鏈路預(yù)測作為數(shù)據(jù)挖掘領(lǐng)域的研究方向之一在計算機領(lǐng)域已有較深入的研究，研究的思路和方法主要基于馬爾科夫鏈和機器學(xué)習(xí)。文獻[2]應(yīng)用馬爾科夫鏈進行網(wǎng)絡(luò)的鏈路預(yù)測和路徑分析。之后，文獻[3]將基于馬爾科夫鏈的預(yù)測方法擴展到自適應(yīng)性網(wǎng)站(adaptive web sites)的預(yù)測中。此外，文獻[4]提出一個回歸模型在文獻引用網(wǎng)絡(luò)中預(yù)測科學(xué)文獻的引用關(guān)系，方法不僅用到了引文網(wǎng)絡(luò)的信息，還有作者信息、期刊信息以及文章內(nèi)容等外部信息。應(yīng)用節(jié)點屬性的預(yù)測方法還有很多，如文獻[5]利用網(wǎng)絡(luò)的拓撲結(jié)構(gòu)信息以及節(jié)點的屬性，建立了一個局部的條件概率模型進行預(yù)測。文獻[6]基于節(jié)點的屬性定義了節(jié)點間的相似性，可以直接用于進行鏈路預(yù)測。雖然應(yīng)用節(jié)點屬性等外部信息的確可以得到很好的預(yù)測效果，但是很多情況下，信息的獲得是非常困難的，甚至是不可能的，如很多在線系統(tǒng)的用戶信息都是保密的。另外，即使獲得了節(jié)點的屬性信息，也很難保證信息的可靠性，即屬性是否反映了節(jié)點的真實情況，如在線社交網(wǎng)絡(luò)中，很多用戶的注冊信息都是虛假的。更進一步，在能夠得到節(jié)點屬性的精確信息的情況下，如何鑒別出哪些信息對網(wǎng)絡(luò)的鏈路預(yù)測是有用的，哪些信息是沒用的，仍然是個問題。

最近幾年，基于網(wǎng)絡(luò)結(jié)構(gòu)的鏈路預(yù)測方法受到越來越多的關(guān)注。相比節(jié)點的屬性信息而言，網(wǎng)絡(luò)的結(jié)構(gòu)更容易獲得，也更加可靠。同時，該類方法對于結(jié)構(gòu)相似的網(wǎng)絡(luò)具有普適性，從而避免了對不同網(wǎng)絡(luò)需要機器學(xué)習(xí)獲得一些特定的參數(shù)組合。文獻[7]提出了基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的相似性定義方法，并分析了若干指標對社會合作網(wǎng)絡(luò)中鏈路預(yù)測的效果。另外一類鏈路預(yù)測方法是基于網(wǎng)絡(luò)結(jié)構(gòu)的最大似然估計。2008年，文獻[8]提出了一種利用網(wǎng)絡(luò)的層次結(jié)構(gòu)進行鏈路預(yù)測的方法，并在具有明顯層次結(jié)構(gòu)的網(wǎng)絡(luò)中表現(xiàn)很好。此外，利用隨機分塊模型[9]預(yù)測網(wǎng)絡(luò)缺失邊和錯誤邊的鏈路預(yù)測方法。值得一提的是，該篇文章第一次提到網(wǎng)絡(luò)錯誤連邊(spurious links)的概念，即在網(wǎng)絡(luò)已知的鏈接中很可能存在一些錯誤的鏈接，比如人們對蛋白質(zhì)相互作用關(guān)系的錯誤認知。

鏈路預(yù)測問題受到來自不同領(lǐng)域、擁有不同背景的科學(xué)家的廣泛關(guān)注，首先是因其重大的實際應(yīng)用價值。如在生物領(lǐng)域研究中，蛋白質(zhì)相互作用網(wǎng)絡(luò)和新陳代謝網(wǎng)絡(luò)，節(jié)點之間是否存在鏈接，或者說是否存在相互作用關(guān)系，是需要通過大量實驗結(jié)果進行推斷的。已知的實驗結(jié)果僅僅揭示了巨大網(wǎng)絡(luò)的冰山一角。僅以蛋白質(zhì)相互作用網(wǎng)絡(luò)為例，酵母菌蛋白質(zhì)之間80%的相互作用不為人們所知[11]，而對于人類自身，人們知道的僅有可憐的0.3%[12-13]。由于揭示該類網(wǎng)絡(luò)中隱而未現(xiàn)的鏈接需要耗費高額的實驗成本，如果能夠事先在已知網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上設(shè)計出足夠精確的鏈路預(yù)測算法，再利用預(yù)測的結(jié)果指導(dǎo)試驗，就有可能提高實驗的成功率，從而降低實驗成本，并加快揭開該類網(wǎng)絡(luò)真實面目的步伐。實際上，社會網(wǎng)絡(luò)分析中也會遇到數(shù)據(jù)不全的問題，鏈路預(yù)測同樣可以作為準確分析社會網(wǎng)絡(luò)結(jié)構(gòu)的有力的輔助工具[14-15]。除了幫助分析數(shù)據(jù)缺失的網(wǎng)絡(luò)，鏈路預(yù)測算法還可以用于分析演化網(wǎng)絡(luò)。如近幾年在線社交網(wǎng)絡(luò)發(fā)展非常迅速[16]，鏈路預(yù)測可以基于當(dāng)前的網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測哪些現(xiàn)在尚未結(jié)交的用戶“應(yīng)該是朋友”，并將此結(jié)果作為“朋友推薦”發(fā)送給用戶。如果預(yù)測足夠準確，顯然有助于提高相關(guān)網(wǎng)站在用戶心目中的地位，從而提高用戶對該網(wǎng)站的忠誠度。另外，鏈路預(yù)測的思想和方法，還可以用于在已知部分節(jié)點類型的網(wǎng)絡(luò)(partially labeled networks)中預(yù)測未標簽節(jié)點的類型，如用于判斷一篇學(xué)術(shù)論文的類型[17]或者判斷一個手機用戶是否產(chǎn)生了切換運營商(如從移動到聯(lián)通)的念頭[18]。另外文獻[10]所提出的對網(wǎng)絡(luò)中的錯誤鏈接的預(yù)測，對于網(wǎng)絡(luò)重組和結(jié)構(gòu)功能優(yōu)化也有重要的應(yīng)用價值，如在很多構(gòu)建生物網(wǎng)絡(luò)的實驗中存在曖昧不清甚至自相矛盾的數(shù)據(jù)[19]，就有可能應(yīng)用鏈路預(yù)測的方法對其進行糾正。

鏈路預(yù)測研究不僅具有廣泛的實際應(yīng)用價值，也具有重要的理論研究意義，特別是對一些相關(guān)領(lǐng)域理論方面的推動和貢獻。近年來，隨著網(wǎng)絡(luò)科學(xué)的快速發(fā)展，其理論上的成果為鏈路預(yù)測搭建了一個研究的平臺，使得鏈路預(yù)測的研究與網(wǎng)絡(luò)的結(jié)構(gòu)與演化緊密聯(lián)系起來。因此，對于預(yù)測的結(jié)果更能夠從理論的角度進行解釋。與此同時，鏈路預(yù)測的研究也可以從理論上幫助人們認識復(fù)雜網(wǎng)絡(luò)演化的機制。針對同一個或者同一類網(wǎng)絡(luò)，很多模型都提供了可能的網(wǎng)絡(luò)演化機制[20-21]。由于刻畫網(wǎng)絡(luò)結(jié)構(gòu)特征的統(tǒng)計量非常多，很難比較不同的機制孰優(yōu)孰劣。鏈路預(yù)測機制有望為演化網(wǎng)絡(luò)提供一個簡單統(tǒng)一且較為公平的比較平臺，從而大大推動復(fù)雜網(wǎng)絡(luò)演化模型的理論研究。另外，如何刻畫網(wǎng)絡(luò)中節(jié)點的相似性也是一個重大的理論問題[22]，該問題和網(wǎng)絡(luò)聚類等應(yīng)用息息相關(guān)[23]。類似，相似性的度量指標數(shù)不勝數(shù)，只有能夠快速準確地評估某種相似性定義是否能夠很好地刻畫一個給定網(wǎng)絡(luò)節(jié)點間的關(guān)系，才能進一步研究網(wǎng)絡(luò)特征對相似性指標選擇的影響，因此，鏈路預(yù)測可以起到核心技術(shù)的作用。鏈路預(yù)測問題本身也帶來了有趣且有重要價值的理論問題，就是通過構(gòu)造網(wǎng)絡(luò)系綜(network ensemble)，并借此利用最大似然估計方法進行鏈路預(yù)測的可能性和可行性研究，對鏈路預(yù)測本身以及復(fù)雜網(wǎng)絡(luò)研究的理論基礎(chǔ)的建立和完善起到推動和借鑒作用。

1 問題描述與評價方法

AUC可以理解為在測試集中的邊的分數(shù)值有比隨機選擇的一個不存在的邊的分數(shù)值高的概率，也就是說，每次隨機從測試集中選取一條邊與隨機選擇的不存在的邊進行比較，如果測試集中的邊的分數(shù)值大于不存在的邊的分數(shù)值，就加1分；如果兩個分數(shù)值相等，就加0.5分。獨立地比較n次，如果有n′次測試集中的邊的分數(shù)值大于不存在的邊的分數(shù)，有n′次兩分數(shù)值相等，則AUC定義為：顯然，如果所有分數(shù)都是隨機產(chǎn)生的，AUC=0.5。因此AUC大于0.5的程度衡量了算法在多大程度上比隨機選擇的方法精確。

Precision定義為在前L個預(yù)測邊中被預(yù)測準確的比例。如果有m個預(yù)測準確，即排在前L的邊中有m個在測試集中，則Precision定義為：顯然，Precision越大預(yù)測越準確。如果兩個算法AUC相同，而算法1的Precision大于算法2，說明算法1更好，因為其傾向于把真正連邊的節(jié)點對排在前面。

2 基于相似性的鏈路預(yù)測

應(yīng)用節(jié)點間的相似性進行鏈路預(yù)測的一個重要前提假設(shè)就是兩個節(jié)點之間相似性(或者相近性)越大，它們之間存在鏈接的可能性就越大。應(yīng)注意，相似性并非一般意義上的相似性，而是指一種接近程度(proximity)?？坍嫻?jié)點的相似性有多種方法，最簡單直接的方法就是利用節(jié)點的屬性，如果兩個人具有相同的年齡、性別、職業(yè)、興趣等等，就說他們倆很相似。利用節(jié)點屬性的相似性進行鏈路預(yù)測的前提，就是網(wǎng)絡(luò)中的邊本身代表著相似。另外一類相似性的定義完全基于網(wǎng)絡(luò)的結(jié)構(gòu)信息，稱為結(jié)構(gòu)相似性。基于結(jié)構(gòu)相似性的鏈路預(yù)測精度的高低取決于該種結(jié)構(gòu)相似性的定義是否能夠很好地抓住目標網(wǎng)絡(luò)的結(jié)構(gòu)特征。如基于共同鄰居的相似性指標，即兩個節(jié)點如果有更多的共同鄰居就更可能連邊，在集聚系數(shù)較高的網(wǎng)絡(luò)中表現(xiàn)非常好，有時甚至超過一些更復(fù)雜的算法。然而對于集聚系數(shù)較低的網(wǎng)絡(luò)如路由器網(wǎng)絡(luò)或電力網(wǎng)絡(luò)等，預(yù)測精度就差很多。

2.1 基于局部信息的相似性指標

基于局部信息的最簡單的相似性指標是共同鄰居(common neighbors)，也就是說兩個節(jié)點如果有更多的共同鄰居，則它們更傾向于連邊。在共同鄰居的基礎(chǔ)上考慮兩端節(jié)點度的影響，從不同的角度以不同的方式又可產(chǎn)生6種相似性指標，分別是Salton指標[27](也叫做余弦相似性)、Jaccard指標[28]、Sorenson指標[29]、大度節(jié)點有利指標(hub promoted index)[30]、大度節(jié)點不利指標(hub depressed index)和LHN-Ⅰ指標[22](由Leicht，Holme和Newman提出而得名)，稱這一類指標為基于共同鄰居的相似性。

另一個只考慮節(jié)點度的相似性為優(yōu)先連接指標(preferential attachment)。應(yīng)用優(yōu)先連接的方法可以產(chǎn)生無標度的網(wǎng)絡(luò)結(jié)構(gòu)，在該網(wǎng)絡(luò)中，一條即將加入的新邊連接到節(jié)點x的概率正比于節(jié)點x的度k(x)[31]，因此新邊連接節(jié)點x和y的概率正比于兩節(jié)點度的乘積。該算法的復(fù)雜度較其他算法低，因為需要的信息量最少。

如果考慮兩節(jié)點共同鄰居的度信息，有Adamic-Adar(AA)指標[32]，其思想是度小的共同鄰居節(jié)點的貢獻大于度大的共同鄰居節(jié)點。因此根據(jù)共同鄰居節(jié)點的度為每個節(jié)點賦予一個權(quán)重值，該權(quán)重等于該節(jié)點的度的對數(shù)分之一，即1/lgk。

文獻[33]從網(wǎng)絡(luò)資源分配(resource allocation)的角度提出一種新的指標，簡稱RA?？紤]網(wǎng)絡(luò)中沒有直接相連的兩個節(jié)點x和y，從x可以傳遞一些資源到y(tǒng)，而在此過程中，它們的共同鄰居就成為傳遞的媒介。假設(shè)每個媒介都有一個單位的資源并且將平均分配傳給它的鄰居，則y可以接收到的資源數(shù)就定義為節(jié)點x和y的相似度。RA和AA指標最大的區(qū)別在于賦予共同鄰居節(jié)點權(quán)重的方式不同，前者以1/k的形式遞減，后者以1/lgk的形式遞減。可見，當(dāng)網(wǎng)絡(luò)的平均度較小時RA和AA差別不大，但是當(dāng)平均度較大時，就有很大的區(qū)別了。

表1 10種基于節(jié)點局部信息的相似性指標

文獻[33]將上述10種基于節(jié)點局部信息的相似性指標在6個實際網(wǎng)絡(luò)中進行實驗，并比較其預(yù)測精確度[33]。6個網(wǎng)絡(luò)分別為：蛋白質(zhì)相互作用網(wǎng)絡(luò)(PPI)、科學(xué)家合作網(wǎng)絡(luò)(NS)、美國電力網(wǎng)絡(luò)(Grid)、政治博客網(wǎng)絡(luò)(PB)、路由器網(wǎng)絡(luò)(INT)以及美國航空網(wǎng)絡(luò)(USAir)，它們的統(tǒng)計性質(zhì)如表2所示。其中N、M分別表示網(wǎng)絡(luò)的節(jié)點數(shù)和邊數(shù)，Nc為網(wǎng)絡(luò)的最大聯(lián)通集團，如2 375/92表示PPI網(wǎng)絡(luò)中有92個聯(lián)通集團，最大聯(lián)通集包含2 375個節(jié)點，e為網(wǎng)絡(luò)的效率，C為網(wǎng)絡(luò)集聚系數(shù)，r為同配系數(shù)，H為網(wǎng)絡(luò)度異質(zhì)性。預(yù)測結(jié)果如表3所示。所有結(jié)果均以AUC為預(yù)測精度評價指標。可見在10種算法中，RA表現(xiàn)最好，其次是CN，再次是AA?？偟膩碚f，PA表現(xiàn)最差，特別是在電力網(wǎng)絡(luò)和路由器網(wǎng)絡(luò)中，預(yù)測精度還不到0.5，意味著PA算法在這兩個網(wǎng)絡(luò)中預(yù)測精度還不如完全隨機預(yù)測的好。

表2 6個實驗網(wǎng)絡(luò)的拓撲性質(zhì)

表3 10種基于節(jié)點局部信息的相似性在6個網(wǎng)絡(luò)鏈路預(yù)測中的精度比較

2.2 基于路徑的相似性指標

基于路徑的相似性指標有3個，分別是局部路徑指標(LP)[34]、Katz指標[35]和LHN-II[22]指標(與LHN-I在同一篇文章中提出)。

表4 基于路徑的相似性指標在使用AUC衡量時的預(yù)測精度比較

表5 基于路徑的相似性指標在使用Precision衡量時的預(yù)測精度比較

2.3 基于隨機游走的相似性指標

有一類相似性算法是基于隨機游走定義的，包括平均通勤時間(average commute time)[37]、Cos+指標[38]、有重啟的隨機游走(random walk with restart)[39]、SimRank指標[40]，以及新提出的兩種基于局部隨機游走的指標[36]。

(1) 平均通勤時間(average commute time)簡稱ACT。設(shè)m(x,y)為一個隨機粒子從節(jié)點x到節(jié)點y需要走的平均步數(shù)，則節(jié)點x和y的平均通勤時間定義為：

其數(shù)值解可通過求該網(wǎng)絡(luò)拉普拉斯矩陣的偽逆+L獲得[37]，即：

關(guān)于RWR的一種快速算法參見文獻[41]，該指標已被應(yīng)用于推薦系統(tǒng)的算法研究中[42]。

(4) SimRank指標簡稱SimR。它的基本假設(shè)是，如果兩節(jié)點所連接的節(jié)點相似，則該兩節(jié)點相似[40]。它的自洽定義式為：

(6) 疊加的局部隨機游走指標(superposed random walk)簡稱SRW[36]。在LRW的基礎(chǔ)上將t步及其以前的結(jié)果加總便得到SRW的值，即：

這個指標的目的就是給鄰近目標節(jié)點的點更多的機會與目標節(jié)點相連。

文獻[36]比較了上述兩種基于局部隨機游走和基于全局隨機游走的ACT和RWR指標在5個不同領(lǐng)域的網(wǎng)絡(luò)中的鏈路預(yù)測效果。該5個網(wǎng)絡(luò)分別為美國航空網(wǎng)絡(luò)(USAir)、科學(xué)家合作網(wǎng)(NS)、電力網(wǎng)絡(luò)(Grid)、蛋白質(zhì)相互作用網(wǎng)絡(luò)(PPI)和線蟲神經(jīng)網(wǎng)絡(luò)(C.elegans)，其拓撲結(jié)構(gòu)的統(tǒng)計特性展現(xiàn)于表6。注意，與節(jié)3.1中數(shù)據(jù)不同的是，這里只考慮了最大聯(lián)通集?！磌〉和〈d〉分別表示平均度和平均最短距離。

表6 5個網(wǎng)絡(luò)最大連通集的統(tǒng)計特征

表7 4種基于隨機游走的算法在使用AUC衡量時的預(yù)測精度比較

表8 4種基于隨機游走的算法在使用Precision衡量時的預(yù)測精度比較

2.4 權(quán)重在鏈路預(yù)測中的作用

含權(quán)網(wǎng)絡(luò)的鏈路預(yù)測是一個較重要的方向，但到目前為止還沒有系統(tǒng)的研究工作，對于如何更好地運用權(quán)重的信息以提高鏈路預(yù)測的精確度還沒有明確的答案。文獻[43]將3種局部算法CN、AA和RA拓展為含權(quán)形式，定義如下：

圖1 美國航空網(wǎng)絡(luò)預(yù)測精度與參數(shù)α的關(guān)系

此外，在科學(xué)家合作網(wǎng)中也發(fā)現(xiàn)了弱連接效應(yīng)。但是在C.elegans線蟲神經(jīng)網(wǎng)絡(luò)中結(jié)果恰恰相反，其最優(yōu)參數(shù)值均大于1，意味著只有更加強調(diào)強連接，弱化弱連接，可稱為鏈路預(yù)測的強連接效應(yīng)，才能得到更好的預(yù)測結(jié)果。文獻[43]隨后運用motif分析方法定性解釋了造成差異的原因，但是還不能進行定量的描述。含權(quán)網(wǎng)絡(luò)的預(yù)測方法研究還具有很大的拓展空間，同樣的網(wǎng)絡(luò)結(jié)構(gòu)，不同的含權(quán)方式在實際預(yù)測中起到的作用也可能不一樣。要搞清這些問題，還需要更加深入細致的研究工作。

3 基于最大似然估計的鏈路預(yù)測

鏈路預(yù)測的另一類方法是基于最大似然估計的。文獻[8]認為，很多網(wǎng)絡(luò)的連接可以看作某種內(nèi)在的層次結(jié)構(gòu)的反映，基于此，文獻[8]提出了一種最大似然估計算法進行鏈路預(yù)測，該方法在處理具有明顯層次組織的網(wǎng)絡(luò)(如恐怖襲擊網(wǎng)絡(luò)和草原食物鏈)時具有較好的精確度。但是，由于每次預(yù)測要生成很多個樣本網(wǎng)絡(luò)，因此其計算復(fù)雜度非常高，只能處理規(guī)模不太大的網(wǎng)絡(luò)。文獻[10]假設(shè)觀察到的網(wǎng)絡(luò)是一個隨機分塊模型(stochastic block model)[9]的一次實現(xiàn)，在該模型中節(jié)點被分為若干集合，兩個節(jié)點間連接的概率只與相應(yīng)的集合有關(guān)。文獻[10]所提出的基于隨機分塊模型的鏈路預(yù)測方法，可以得到更好的結(jié)果。同時，該方法不僅可以預(yù)測缺失邊，還可以預(yù)測網(wǎng)絡(luò)的錯誤鏈接，如糾正蛋白質(zhì)相互作用網(wǎng)絡(luò)中的錯誤鏈接?；谧畲笏迫还烙嫹椒ǖ囊粋€最大問題是計算復(fù)雜度太高，因此并不適合在規(guī)模較大的網(wǎng)絡(luò)中應(yīng)用。

3.1 層次結(jié)構(gòu)模型[8]

圖2 用樹形圖表示網(wǎng)絡(luò)的層次結(jié)構(gòu)示例

給定一個網(wǎng)絡(luò)G及和它相對應(yīng)的一個樹形圖D，則這個樹形圖對目標網(wǎng)絡(luò)G的似然估計值為：

(2) 隨機選擇一個內(nèi)部節(jié)點r并考慮以其兄弟節(jié)點為根節(jié)點的子樹集合B和以其兒女節(jié)點為根節(jié)點的子樹集合C。

(3) 通過交換子樹集合B和C中的子樹獲得新的樹狀圖D′，注意D和D′不同。

(5) 當(dāng)該馬爾科夫鏈收斂于平穩(wěn)時，開始生成可用的樹形圖，如5 000個。

3.2 隨機分塊模型[10]

式中Ω為所有可能的分塊模型集合(實際運算中并不需要真正考慮所有的)。為方便計算，可將p(M)設(shè)定為一個常數(shù)?？尚哦仍礁弑硎驹娇赡苓B邊。隨機分塊模型不僅可以預(yù)測缺失邊，還可以根據(jù)可信度判斷哪些邊是錯誤連邊，如對蛋白質(zhì)相互作用關(guān)系的錯誤認識。隨機分塊模型平均而言表現(xiàn)比層次結(jié)構(gòu)模型好，尤其是在預(yù)測錯誤連邊時。但是它與層次模型同樣都存在計算時間復(fù)雜度高的問題。

4 概率模型

運用概率模型進行鏈路預(yù)測的基本思路就是建立一個含有一組可調(diào)參數(shù)的模型，然后使用優(yōu)化策略尋找最優(yōu)的參數(shù)值，使得所得到的模型能夠更好地再現(xiàn)真實網(wǎng)絡(luò)的結(jié)構(gòu)和關(guān)系特征，網(wǎng)絡(luò)中兩個未連邊的節(jié)點對連邊的概率就等于在該組最優(yōu)參數(shù)下它們之間產(chǎn)生連邊的條件概率。如果將邊的存在性(存在或不存在)看成是邊的一種屬性，那么鏈路預(yù)測問題就轉(zhuǎn)變?yōu)轭A(yù)測邊的屬性問題[47]。兩個常用的框架為概率關(guān)系模型框架(probabilistic relational models)[48]和有向無環(huán)概率實體關(guān)系框架(directed acyclic probabilistic entity relationship)[49]。它們的區(qū)別在于對數(shù)據(jù)庫的表達方式不同，前者基于關(guān)系模型(relational models)，后者基于實體關(guān)系模型(entityrelationship model)。

概率模型的優(yōu)勢在于較高的預(yù)測精確度，它不僅使用了網(wǎng)絡(luò)的結(jié)構(gòu)信息還涉及節(jié)點的屬性信息。但是計算的復(fù)雜度以及非普適性的參數(shù)使其應(yīng)用范圍受到限制。

4.1 概率關(guān)系模型(PRMs)

概率關(guān)系模型是將概率模型和關(guān)系模型相結(jié)合的一種預(yù)測模型。概率關(guān)系模型包括3個網(wǎng)絡(luò)：(1) 數(shù)據(jù)網(wǎng)絡(luò)(data graph)即所謂的訓(xùn)練集，包含原始的數(shù)據(jù)信息；(2) 模型網(wǎng)絡(luò)(model graph)，分析數(shù)據(jù)網(wǎng)絡(luò)得到的用于刻畫網(wǎng)絡(luò)主體屬性之間的關(guān)系，該種關(guān)系既包括一類主體內(nèi)部屬性之間的關(guān)系，也包括不同主體屬性之間的關(guān)系；(3) 推理網(wǎng)絡(luò)(inference graph)，是將模型網(wǎng)絡(luò)與目標網(wǎng)絡(luò)(測試集)相結(jié)合的網(wǎng)絡(luò)，用于對目標網(wǎng)絡(luò)的預(yù)測。根據(jù)模型網(wǎng)絡(luò)的不同構(gòu)造方法又可將概率關(guān)系模型分為貝葉斯網(wǎng)絡(luò)關(guān)系模型(relational bayesian networks)[50]、馬爾科夫網(wǎng)絡(luò)關(guān)系模型(relational markov networks)[51]和關(guān)系依賴網(wǎng)絡(luò)模型(relational dependency networks)[52-53]。

4.2 有向無環(huán)概率實體關(guān)系模型(DAPER)[49]

DAPER是以實體關(guān)系模型為基礎(chǔ)所建立的模型，它將實體之間的關(guān)系也看成和實體一樣重要。DAPER模型包括6類組成成分。

(1) 實體類(entity classes)，即網(wǎng)絡(luò)的實體，如大學(xué)數(shù)據(jù)庫中的學(xué)生類和課程類。

(2) 關(guān)系類(relationship classes)，即描述實體間的關(guān)系，如學(xué)生選擇課程中的選擇關(guān)系。

(3) 屬性類(attribute classes)，即實體或者關(guān)系的屬性，如學(xué)生的智商，課程的難易程度等。

(4) 弧線類(arc classes)，用于描述各個屬性之間的關(guān)系，如學(xué)生的課程分數(shù)受到學(xué)生智商和課程難度的影響。屬性關(guān)系構(gòu)成的網(wǎng)絡(luò)為有向無環(huán)網(wǎng)絡(luò)(與RBN類似)。

(5) 局部概率分布類(local distribution classes)，對某一屬性類的條件概率分布，與PRMs中的條件概率類似。

(6) 限制條件類(constraint classes)，衡量屬性關(guān)系之間的限制條件。

文獻[49]比較了該模型與PRMs模型的區(qū)別和聯(lián)系。圖3展現(xiàn)了在學(xué)生選擇課程的例子中分別用DAPER和PRMs建立的模型，分別如圖3a和3b所示。

圖3 以大學(xué)數(shù)據(jù)中學(xué)生和課程為例的DAPER模型和PRMs模型

5 總結(jié)與展望

綜上所述，無論是基于結(jié)構(gòu)的相似性預(yù)測方法還是基于最大似然估計的方法，或是概率模型本質(zhì)上都是通過對已知數(shù)據(jù)的盡可能真切的刻畫的方法實現(xiàn)預(yù)測，但是它們的角度各自不同。基于結(jié)構(gòu)相似性的方法只涉及網(wǎng)絡(luò)的結(jié)構(gòu)信息，主要從某一個角度對于網(wǎng)絡(luò)的某一方面的結(jié)構(gòu)特點進行刻畫，如果目標網(wǎng)絡(luò)的結(jié)構(gòu)在該方面特征顯著，即可得到較好的預(yù)測效果。雖然基于網(wǎng)絡(luò)結(jié)構(gòu)相似性的方法比較簡單，計算復(fù)雜度相對較低，特別是基于局部結(jié)構(gòu)的算法，但是各個方法在不同網(wǎng)絡(luò)中的預(yù)測能力大不相同。目前還沒有對算法性能和網(wǎng)絡(luò)結(jié)構(gòu)特征之間關(guān)系較深入的研究。對于比較復(fù)雜的網(wǎng)絡(luò)，如含權(quán)網(wǎng)絡(luò)、有向網(wǎng)絡(luò)、多部分網(wǎng)絡(luò)以及含有異質(zhì)邊的網(wǎng)絡(luò)，如何通過結(jié)構(gòu)信息進行預(yù)測的討論甚少且不系統(tǒng)[43,55-56]?；谧畲笏迫还烙嫷姆椒m然也是基于網(wǎng)絡(luò)結(jié)構(gòu)的，但是其針對的是整個網(wǎng)絡(luò)結(jié)構(gòu)而不僅僅局限于某一方面。該類方法由于計算復(fù)雜度較高，不可能應(yīng)用于規(guī)模較大的網(wǎng)絡(luò)。實驗顯示該類方法的預(yù)測精度也不是很高。概率模型是數(shù)據(jù)挖掘的傳統(tǒng)模型，它可以同時考慮網(wǎng)絡(luò)的結(jié)構(gòu)信息和節(jié)點的屬性信息，以求得到更好的預(yù)測效果。但是計算的復(fù)雜性以及節(jié)點外在屬性信息在獲取上的難度，造成該類方法應(yīng)用的局限性。

最近十年，復(fù)雜網(wǎng)絡(luò)研究在很多科學(xué)分支，包括物理、生物、計算機等掀起高潮[57]，其中相當(dāng)一部分研究立足于揭示網(wǎng)絡(luò)演化的內(nèi)在驅(qū)動因素。僅以無標度網(wǎng)絡(luò)(scale-free networks)為例[58]，已經(jīng)報道的可以產(chǎn)生冪律度分布的機制就包括了富者愈富(rich-get-richer)機制[31]、好者變富(good-get-richer)機制[59]、優(yōu)化設(shè)計(optimal design)驅(qū)動[60]、哈密頓動力學(xué)(hamiltonian dynamics)驅(qū)動[61]、聚生(merging and regeneration)機制[62]、穩(wěn)定性限制(stability constraints)驅(qū)動[63]，等等?？墒?，由于刻畫網(wǎng)絡(luò)結(jié)構(gòu)特征的統(tǒng)計指標非常多，很難比較和判定什么樣的機制能夠更好再現(xiàn)真實網(wǎng)絡(luò)的生長特性。利用鏈路預(yù)測有望建立簡單的比較平臺，能夠在知道目標網(wǎng)絡(luò)演化情況的基礎(chǔ)上，量化比較各種不同機制對于真實生長行為的預(yù)測能力，從而可以大大推動復(fù)雜網(wǎng)絡(luò)演化機制的相關(guān)研究。

與此同時，受益于復(fù)雜網(wǎng)絡(luò)研究的快速發(fā)展，基于網(wǎng)絡(luò)結(jié)構(gòu)的鏈路預(yù)測方法有望在網(wǎng)絡(luò)理論的幫助下得到發(fā)展和完善。一方面是如何以網(wǎng)絡(luò)系綜理論為基礎(chǔ)，建立網(wǎng)絡(luò)鏈路預(yù)測的理論框架，并產(chǎn)生對實際預(yù)測有指導(dǎo)作用的理論結(jié)論，如通過對網(wǎng)絡(luò)結(jié)構(gòu)的統(tǒng)計分析估算各個方法的可預(yù)測的極限，從而指導(dǎo)選擇最佳的預(yù)測方法等；另一方面是如何通過網(wǎng)絡(luò)的結(jié)構(gòu)信息，借助復(fù)雜網(wǎng)絡(luò)的分析工具，設(shè)計高效的算法處理大規(guī)模網(wǎng)絡(luò)的鏈路預(yù)測問題。

盡管已有一些論文討論了如何將鏈路預(yù)測的方法和思想與一些應(yīng)用問題(如部分標號網(wǎng)絡(luò)的節(jié)點類型預(yù)測[19,64-65]與信息推薦問題[33,55-66])相聯(lián)系的可能性與方法，但是，目前尚缺乏對于大規(guī)模真實數(shù)據(jù)在應(yīng)用層面的深入分析和研究。這方面的研究不僅僅具有實用價值，而且有助于揭示鏈路預(yù)測問題本身存在的優(yōu)勢與局限性。

[1] GETOOR L, DIEHL C P. Link mining: a survey[J]. ACM SIGKDD Explorations Newsletter, 2005, 7(2): 3-12.

[2] SARUKKAI R R. Link prediction and path analysis using markov chains[J]. Computer Networks, 2000, 33(1-6):377-386.

[3] ZHU J, HONG J, HUGHES J G. Using markov chains for link prediction in adaptive web sites[J]. Lect Notes Comput Sci, 2002, 2311:60-73.

[4] POPESCUL A, UNGAR L. Statistical relational learning for link prediction[C]//Proceedings of the Workshop on Learning Statistical Models from Relational Data. New York:ACM Press, 2003: 81-87.

[5] O’MADADHAIN J, HUTCHINS J, SMYTH P. Prediction and ranking algorithms for event-based network data[C]//Proceedings of the ACM SIGKDD 2005. New York: ACM Press, 2005: 23-30.

[6] LIN D. An information-theoretic definition of similarity[C]//Proceedings of the 15th Intl Conf Mach. Learn.. San Francisco, Morgan Kaufman Publishers, 1998: 296-304.

[7] LIBEN-NOWELL D, KLEINBERG J. The link-prediction problem for social networks[J]. J Am Soc Inform Sci Technol, 2007, 58(7): 1019-1031.

[8] CLAUSET A, MOORE C, NEWMAN M E J. Hierarchical structure and the prediction of missing links in networks[J].Nature, 2008, 453: 98-101.

[9] HOLLAND P W, LASKEY K B, LEINHARD S. Stochastic blockmodels: First steps[J]. Social Networks, 1983, 5:109-137.

[10] GUIMERA R, SALES-PARDO M. Missing and spurious interactions and the reconstruction of complex networks[J].Proc Natl Sci Acad USA, 2009, 106(52): 22073-22078.

[11] YU H, BRAUN P, YILDIRIM M A, et al. High-quality binary protein interaction map of the yeast interactome network[J]. Science, 2008, 322(5898): 104-110.

[12] STUMPF M P H, THORNE T, SILVA E de, et al.Estimating the size of the human interactome[J]. Proc Natl Sci Acad USA, 2008, 105(19): 6959-6964.

[13] AMARAL L A N. A truer measure of our ignorance[J].Proc Natl Sci Acad USA, 2008, 105(19): 6795-6796.

[14] SCHAFER L, GRAHAM J W. Missing data: Our view of the state of the art[J]. Psychol Methods, 2002, 7(2):147-177.

[15] KOSSINETS G. Effects of missing data in social networks[J]. Social Networks, 2006, 28(3): 247-268.

[16] KUMAR R, NOVAK J, TOMKINS A. Structure and evolution of online social networks[C]// Proceedings of the ACM SIGKDD 2006. New York: ACM Press, 2006:611-617.

[17] GALLAGHER B, TONG H, ELIASSI-RAD T, et al. Using ghost edges for classification in sparsely labeled networks[C]// Proceedings of the ACM SIGKDD 2008.New York: ACM Press, 2008: 256-264.

[18] DASGUPTA K, SINGH R, VISWANATHAN B, et al.Social ties and their relevance to churn in mobile telecom networks[C]// Proceedings of the EDBT’08. New York:ACM Press, 2008: 668-677.

[19] MERING C V, KRAUSE R, SNEL B, et al. Comparative assessment of large-scale data sets of protein-protein interactions[J]. Nature, 2002, 417: 399-403.

[20] ALBERT R, BARABASI A-L. Statistical mechanics of complex networks[J]. Rev Mod Phys, 2002, 74(1): 47-97.

[21] DOROGOVTSEV S N, MENDES J F F. Evolution of networks[J]. Adv Phys, 2002, 51(4): 1079-1187.

[22] LEICHT E A, HOLME P, NEWMAN M E J. Vertex similarity in networks[J]. Phys Rev E, 2006, 73: 026120.

[23] PAN Y, LI D H, LIU J G, et al. Detecting community structure in complex networks via node similarity[J].Physica A, 2010, 389(14): 2849-2857.

[24] HANELY J A, MCNEIL B J. The meaning and use of the area under a receiver operating characteristic (ROC)curve[J]. Radiology, 1982, 143: 29-36.

[25] HERLOCKER J L, KONSTANN J A, TERVEEN K, et al.Evaluating collaborative filtering recommender systems[J].ACM Trans Inf Syst, 2004, 22(1): 5-53.

[26] ZHOU T, REN J, MEDO M, et al. Bipartite network projection and personal recommendation[J]. Phys Rev E,2007, 76: 046115.

[27] SALTON G, MCGILL M J. Introduction to modern information retrieval[M]. Auckland: MuGraw-Hill, 1983.

[28] JACCARD P. Etude comparative de la distribution florale dans une portion des Alpes et des Jura[J]. Bulletin de la Société Vaudoise des Science Naturelles, 1901, 37:547-579.

[29] SORENSEN T. A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons[J]. Biol Skr, 1948, 5(4): 1-34.

[30] RAVASZ E, SOMERA A L, MONGRU D A, et al.Hierarchical organization of modularity in metabolic networks[J]. Science, 2002, 297(5586): 1553-1555.

[31] BARABASI A-L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.

[32] ADAMIC L A, ADAR E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3): 211-230.

[33] ZHOU T, Lü L, ZHANG Y C. Predicting missing links via local information[J]. Eur Phys J B, 2009, 71(4): 623-630.

[34] Lü L, JIN C H, ZHOU T. Similarity index based on local paths for link prediction of complex networks[J]. Phys Rev E, 2009, 80: 046122.

[35] KATZ L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39-43.

[36] LIU W, Lü L. Link prediction based on local random walk[J]. Europhys Lett, 2010, 89(5): 58007.

[37] Klein D J, Randic M, Resistance distance[J]. J Math Chem,1993, 12(1): 81-95.

[38] FOUSS F, PIROTTE A, RENDERS J M, et al.Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J]. IEEE Trans Knowl Data Eng, 2007,19(3): 355-369.

[39] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. Comput Netw & ISDN Syst, 1998, 30(1-7): 107-117.

[40] JEH G, WIDOM J. SimRank: A measure of structuralcontext similarity[C]// Proceedings of the ACM SIGKDD 2002. New York: ACM Press, 2002: 538-543.

[41] TONG H, FALOUTSOS C, PAN J Y. Fast random walk with restart and its applications[C]// Proceedings of the 6th Intl Conf Data Min, Washington, D C, USA: IEEE Press,2006: 613-622.

[42] SHANG M S, Lü L, ZENG W, et al. Relevance is more significant than correlation: Information filtering on sparse data[J]. Europhys Lett, 2009, 88(6): 68008.

[43] Lü L, ZHOU T. Link prediction in weighted networks: The Role of Weak Ties[J]. Europhys Lett, 2010, 89(1): 18001.

[44] GRANOVETTER M S. The strength of weak ties[J]. Am J Sociology, 1973, 78(6): 1360-1380.

[45] RAVASZ E, BARABáasi A L. Hierarchical organization in complex networks[J]. Phys Rev E, 2003, 67: 026112.

[46] ZHOU C, ZEMANOVá L, ZAMORA G, et al. Hierarchical organization unveiled by functional connectivity in complex brain networks[J]. Phys Rev Lett, 2006, 97:238103.

[47] TASKAR B, WONG M F, ABBEEL P, et al. Link prediction in relational data[C]// Proceedings of the Neural Information Processing Systems(NIPS’03). Cambridge MA: MIT Press, 2004: 659-666.

[48] FRIEDMAN N, GETOOR L, KOLLER D, et al. Learning probabilistic relational models[C]// Proceedings of the 16th Intl Joint Conf Artif Intell(IJCAI). Stockholm, Sweden:[s.n.], 1999: 1300-1307.

[49] HECKERMAN D, MEEK C, KOLLER D. Probabilistic entity-relationship models, PRMs, and plate models[C]//Proceedings of the 21st Intl Conf Mach Learn, Banff,Canada: [s.n.], 2004: 55-60.

[50] HECKERMAN D, GEIGER D, CHICKERING D.Learning bayesian networks: the combination of knowledge and statistical data[J]. Mach, Learn, 1995, 20(3):197-243.

[51] TASKAR B, ABBEEL P, KOLLER D. Discriminative probabilistic models for relational data[C]// Proceedings of the UAI2002. Edmonton, Canada: [s.n.], 2002: 485-492.

[52] HECKERMAN D, CHICKERING D M, MEEK C, et al.Dependency networks for inference, collaborative filtering,and data visualization[J]. J Mach Learn Res, 2000, 1:49-75.

[53] NEVILLE J, JENSEN D. Relational dependency networks[J]. J Mach Learn Res, 2007, 8: 653-692.

[54] BESAG J. Statistical analysis of non-lattice data[J]. The Statistician, 1975, 24(3): 179-195.

[55] LESKOVEC J, HUTTENLOCHER D, KleinBerg J.Predicting positive and negative links in online social networks[C]// Proceedings of the WWW 2010. New York:ACM, 2010: 641-650.

[56] MURATA T, MORIYASU S. Link prediction of social networks based on weighted proximity measures[C]//Proceedings of the IEEE/WIC/ACM Intl Conf Web Intelligence. Washington, D C, USA: IEEE Press, 2007:85-88.

[57] BARABASI A-L. Scale-Free Networks: a decade and beyond[J]. Science, 2009, 325(5939): 412-413.

[58] CALDARELLI G. Scale-Free Networks: complex webs in nature and technology[M]. New York: Oxford Press, 2007.

[59] GARLASCHELLI D, CAPOCCI A, CALDARELLI G.Self-organized network evolution coupled to extremal dynamics[J]. Nature Physics, 2007, 3: 813-817.

[60] VALVERDE S, CANCHO R F, SOLE R V. Scale-free networks from optimal design[J]. Europhys Lett, 2002,60(4): 512-517.

[61] BAIESI M, MANNA S S. Scale-free networks from a Hamiltonian dynamics[J]. Phys Rev E, 2003, 68: 047103.

[62] KIM B J, TRUSINA A, MINNHAGEN P, et al. Self organized scale-free networks from merging and regeneration[J]. Eur Phys J B, 2005, 43(3): 369-372.

[63] PEROTTI J I, BILLONI O V, TAMARIT F A, et al.Emergent self-organized complex network topology out of stability constraints[J]. Phys Rev Lett, 2009, 103: 108701.

[64] ZHANG Q M, SHANG M S, Lü L. Similarity-based classification in partially labeled networks[J]. Int J Mod Phys C, 2010, 21(6): 813-824.

[65] SEN P, NAMATA G, BILGIC M, et al. Collective classification in network data[J]. AI Magazine, 2008, 29(3):93-106.

[66] ZHOU T. Statistical mechanics of information systems:information filtering on complex networks[D]. Switzerland:University of Fribourg, 2010.