一種基于節(jié)點局部相似性的復雜網(wǎng)絡(luò)鏈路預(yù)測算法

白 樺 馬云龍 畢 玉 張為子

1(上海高重信息科技有限公司 上海 200072)2(同濟大學 上海 201804)

0 引 言

許多領(lǐng)域中，不同種類的數(shù)據(jù)都可以表示為具有代表個體的節(jié)點和代表它們之間交互關(guān)系的邊的網(wǎng)絡(luò)。在理解社會網(wǎng)絡(luò)中的信息傳播，人與人之間的相互作用，蛋白質(zhì)的結(jié)構(gòu)相似性以及人、公司或國家之間的商業(yè)關(guān)系框架等問題中，復雜網(wǎng)絡(luò)有著重要的作用，并且得到了廣泛的研究。與人們生活關(guān)系密切的社交網(wǎng)絡(luò)就是復雜網(wǎng)絡(luò)的一個經(jīng)典例子。人們之間可能相距很遠，有不同的文化、不同的語言，但是人與人之間的相互作用通過網(wǎng)絡(luò)媒介交織在一起構(gòu)成了復雜的社交網(wǎng)絡(luò)。社交網(wǎng)絡(luò)有助于人們接收來自世界各地的新聞、與朋友保持聯(lián)系、促進學術(shù)和文化交流等。復雜網(wǎng)絡(luò)的另一個例子是信息網(wǎng)絡(luò)，它也被稱為“知識網(wǎng)絡(luò)”[1]，且具有與社交網(wǎng)絡(luò)類似的結(jié)構(gòu)特征。信息網(wǎng)絡(luò)最常見的例子是引文網(wǎng)絡(luò)，在其中作者們通過共同出版學術(shù)文獻或者共同引用參考文獻來互動[2]。生物網(wǎng)絡(luò)可能為復雜網(wǎng)絡(luò)提供另一個例子，節(jié)點代表蛋白質(zhì)、代謝物質(zhì)或者生物體，相應(yīng)的連邊代表蛋白質(zhì)-蛋白質(zhì)相互作用、代謝途徑或生物體之間的遺傳相互作用。無論在何種網(wǎng)絡(luò)中，個體及其在網(wǎng)絡(luò)結(jié)構(gòu)中的不同關(guān)系可以簡單地抽象為由一組節(jié)點(頂點)和邊(鏈接)組成的圖。這樣的圖可以定義為G=〈V，E〉，其中V是頂點集，E是圖中的邊集[3]。

網(wǎng)絡(luò)科學中最早的研究對象是基于Erd?s和Rényi提出的隨機圖[4]，在n(n-1)/2條可能的邊上以p的概率隨機連接n條邊。Aiello等[5]對隨機圖進行了更深入的研究，證明了網(wǎng)絡(luò)的共同特性及其概率分布，并為長期以來的研究提供了新的研究思路。后來的研究者將他們的注意力轉(zhuǎn)移到了真實的網(wǎng)絡(luò)(而不是隨機產(chǎn)生的)，并解釋了它們的形成和演變機制。網(wǎng)絡(luò)科學研究主要包括復雜網(wǎng)絡(luò)的統(tǒng)計分析[6]、社區(qū)檢測和節(jié)點分類[7]、動態(tài)網(wǎng)絡(luò)隨時間的演變機制[8]、信息擴散和級聯(lián)分析[9]、網(wǎng)絡(luò)數(shù)據(jù)挖掘[10]和可視化[11]等。其中一個長期存在的挑戰(zhàn)是復雜網(wǎng)絡(luò)中的鏈路預(yù)測問題。鏈路預(yù)測是指通過已知的網(wǎng)絡(luò)拓撲結(jié)構(gòu)以及網(wǎng)絡(luò)節(jié)點屬性等信息，預(yù)測網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個節(jié)點之間產(chǎn)生鏈接的可能性或者推斷網(wǎng)絡(luò)中缺失的連邊[12]。

鏈路預(yù)測的通用框架是計算節(jié)點之間的相似性：如果兩個節(jié)點更相似，則它們將來更可能被連接?；诖思僭O(shè)，設(shè)未連接節(jié)點對(x,y)之間的相似性為Sxy，具有高相似性得分的Sxy尚未存在的節(jié)點對之間有高概率被鏈接起來。這些方法完全基于網(wǎng)絡(luò)的結(jié)構(gòu)信息，可以分為三種類型：全局、局部和準局部。

