一種基于節點局部相似性的復雜網絡鏈路預測算法

2020-05-16 06:46:50馬云龍張為子

計算機應用與軟件 2020年5期

白樺馬云龍畢玉張為子

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

0 引言

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

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

鏈路預測的通用框架是計算節點之間的相似性：如果兩個節點更相似，則它們將來更可能被連接。基于此假設，設未連接節點對(x,y)之間的相似性為Sxy，具有高相似性得分的Sxy尚未存在的節點對之間有高概率被鏈接起來。這些方法完全基于網絡的結構信息，可以分為三種類型：全局、局部和準局部。

本文主要針對基于局部相似性的方法展開。基于局部相似性的方法假設：如果節點對具有共同的鄰居結構或節點對中的某一節點已經具有更高的度，則它們可能形成鏈接。因為它們僅適用基于鄰居相關結構的局部拓撲信息而不是考慮整個網絡結構，所以它們比基于全局相似性的方法更快。許多研究表明在動態網絡上，它們的性能比起基于全局相似性的方法更加優越。它們被限制為僅計算節點對的所有可能組合的相似性，因為它們僅對距離為2的節點之間的相似性進行排序。

1 鏈路預測算法

1.1 CN指標

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

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

(1)

1.2 AA指標

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

(2)

1.3 RA指標

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

(3)

1.4 ERA指標

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

(4)

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

輸入：無向圖graph

輸出：圖graph中所有節點對之間的EAA相似性分數

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中元素個數>1

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

FOR j←0 TO m-2

FOR k←j+1 TO m-1

產生元組Tuple3

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

將該元組加入收集器Collector1

END FOR

END IF

END FOR

4. DataSet>tem←Collector1

5. 將數據集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

產生元組Tuple3，并加入收集器Collector2

END FOR

7. DataSet>result←Collector2

1.5 評價方法

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

(5)

2 實驗

2.1 實驗設置

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

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

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

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

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

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

2.2 實驗數據集

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

表1 各數據集的網絡屬性

2.3 實驗結果分析

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

(a) NS

(b) PB

(d) Yeast

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

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