鏈路預(yù)測(cè)的方法與發(fā)展綜述

(北京信息科技大學(xué) 信息與通信工程學(xué)院,北京 100101)

復(fù)雜網(wǎng)絡(luò)能夠很好地描述社會(huì)科學(xué)、自然科學(xué)、管理科學(xué)以及工程技術(shù)等領(lǐng)域的相互關(guān)聯(lián)的復(fù)雜模型，應(yīng)用范圍廣泛。其以復(fù)雜系統(tǒng)為研究目標(biāo)，利用數(shù)學(xué)、統(tǒng)計(jì)學(xué)、計(jì)算機(jī)等科學(xué)工具，分析和研究事物的本質(zhì)結(jié)構(gòu)和規(guī)律。復(fù)雜網(wǎng)絡(luò)具有規(guī)模龐大、連接結(jié)構(gòu)復(fù)雜、節(jié)點(diǎn)種類多樣以及網(wǎng)絡(luò)演化過(guò)程復(fù)雜的特點(diǎn)，使得其研究充滿了挑戰(zhàn)。但是，掌握了復(fù)雜網(wǎng)絡(luò)的演化規(guī)律可以幫助人們更好地掌控網(wǎng)絡(luò)結(jié)構(gòu)的變化趨勢(shì)，因此，吸引了越來(lái)越多的人去探索復(fù)雜網(wǎng)絡(luò)已存在的結(jié)構(gòu)特征及其發(fā)展趨勢(shì)。

鏈路預(yù)測(cè)是研究復(fù)雜網(wǎng)絡(luò)的核心內(nèi)容之一。在復(fù)雜網(wǎng)絡(luò)中，個(gè)體被稱為節(jié)點(diǎn)，節(jié)點(diǎn)與節(jié)點(diǎn)間的關(guān)系稱為鏈接。鏈接的內(nèi)在機(jī)制、形式和結(jié)構(gòu)在不同系統(tǒng)中的演變過(guò)程揭示了人類在社會(huì)活動(dòng)中的行為和趨勢(shì)[1]。研究鏈接的產(chǎn)生有助于塑造和提高對(duì)人類行為和社會(huì)網(wǎng)絡(luò)的理解，也有助于推進(jìn)對(duì)其他眾多領(lǐng)域的研究，比如社交軟件的好友推薦系統(tǒng)、網(wǎng)絡(luò)超鏈接的預(yù)測(cè)以及股市走向等。準(zhǔn)確的鏈路預(yù)測(cè)為復(fù)雜網(wǎng)絡(luò)的進(jìn)化研究工作提供了有力幫助。因此，對(duì)復(fù)雜網(wǎng)絡(luò)中的結(jié)構(gòu)和鏈路進(jìn)行研究和建模是十分必要的。

本文對(duì)節(jié)點(diǎn)屬性、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、機(jī)器學(xué)習(xí)、最大似然等4類鏈路預(yù)測(cè)方法進(jìn)行總結(jié)與概括，介紹了各類方法中學(xué)者們提出的一些經(jīng)典算法，對(duì)這4種方法的優(yōu)缺點(diǎn)進(jìn)行了闡述。對(duì)幾種較為常見的評(píng)價(jià)鏈路預(yù)測(cè)算法精確度的方法進(jìn)行了介紹，最后對(duì)鏈路預(yù)測(cè)的未來(lái)研究方向和發(fā)展前景進(jìn)行了總結(jié)和展望。

1 網(wǎng)絡(luò)模型介紹

表1 網(wǎng)絡(luò)符號(hào)及定義