本文主要針對基于局部相似性的方法展開?；诰植肯嗨菩缘姆椒僭O(shè)：如果節(jié)點對具有共同的鄰居結(jié)構(gòu)或節(jié)點對中的某一節(jié)點已經(jīng)具有更高的度，則它們可能形成鏈接。因為它們僅適用基于鄰居相關(guān)結(jié)構(gòu)的局部拓撲信息而不是考慮整個網(wǎng)絡(luò)結(jié)構(gòu)，所以它們比基于全局相似性的方法更快。許多研究表明在動態(tài)網(wǎng)絡(luò)上，它們的性能比起基于全局相似性的方法更加優(yōu)越。它們被限制為僅計算節(jié)點對的所有可能組合的相似性，因為它們僅對距離為2的節(jié)點之間的相似性進行排序。

1 鏈路預(yù)測算法

1.1 CN指標

因為CN(Common-Neighbor)高效簡單，所以CN在鏈路預(yù)測中使用很廣泛。其思路為：未來兩個節(jié)點產(chǎn)生鏈接的概率受其共同節(jié)點數(shù)量的影響，即如果兩個節(jié)點具有更多共同鄰居，則很可能建立鏈接。對于網(wǎng)絡(luò)中的節(jié)點x，定義它的鄰居為Γ(x)，節(jié)點x的度為k(x)=|Γ(x)|，則CN指標的相似性分數(shù)可定義為：

Sxy=|Γ(x)∩Γ(y)|

(1)

1.2 AA指標

AA(Admic-Adar)指標于2003年被提出，主要用于社交網(wǎng)絡(luò)中的鏈路預(yù)測計算。該指標的相似性分數(shù)定義如下：

(2)

1.3 RA指標

RA(Resource-Allocation)指標于2009年被提出，其目的是應(yīng)用于各種網(wǎng)絡(luò)中的鏈路預(yù)測。該指標的相似性分數(shù)定義如下：

(3)

1.4 ERA指標

ERA(Enhanced-Resource-Allocation)指標綜合了AA和RA的思想，共同鄰居節(jié)點中度小的節(jié)點貢獻度更大，可以更進一步增加小度節(jié)點的相似度，減少大度節(jié)點的相似度。該指標的相似性分數(shù)定義如下：

(4)

對于無向圖中任意一個頂點x而言，其所有的鄰居節(jié)點之間互相都有共同的鄰居頂點x。首先，從無向圖中獲得帶權(quán)的邊的集合，其中邊的權(quán)為源點的度。然后根據(jù)邊的源節(jié)點v進行分組，這樣每組中的目的節(jié)點相互都有共同的鄰居節(jié)點，為源節(jié)點v。所以將每組中的目的節(jié)點兩兩組合起來，并加上源點的度的常用對數(shù)的倒數(shù)的平方，就得到一個集合，該集合中的所有元組中的兩個節(jié)點都有一個共同鄰居。最后，將該集合中兩個節(jié)點對應(yīng)相等的元組結(jié)合起來，并將元組兩頂點共同鄰居的常用對數(shù)的倒數(shù)的平方的值degree加起來就得到了ERA相似性分數(shù)。ERA的算法描述如下：

輸入：無向圖graph

輸出：圖graph中所有節(jié)點對之間的EAA相似性分數(shù)

1. 從graph中得到邊集DataSet>edge

2. 將邊集edge按照source vertex id分組，分為n組，其中source vertex id相等的元組組成同一組，記為group1i(其中，i=0,1,…，n-1)

3. FOR i←0 TO n-1

IF group1i中元素個數(shù)>1

用數(shù)組list[m]按照target vertex id從小到大的順序存儲group1i中所有的元素

FOR j←0 TO m-2

FOR k←j+1 TO m-1

產(chǎn)生元組Tuple3

1/(lg(source vertex degree))2>

將該元組加入收集器Collector1

END FOR

END FOR

END IF

END FOR

4. DataSet>tem←Collector1

5. 將數(shù)據(jù)集tem按照first vertex id和second vertex id分組，分為p組，其中各自first vertex id和second vertex id都相等的元組組成同一組，記為group2u(其中，u=0,1,……，p-1)

6. FOR u←0 TO p-1

將group2u中所有的元組的第三個域inverse of degree相加得到score

產(chǎn)生元組Tuple3，并加入收集器Collector2

END FOR

7. DataSet>result←Collector2

1.5 評價方法

