復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)

呂琳媛

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

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

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

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

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

1 問題描述與評(píng)價(jià)方法

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

Precision定義為在前L個(gè)預(yù)測(cè)邊中被預(yù)測(cè)準(zhǔn)確的比例。如果有m個(gè)預(yù)測(cè)準(zhǔn)確，即排在前L的邊中有m個(gè)在測(cè)試集中，則Precision定義為：顯然，Precision越大預(yù)測(cè)越準(zhǔn)確。如果兩個(gè)算法AUC相同，而算法1的Precision大于算法2，說明算法1更好，因?yàn)槠鋬A向于把真正連邊的節(jié)點(diǎn)對(duì)排在前面。

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

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

2.1 基于局部信息的相似性指標(biāo)

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

另一個(gè)只考慮節(jié)點(diǎn)度的相似性為優(yōu)先連接指標(biāo)(preferential attachment)。應(yīng)用優(yōu)先連接的方法可以產(chǎn)生無標(biāo)度的網(wǎng)絡(luò)結(jié)構(gòu)，在該網(wǎng)絡(luò)中，一條即將加入的新邊連接到節(jié)點(diǎn)x的概率正比于節(jié)點(diǎn)x的度k(x)[31]，因此新邊連接節(jié)點(diǎn)x和y的概率正比于兩節(jié)點(diǎn)度的乘積。該算法的復(fù)雜度較其他算法低，因?yàn)樾枰男畔⒘孔钌佟?/p>

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

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

表1 10種基于節(jié)點(diǎn)局部信息的相似性指標(biāo)

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

表2 6個(gè)實(shí)驗(yàn)網(wǎng)絡(luò)的拓?fù)湫再|(zhì)

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

2.2 基于路徑的相似性指標(biāo)

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

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

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

2.3 基于隨機(jī)游走的相似性指標(biāo)

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

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

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

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

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

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

這個(gè)指標(biāo)的目的就是給鄰近目標(biāo)節(jié)點(diǎn)的點(diǎn)更多的機(jī)會(huì)與目標(biāo)節(jié)點(diǎn)相連。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(5) 當(dāng)該馬爾科夫鏈?zhǔn)諗坑谄椒€(wěn)時(shí)，開始生成可用的樹形圖，如5 000個(gè)。

3.2 隨機(jī)分塊模型[10]

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

4 概率模型

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

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

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

概率關(guān)系模型是將概率模型和關(guān)系模型相結(jié)合的一種預(yù)測(cè)模型。概率關(guān)系模型包括3個(gè)網(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ò)與目標(biāo)網(wǎng)絡(luò)(測(cè)試集)相結(jié)合的網(wǎng)絡(luò)，用于對(duì)目標(biāo)網(wǎng)絡(luò)的預(yù)測(cè)。根據(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)概率實(shí)體關(guān)系模型(DAPER)[49]

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

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

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

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

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

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

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

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

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

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

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

[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.