鏈路預(yù)測(cè)的定義為：對(duì)選定的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行處理，將連邊集合E分成訓(xùn)練集ET和測(cè)試集EP兩部分，且訓(xùn)練集和測(cè)試集并無(wú)交集。一般隨機(jī)選擇邊作為測(cè)試集的邊，時(shí)序鏈路預(yù)測(cè)中，會(huì)將最近時(shí)間內(nèi)產(chǎn)生的邊作為測(cè)試集。利用鏈路預(yù)測(cè)方法，計(jì)算出訓(xùn)練集中的給定節(jié)點(diǎn)對(duì)(x,y)的評(píng)分?jǐn)?shù)值Sxy，并將評(píng)分?jǐn)?shù)值Sxy按大小進(jìn)行排序，如果節(jié)點(diǎn)對(duì)的評(píng)分?jǐn)?shù)值越大，那么節(jié)點(diǎn)間產(chǎn)生鏈接的可能性越大，將得到的預(yù)測(cè)結(jié)果與測(cè)試集進(jìn)行對(duì)比得出評(píng)價(jià)結(jié)果，從而得出真實(shí)網(wǎng)絡(luò)的演化模型并對(duì)其進(jìn)行預(yù)測(cè)和分析。其具體過(guò)程如圖1所示。

圖1 鏈路預(yù)測(cè)過(guò)程描述

鏈路預(yù)測(cè)的方法基本分為4類：以節(jié)點(diǎn)屬性為基礎(chǔ)、以網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為基礎(chǔ)、以機(jī)器學(xué)習(xí)為基礎(chǔ)以及以最大似然為基礎(chǔ)?；诠?jié)點(diǎn)屬性的鏈路預(yù)測(cè)方法有助于提高預(yù)測(cè)準(zhǔn)確度，但是節(jié)點(diǎn)屬性，如姓名、愛好、地理位置等信息難以獲取，而且已獲取信息的時(shí)效性和真實(shí)性不能確定。與該方法相比較，基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方法容易獲取網(wǎng)絡(luò)結(jié)構(gòu)信息，通過(guò)網(wǎng)絡(luò)結(jié)構(gòu)，更容易發(fā)現(xiàn)哪些節(jié)點(diǎn)更傾向于連接或斷開連接。部分學(xué)者利用基于機(jī)器學(xué)習(xí)或最大似然等技術(shù)更新的鏈路預(yù)測(cè)方法，與節(jié)點(diǎn)屬性、網(wǎng)絡(luò)結(jié)構(gòu)等信息相結(jié)合，綜合性地對(duì)連接關(guān)系進(jìn)行預(yù)測(cè)，大大提高了鏈路預(yù)測(cè)的準(zhǔn)確程度。

2 鏈路預(yù)測(cè)方法分類

2.1 基于節(jié)點(diǎn)屬性的方法

在早期對(duì)鏈路預(yù)測(cè)的研究中，多數(shù)學(xué)者采用的是基于節(jié)點(diǎn)屬性的鏈路預(yù)測(cè)方法。兩個(gè)節(jié)點(diǎn)的屬性，如興趣愛好等越相似，就越容易產(chǎn)生連接。在社交網(wǎng)絡(luò)中，最簡(jiǎn)單的獲得節(jié)點(diǎn)屬性的方法就是使用標(biāo)簽。卜心怡等人[2]利用微博做出了實(shí)證分析，用粉絲數(shù)量、微博數(shù)量、關(guān)注人數(shù)、轉(zhuǎn)發(fā)微博數(shù)量等作為節(jié)點(diǎn)屬性標(biāo)簽，與基于共同鄰居的算法相結(jié)合進(jìn)行節(jié)點(diǎn)連接的預(yù)測(cè)。Jure等人[3]利用包含超過(guò)300億次對(duì)話、1.8億節(jié)點(diǎn)與13億鏈接的數(shù)據(jù)集進(jìn)行了仿真，證明人們更傾向于和相同地區(qū)、共同興趣、愛好相似的人建立新連接。利用節(jié)點(diǎn)屬性等信息可以提高的預(yù)測(cè)準(zhǔn)確性，但網(wǎng)絡(luò)用戶更傾向于保護(hù)自己的隱私，信息的獲取變得難度很大，即使成功獲取信息也無(wú)法保證其準(zhǔn)確性。此外，在獲取信息后，如何提取有用信息也是較為煩瑣的工程。因此，基于節(jié)點(diǎn)屬性的鏈路預(yù)測(cè)方法在實(shí)現(xiàn)上具有一定的難度，更多學(xué)者傾向于使用以網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為基礎(chǔ)的方法進(jìn)行鏈路預(yù)測(cè)。