鏈路預(yù)測的主要評價指標有AUC、Precision和Ranking Score三種，本文中使用AUC作為評價指標。AUC是ROC曲線之下和x軸之間的面積，因為ROC曲線一般處于y=x直線的上方，所以AUC的范圍在0.5～1之間。對鏈路預(yù)測算法進行多次AUC的抽樣比較后，如果測試邊集中的測試結(jié)果大于不存在邊集的測試結(jié)果，則取值為1，如果相等則取值0.5。AUC可通過以下公式計算[13]：

(5)

2 實 驗

2.1 實驗設(shè)置

在本文中使用AUC指標來評價鏈路預(yù)測算法的表現(xiàn)，為了計算AUC，需要劃分訓練集和測試集，在劃分訓練集和測試集時為了避免隨機性對結(jié)果的干擾，將進行多次劃分重復計算AUC。具體實驗過程如下：

步驟1 從圖文件讀取邊集E。

步驟2 將邊集劃分為訓練集ET和測試集EP。

步驟3 對訓練集ET運用ERA、AA、RA和CN算法算出各節(jié)點對的相似性分數(shù)。

步驟4 從不存在的邊的集合EN和測試集EP中各選出一條邊，并比較其相似性分數(shù)的大小，重復n次，根據(jù)式(5)計算AUC。

步驟5 重復執(zhí)行步驟2-步驟4，重復20次，并計算AUC的平均值。

2.2 實驗數(shù)據(jù)集

本實驗中使用的五種網(wǎng)絡(luò)分別為NS科學家合作網(wǎng)絡(luò)、PB美國政治博客網(wǎng)絡(luò)、美國航空路線圖USAir網(wǎng)絡(luò)、Yeast蛋白質(zhì)網(wǎng)絡(luò)和C.Elegans網(wǎng)絡(luò)。各網(wǎng)絡(luò)的主要參數(shù)如表1所示。其中：V表示節(jié)點數(shù)，E表示邊數(shù)，AD表示平均度，GD表示圖密度，ACC表示平均聚類系數(shù)。

表1 各數(shù)據(jù)集的網(wǎng)絡(luò)屬性

2.3 實驗結(jié)果分析

以AUC作為評價預(yù)測精度的指標，并以AA、RA和CN這三種基于局部相似性的鏈路預(yù)測算法作為基準進行比較，將改進后的ERA算法應(yīng)用于NS、PB、USAir、Yeast和C.Elegans五個網(wǎng)絡(luò)數(shù)據(jù)集中。實驗過程中，對測試集的比例劃分為1%、10%、20%、33%。隨著測試集比例的上升，預(yù)測精度出現(xiàn)了明顯的降低，故不再對高于40%的測試集進行測試。測試結(jié)果見圖1，柱狀圖的順序從左到右為ERA、AA、RA和CN。

(a) NS

(b) PB

(c) USAir

(d) Yeast

(e) C.Elegans圖1 不同數(shù)據(jù)集的中的AUC評估值

可以看出，ERA算法的整體預(yù)測精確度優(yōu)于AA、RA和CN算法。從表2可以看出，ERA在NS數(shù)據(jù)集上的平均預(yù)測精度相較于AA、RA和CN算法分別提升了0.07%、0.19%、0.48%；在PB數(shù)據(jù)集上分別提高了0.31%、0.13%、0.60%；在USAir數(shù)據(jù)集上分別提高了0.53%、0.06%、1.57%；在Yeast數(shù)據(jù)集上分別提高了0.07%、0.09%、0.07%；在C.Elegans數(shù)據(jù)集上分別提高了0.48%、-0.13%、2.75%。從表3可以看出，93.3%的ERA算法的預(yù)測精確度高于對比算法的預(yù)測精確度，個別預(yù)測精度沒有達到預(yù)期的情況，這種情況和所使用的數(shù)據(jù)集和抽樣的隨機性有一定關(guān)系。

表2 各數(shù)據(jù)集中平均AUC預(yù)測精度

表3 ERA在個數(shù)據(jù)集上的AUC改進度 %

3 結(jié) 語

本文針對鏈路預(yù)測中已有的Adamic-Adar和Resource-Allocation算法進行了改進，提出了一種新的算法。通過在真實網(wǎng)絡(luò)數(shù)據(jù)集上的實驗與AA、RA和CN算法進行了比較，結(jié)果表明在確保算法復雜度沒有發(fā)生變化的情況下，本文算法能提升鏈路預(yù)測的精確度。