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

白 樺 馬云龍 畢 玉 張為子

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

0 引 言

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

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

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

本文主要針對(duì)基于局部相似性的方法展開(kāi)。基于局部相似性的方法假設(shè)：如果節(jié)點(diǎn)對(duì)具有共同的鄰居結(jié)構(gòu)或節(jié)點(diǎn)對(duì)中的某一節(jié)點(diǎn)已經(jīng)具有更高的度，則它們可能形成鏈接。因?yàn)樗鼈儍H適用基于鄰居相關(guān)結(jié)構(gòu)的局部拓?fù)湫畔⒍皇强紤]整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)，所以它們比基于全局相似性的方法更快。許多研究表明在動(dòng)態(tài)網(wǎng)絡(luò)上，它們的性能比起基于全局相似性的方法更加優(yōu)越。它們被限制為僅計(jì)算節(jié)點(diǎn)對(duì)的所有可能組合的相似性，因?yàn)樗鼈儍H對(duì)距離為2的節(jié)點(diǎn)之間的相似性進(jìn)行排序。

1 鏈路預(yù)測(cè)算法

1.1 CN指標(biāo)

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

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

(1)

1.2 AA指標(biāo)

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

(2)

1.3 RA指標(biāo)

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

(3)

1.4 ERA指標(biāo)

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

(4)

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

輸入：無(wú)向圖graph

輸出：圖graph中所有節(jié)點(diǎn)對(duì)之間的EAA相似性分?jǐn)?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中元素個(gè)數(shù)>1

用數(shù)組list[m]按照target vertex id從小到大的順序存儲(chǔ)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按照f(shuō)irst 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中所有的元組的第三個(gè)域inverse of degree相加得到score

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

END FOR

7. DataSet>result←Collector2

1.5 評(píng)價(jià)方法

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

(5)

2 實(shí) 驗(yàn)

2.1 實(shí)驗(yàn)設(shè)置

在本文中使用AUC指標(biāo)來(lái)評(píng)價(jià)鏈路預(yù)測(cè)算法的表現(xiàn)，為了計(jì)算AUC，需要?jiǎng)澐钟?xùn)練集和測(cè)試集，在劃分訓(xùn)練集和測(cè)試集時(shí)為了避免隨機(jī)性對(duì)結(jié)果的干擾，將進(jìn)行多次劃分重復(fù)計(jì)算AUC。具體實(shí)驗(yàn)過(guò)程如下：

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

步驟2 將邊集劃分為訓(xùn)練集ET和測(cè)試集EP。

步驟3 對(duì)訓(xùn)練集ET運(yùn)用ERA、AA、RA和CN算法算出各節(jié)點(diǎn)對(duì)的相似性分?jǐn)?shù)。

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

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

2.2 實(shí)驗(yàn)數(shù)據(jù)集

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

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

2.3 實(shí)驗(yàn)結(jié)果分析

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

(a) NS

(b) PB

(c) USAir

(d) Yeast

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

可以看出，ERA算法的整體預(yù)測(cè)精確度優(yōu)于AA、RA和CN算法。從表2可以看出，ERA在NS數(shù)據(jù)集上的平均預(yù)測(cè)精度相較于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ù)測(cè)精確度高于對(duì)比算法的預(yù)測(cè)精確度，個(gè)別預(yù)測(cè)精度沒(méi)有達(dá)到預(yù)期的情況，這種情況和所使用的數(shù)據(jù)集和抽樣的隨機(jī)性有一定關(guān)系。

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

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

3 結(jié) 語(yǔ)

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