2.2 基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方法

基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的鏈路預(yù)測(cè)方法的原理為：以網(wǎng)絡(luò)結(jié)構(gòu)的相似性為基礎(chǔ)，判別節(jié)點(diǎn)的相似性，兩個(gè)節(jié)點(diǎn)的結(jié)構(gòu)越相似，那么它們之間越可能產(chǎn)生連接。以網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為研究基礎(chǔ)的鏈路預(yù)測(cè)方法，可以分為3種研究方向：以局部信息、路徑和隨機(jī)游走為基礎(chǔ)。

解決鏈接預(yù)測(cè)問題最有效的方法是建立相似性指標(biāo)。不同的鏈路預(yù)測(cè)方法主要區(qū)別之一即是相似性指標(biāo)的不同。相似性指標(biāo)是定義網(wǎng)絡(luò)節(jié)點(diǎn)之間相似性的評(píng)分函數(shù)，根據(jù)該函數(shù)對(duì)網(wǎng)絡(luò)中所有的節(jié)點(diǎn)，兩兩計(jì)算相應(yīng)的評(píng)分?jǐn)?shù)值。

2.2.1 基于局部信息的方法

在基于局部信息的鏈路預(yù)測(cè)方法中，最基本的是共同鄰居(Common Neighbor，CN)指標(biāo)。CN評(píng)價(jià)指標(biāo)代表了兩個(gè)節(jié)點(diǎn)間共同鄰居的多少。如果其數(shù)目越多，這兩個(gè)節(jié)點(diǎn)越可能進(jìn)行連接。除此之外，CN評(píng)價(jià)指標(biāo)還有很多基于鄰居其他屬性的評(píng)價(jià)方式：Salton指標(biāo)[4]、Jaccard指標(biāo)、Sorensen指標(biāo)、LHN-I指標(biāo)等，如表2所示，分別利用了共同鄰居、鄰居的并集以及節(jié)點(diǎn)的度屬性等。另外，Adamic和Adar還提出了AA指標(biāo)，其主要考慮節(jié)點(diǎn)對(duì)共同鄰居的重要程度不同，從而通過(guò)共同鄰居的度來(lái)突出這一特點(diǎn)。Zhou等人[5]對(duì)9種基于局部性的指標(biāo)進(jìn)行了準(zhǔn)確性對(duì)比，并提出了準(zhǔn)確度更高的資源分配(Resource Allocation，RA)指標(biāo)。大量的實(shí)驗(yàn)結(jié)果顯示，RA指標(biāo)與AA指標(biāo)的表現(xiàn)相近，但在準(zhǔn)確性上略微高于AA指標(biāo)。

表2 相似性指標(biāo)及其定義公式

2.2.2 基于路徑的方法

基于路徑的相似性指標(biāo)有3種不同的研究方向，局部路徑(Local Paths，LP)指標(biāo)、LHZ-II指標(biāo)以及Katz指標(biāo)。

CN指標(biāo)可以看作是考慮兩個(gè)節(jié)點(diǎn)間的二階路徑數(shù)目，LP指標(biāo)在CN指標(biāo)的基礎(chǔ)上進(jìn)行了改進(jìn)，在二階路徑的基礎(chǔ)上再考慮三階路徑數(shù)目。當(dāng)考慮的階數(shù)越來(lái)越多，趨近于無(wú)窮時(shí)，這一指標(biāo)的計(jì)算公式就相當(dāng)于Katz指標(biāo)了，與LP指標(biāo)相比，Katz指標(biāo)的計(jì)算復(fù)雜度也成倍增高。Leicht等人提出了基于自相似度矩陣的LHZ-II指標(biāo)，表示如果兩個(gè)節(jié)點(diǎn)是相似的，它們?cè)诰W(wǎng)絡(luò)中的鄰居也相似，那么它們建立連接的可能性較大。LHZ-II指標(biāo)可以使用網(wǎng)絡(luò)的鄰接矩陣關(guān)系，進(jìn)行多次迭代遍歷網(wǎng)絡(luò)中所有節(jié)點(diǎn)的相互關(guān)系，進(jìn)行鏈路預(yù)測(cè)。

2.2.3 基于隨機(jī)游走的方法

基于隨機(jī)游走的指標(biāo)，比如Cos+指標(biāo)、重新開始的隨機(jī)游走指標(biāo)(Random Walk with Restart,RWR)以及Sim Rank指標(biāo)等。

Fouss等人基于馬爾科夫隨機(jī)游走模型，通過(guò)計(jì)算平均通勤時(shí)間等信息，為節(jié)點(diǎn)對(duì)之間的鏈接定義Cos+相似性指標(biāo)。實(shí)驗(yàn)結(jié)果表明，該算法在Mivieles數(shù)據(jù)集上表現(xiàn)良好，但不能很好地應(yīng)用于大型數(shù)據(jù)集。張學(xué)佩[6]定義了局部隨機(jī)游走的節(jié)點(diǎn)相似度指標(biāo)，并與其他相似性指標(biāo)進(jìn)行比較。結(jié)果表明，其提出的算法具有更低的計(jì)算復(fù)雜度。Jeh等人認(rèn)為，如果兩個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)相似，則它們是相似的，并據(jù)此提出了Sim Rank指標(biāo)。

2.3 基于機(jī)器學(xué)習(xí)的方法

現(xiàn)有的鏈路預(yù)測(cè)方法除了以相似性為研究基礎(chǔ)，還有基于機(jī)器學(xué)習(xí)的方法，主要分為三大類：特征分類、概率模型以及矩陣分解?；跈C(jī)器學(xué)習(xí)的算法有助于解決數(shù)據(jù)挖掘中的常見問題，例如類別不平衡，過(guò)度擬合等。

在基于特征分類的鏈路預(yù)測(cè)算法方面，很多學(xué)者使用監(jiān)督學(xué)習(xí)中一些較為常用的算法，比如支持向量機(jī)、決策樹、徑向基網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)[7]等，對(duì)未知鏈接進(jìn)行預(yù)測(cè)，其中預(yù)測(cè)精度最高的是支持向量機(jī)方法。Li等人[8]將快速分類法應(yīng)用于支持向量機(jī)，對(duì)分類器進(jìn)行訓(xùn)練，把大部分預(yù)測(cè)過(guò)程中測(cè)試階段傳遞到訓(xùn)練階段，大大減少了預(yù)測(cè)階段的時(shí)間復(fù)雜度。Yuan等人[9]提取推特中用戶的情感信息，通過(guò)分析情感特征來(lái)判斷兩個(gè)用戶是否可能成為好友。實(shí)驗(yàn)結(jié)果表明，提出的模型優(yōu)于Logistic分類器和隨機(jī)森林。

基于概率模型的鏈路預(yù)測(cè)算法的主要思想為，首先建立一個(gè)可以調(diào)整參數(shù)的可預(yù)測(cè)模型，然后在調(diào)整參數(shù)的過(guò)程中找到使模型達(dá)到最優(yōu)的參數(shù)值，可令模型的預(yù)測(cè)準(zhǔn)確度達(dá)到最高。構(gòu)建概率模型的方法主要有馬爾科夫網(wǎng)絡(luò)關(guān)系模型以及貝葉斯網(wǎng)絡(luò)模型等。Liben等人[10]首先利用機(jī)器學(xué)習(xí)的方法進(jìn)行了鏈路預(yù)測(cè)，且預(yù)測(cè)準(zhǔn)確度較高。Asil等人[11]使用監(jiān)督學(xué)習(xí)的方法進(jìn)行鏈路預(yù)測(cè)，并證明多數(shù)情況下，加權(quán)網(wǎng)絡(luò)比未加權(quán)網(wǎng)絡(luò)在監(jiān)督和非監(jiān)督方法中都有更好的預(yù)測(cè)結(jié)果。Gupta等人[12]將鏈路預(yù)測(cè)問題視為二元分類問題，應(yīng)用貝葉斯分類來(lái)預(yù)測(cè)網(wǎng)絡(luò)中缺失的鏈接?；诟怕誓Ｐ偷逆溌奉A(yù)測(cè)研究可以擴(kuò)展到包括社交網(wǎng)絡(luò)分析在內(nèi)的各個(gè)領(lǐng)域，可以用來(lái)發(fā)現(xiàn)生物學(xué)中蛋白質(zhì)的相互作用[19]，幫助建立電子社交網(wǎng)絡(luò)中的推薦系統(tǒng)[13]，還可以識(shí)別出社交網(wǎng)絡(luò)中隱藏的連接。

在基于矩陣分解的鏈路預(yù)測(cè)算法，Menon等人[15]提出了一個(gè)擴(kuò)展矩陣分解的模型來(lái)解決有向網(wǎng)絡(luò)中的鏈路預(yù)測(cè)問題，并在實(shí)驗(yàn)中證明，顯式特征通常能夠提供比隱式特征更好地鏈路預(yù)測(cè)結(jié)果，但兩者結(jié)合可以更好地提高預(yù)測(cè)性能。郭麗媛[16]提出用集體矩陣分解方法將可用的鏈接信息從相對(duì)密集的交互網(wǎng)絡(luò)轉(zhuǎn)移到稀疏的目標(biāo)網(wǎng)絡(luò)，通過(guò)網(wǎng)絡(luò)相似性來(lái)建立源網(wǎng)絡(luò)和目標(biāo)網(wǎng)絡(luò)之間的對(duì)應(yīng)關(guān)系。Ahmed等人[17]針對(duì)動(dòng)態(tài)圖中的鏈路預(yù)測(cè)問題，提出了一種基于非負(fù)矩陣分解的方法，該方法從動(dòng)態(tài)網(wǎng)絡(luò)的時(shí)間和拓?fù)浣Y(jié)構(gòu)中學(xué)習(xí)潛在特征，可以獲得更高的預(yù)測(cè)結(jié)果。該方法應(yīng)用新的迭代規(guī)則構(gòu)造具有重要網(wǎng)絡(luò)特征的矩陣因子，并證明了算法的收斂性和正確性。

2.4 基于最大似然的方法

基于最大似然的鏈路預(yù)測(cè)方法的基本思路是：根據(jù)目前已經(jīng)觀測(cè)到的網(wǎng)絡(luò)中的鏈路計(jì)算網(wǎng)絡(luò)的似然值，并假設(shè)真實(shí)網(wǎng)絡(luò)的似然值最大，最后根據(jù)網(wǎng)絡(luò)似然最大化，計(jì)算所有未連接節(jié)點(diǎn)間的連邊概率。以網(wǎng)絡(luò)結(jié)構(gòu)為研究基礎(chǔ)的最大似然估計(jì)方法較為適用于具有組合結(jié)構(gòu)的網(wǎng)絡(luò)類型。

2008年，Clauset等人提出一種通過(guò)網(wǎng)絡(luò)數(shù)據(jù)推斷網(wǎng)絡(luò)層級(jí)結(jié)構(gòu)的方法，證明層次結(jié)構(gòu)可以用來(lái)預(yù)測(cè)網(wǎng)絡(luò)中丟失的鏈接，并具有較高的精確度。劉繼嘉[18]提出了一個(gè)擴(kuò)展的經(jīng)典隨機(jī)塊模型，預(yù)測(cè)了網(wǎng)絡(luò)中的丟失鏈接和錯(cuò)誤鏈接。田甜等人[19]提出了一種基于最大似然估計(jì)的層次隨機(jī)圖模型，利用腦網(wǎng)絡(luò)數(shù)據(jù)建立層級(jí)隨機(jī)圖，通過(guò)改進(jìn)的馬爾科夫蒙特卡洛算法對(duì)樹狀圖空間進(jìn)行采樣，最后計(jì)算腦網(wǎng)絡(luò)邊的平均連接概率，實(shí)驗(yàn)驗(yàn)證，該算法比傳統(tǒng)的算法計(jì)算復(fù)雜度低。

3 衡量算法精確度

衡量鏈路預(yù)測(cè)算法準(zhǔn)確度的指標(biāo)最常用的有3種：AUC(Area Under ROC Curve，ROC曲線下面積)、Precision和Ranking Score。

3.1 AUC

AUC的評(píng)價(jià)方式為：每次從測(cè)試集EP中隨機(jī)選取一條邊，再隨機(jī)從不存在的邊的集合中選取一條邊，對(duì)兩者的評(píng)分?jǐn)?shù)值Sij進(jìn)行比較，若測(cè)試集中的邊分?jǐn)?shù)高，則記1分，若兩者相等，記0.5分。假定一共比較n次，其中有n′次測(cè)試集分?jǐn)?shù)高，有n″次兩者分?jǐn)?shù)相同，則AUC計(jì)算值為

(1)

3.2 Precision

在鏈路預(yù)測(cè)完成后，需要對(duì)所有的邊計(jì)算的評(píng)分?jǐn)?shù)值由高到低排序，而Precision計(jì)算的是排在前L位的邊中，預(yù)測(cè)正確的邊所占比例，即如果在預(yù)測(cè)后的排序結(jié)果中，排在前L位的邊有m個(gè)與測(cè)試集中的邊相同，那么Precision的計(jì)算值為

(2)

當(dāng)兩個(gè)鏈路預(yù)測(cè)方法的AUC值相同時(shí)，用Precision比較其準(zhǔn)確性，Precision值越大，越傾向于把連邊準(zhǔn)確的節(jié)點(diǎn)對(duì)排在前面。

3.3 Ranking Score

(3)

4 結(jié)束語(yǔ)

綜上所述，無(wú)論是通過(guò)節(jié)點(diǎn)屬性、網(wǎng)絡(luò)拓?fù)?，還是基于概率模型，都是通過(guò)已知的數(shù)據(jù)，盡可能貼近實(shí)際情況刻畫鏈路的連接走向，但它們各自有優(yōu)缺點(diǎn)?；诠?jié)點(diǎn)屬性的預(yù)測(cè)方法通過(guò)獲取用戶信息來(lái)確定連接關(guān)系，但無(wú)法確定用戶信息的真實(shí)性和準(zhǔn)確性，深入挖掘又涉及用戶的隱私問題，單從這一方面進(jìn)行預(yù)測(cè)，準(zhǔn)確率難以保證。通過(guò)網(wǎng)絡(luò)拓?fù)鋪?lái)進(jìn)行預(yù)測(cè)，計(jì)算復(fù)雜度比較低，只通過(guò)網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測(cè)鏈路需要獲取的數(shù)據(jù)較為簡(jiǎn)單。機(jī)器學(xué)習(xí)是最近較為熱門的方向，與鏈路預(yù)測(cè)相結(jié)合會(huì)得到更高的預(yù)測(cè)準(zhǔn)確率。概率模型是數(shù)據(jù)挖掘的傳統(tǒng)模型，它同時(shí)考慮了節(jié)點(diǎn)屬性和網(wǎng)絡(luò)結(jié)構(gòu)，能夠得到較好的準(zhǔn)確度，可是計(jì)算復(fù)雜度和用戶屬性的獲取都是它無(wú)法大規(guī)模進(jìn)行采用實(shí)施的原因。

目前，鏈路預(yù)測(cè)廣泛應(yīng)用于生物系統(tǒng)、社交關(guān)系、推薦好友方式、股市走向等方面，已經(jīng)成為一門熱門的交叉學(xué)科。如何在不侵犯用戶隱私、計(jì)算復(fù)雜度低的條件下設(shè)計(jì)出快速、準(zhǔn)確的鏈路預(yù)測(cè)模型，從而應(yīng)用于大規(guī)模復(fù)雜網(wǎng)絡(luò)上，是接下來(lái)要繼續(xù)攻克的難題。