結合鄰居影響和資源分配的鏈路預測算法

劉英杰, 劉士虎, 高海燕, 徐偉華

(1.云南民族大學 數學與計算機科學學院 云南 昆明 650504; 2.西南大學 人工智能學院 重慶 400715)

0 引言

現實中的社交網絡[1]、生物網絡[2]和機會網絡[3]等復雜網絡不僅可以用來描述節點的屬性信息,還能用于刻畫節點之間的拓撲信息。因此,復雜網絡因其潛在的數據信息而引起各領域學者的廣泛關注。復雜網絡中的研究分支主要有鏈路預測[4]、社團檢測[5]和聚類分析[6]。其中,鏈路預測旨在探測節點之間存在連邊的可能性。因此,鏈路預測具有巨大的實際應用價值。例如,在電子商務網絡中使用鏈路預測技術為顧客推薦其喜愛的產品[7]。在犯罪網絡中使用鏈路預測技術揭示罪犯之間隱而未現的關聯關系,協助警方及時偵破案件[8]。

針對現有的鏈路預測問題,學者們主要采用基于節點相似性的算法來進行研究,這類算法主要分為基于局部結構的算法、基于路徑信息的算法和基于隨機游走的算法。

在基于局部結構的算法中,資源分配(resource allocation,RA)指標[9]和聚類系數(clustering coefficient for link prediction,CCLP)指標[10]分別在共同鄰居的基礎上考慮了共同鄰居的度和聚類系數的影響;局部社區范式(cannistraci-resource-allocation,CRA)指標[11]在共同鄰居的基礎上考慮了共同鄰居之間的連邊數的影響。在基于路徑信息的算法中,Katz指標[12]是基于兩個節點之間的全路徑信息的,局部路徑(local path,LP)指標[13]是基于兩個節點之間所有二階路徑與部分三階路徑信息的。在基于隨機游走的算法中,平均通勤時間(average commute time,ACT)指標[14]基于網絡中的全局隨機游走而被提出。

除了上述三類算法,研究者們也提出了一系列具有代表性的算法和指標。例如,偏好連接(preferential attachment,PA)指標[15]基于節點之間連邊生長的概率與節點度之積成正比的關系而被提出。矩陣森林(matrix-forest index,MFI)指標[16]利用矩陣森林理論來刻畫節點相似性而被提出。CCLP2指標[17]基于二級共同鄰居的聚類系數而被提出。此外,二級節點的度也被相關學者考慮在鏈路預測算法的設計中[18],但他們沒有在拓撲性質不同的網絡中對共同鄰居和二級節點的影響深入分析。

值得一提的是,現有的鏈路預測研究還源自于網絡演化中的資源傳輸過程[19-20]。其基本假設是兩個節點之間存在資源傳輸,則它們之間的關系是親密的,從而它們就更有可能相似。李英樂等[21]在RA指標的基礎上,利用共同鄰居周圍的三角結構來量化其分配給兩個節點的資源量,提出了拓撲緊密性(topological tightness,TT)指標。然而,TT指標只關注共同鄰居對資源的分配,卻忽略了二級節點在資源分配中的作用。

基于上述分析,為進一步探究共同鄰居和二級節點在鏈路預測過程中的影響,本文提出了一種結合鄰居影響和資源分配的鏈路預測算法。借助無向網絡中節點之間的雙向資源傳輸,該算法利用平衡系數來調節共同鄰居和二級節點分配給兩個節點的資源總量所占的比例,以探究二者在拓撲性質不同的網絡中對鏈路預測準確率的影響。實驗結果表明,在平均聚類系數高的網絡中,若兩個節點接收更多由共同鄰居分配的資源,則可以提升鏈路預測的準確率;在生態網絡和平均聚類系數低的網絡中,若兩個節點接收更多由二級節點分配的資源,則可以提升鏈路預測的準確率;此外,結合共同鄰居和二級節點的共同影響對鏈路預測算法準確率的提升將更有效。

1 預備知識

1.1 復雜網絡

形式上,無向復雜網絡可用一個二元組G=(V,E)來表示,V表示節點集合;E表示連接任意兩個節點的連邊集合,即E中包含了G=(V,E)中的實際存在的邊。在網絡G=(V,E)中,若其內部的任意一個節點都與其余的n-1個節點相連,則G=(V,E)中共有n·(n-1)/2條可能存在的邊,使用集合U來表示。于是,在G=(V,E)中的所有未知連邊可用集合U-E來表示。其中,未知連邊是指G=(V,E)中可能存在但尚未被探測的邊。

1.2 鏈路預測

在進行鏈路預測時,按照一定的比例b(0

基于以上敘述,鏈路預測問題可被描述如下:對于G=(V,E)中任意一條邊e,根據給定的鏈路預測算法為邊e賦予一個相似性分數,然后將G=(V,E)中的所有可能的邊都按照為它們賦予的分數進行降序排列,那么排名越靠前的連邊存在的可能性就越大。

2 資源分配驅動的鏈路預測

資源分配驅動的鏈路預測的基本原理是若兩個節點之間存在資源交互,則它們的關系較為親密,故它們更加相似,從而它們之間更有可能存在連邊。

在無向網絡中,節點之間的資源交互是指始發節點和終結節點可以相互向對方傳輸一定的資源。在這個過程中,始發節點與終結節點之間的逐階路徑上的中間節點便扮演著資源承載者的角色[21]。一般地,兩個節點之間的共同鄰居就是它們之間的二階路徑上的中間節點,兩個節點之間的二級節點就是它們之間的三階路徑上的中間節點。下面將分別介紹兩個節點之間傳輸的資源由共同鄰居和二級節點分配時的情況。

2.1 基于共同鄰居的資源分配

圖1分別給出了節點vx和vy之間傳輸的資源經由共同鄰居vz進行分配時的三種情況。圖1(a)表示節點vx發送的資源經由共同鄰居vz平均分配給節點vy的情況;圖1(b)表示節點vy發送的資源經由共同鄰居vz平均分配給節點vx的情況;圖1(c)表示共同鄰居vz自身具有的資源被平均分配給節點vx和vy的情況。在最簡單的情況下,假設節點vx和vy均向對方發送一個單位的資源被共同鄰居vz分配,而共同鄰居vz的聚類系數ccz被假設為它自身影響兩個節點的相似性時所具有的資源量[19-20]。因此,圖1中節點vx和vy在經過了雙向的資源傳輸后能夠接收1/kz+1/kz+ccz/kz=0.2+0.2+0.04=0.44單位的資源總量,其中kz為節點vz的度。

圖1 資源由共同鄰居分配Figure 1 Resource allocated by common neighbor

2.2 基于二級節點的資源分配

圖2給出了節點vx和vy進行資源傳輸的過程中,資源在經由二級節點vz2被分配到節點vx和vy時的三種情況。圖2(a)表示節點vx發送的資源經由二級節點vz2平均分配給節點vy的情況;圖2(b)表示節點vy發送的資源經由二級節點vz2平均分配給節點vx的情況;圖2(c)表示二級節點vz2自身所具有的資源被分配給節點vx和vy的情況。同樣地,假設節點vx和vy向對方發送一個單位的資源被二級節點vz2分配,而二級節點vz2的聚類系數ccz2被假設為它自身影響節點vx和vy的相似性時所具有的資源量。

圖2 資源由二級節點分配Figure 2 Resource allocated by second-level node

不難發現,節點之間的資源由二級節點進行分配后也會經過它們的共同鄰居,但探究共同鄰居和二級節點在預測過程中的影響時需要控制單一變量,故對由二級節點分配給兩個節點的資源會不會因為共同鄰居的影響而被稀釋掉的問題,將在后續的工作中進一步討論。本次研究在考慮資源由二級節點進行分配時,不再考慮共同鄰居對資源分配的影響。以圖2為例,節點vx和vy經過二級節點進行資源的雙向傳輸后能接收1/kz2+1/kz2+ccz2/kz2≈0.25+0.25+0.042=0.542單位的資源總量。

2.3 鄰居影響下的資源分配鏈路預測指標

本研究利用共同鄰居和二級節點分配給兩個節點的資源總量來探究它們在鏈路預測中的影響,并提出了一種結合鄰居影響和資源分配(neighbor influence and resource allocation,NIRA)的鏈路預測指標。因此,考慮無向網絡G=(V,E)中的任意兩個節點vx和vy,vz和vz2分別是它們的共同鄰居和二級節點,則NIRA的計算表達式可定義為

其中:N(vx)∩N(vy)和SN(vx,vy)分別表示vx和vy的共同鄰居集合和二級節點集合,且SN(vx,vy)=[N(N(vx))∩N(vy)]‖[N(vx)∩N(N(vy))],不包括vx和vy的共同鄰居;λ∈[0,1]是一個平衡系數,用于調節由共同鄰居和二級節點分配給兩個節點的資源比例。當λ=0時,資源只由二級節點分配給兩個節點;當λ=1時,資源只由共同鄰居分配給兩個節點;當λ∈(0,1)時,資源由共同鄰居和二級節點一起分配給兩個節點。

3 實驗設置

本文的實驗環境為16 GB內存,1.8 GHz速度,Windows 10操作系統和AMD Ryzen 7 4800U處理器,編程語言為MATLAB 2020a。

本文使用CCLP指標、CCLP2指標、RA指標、CRA指標、PA指標、LP指標、Katz指標、MFI指標和ACT指標作為實驗的基準指標,為適用本文中的二級節點集合,CCLP2指標的計算公式也被進行了相應的擴展。下面介紹本文使用的網絡數據和評價指標。

3.1 網絡數據

本文從公開的網絡數據的學術網站上(http:∥konect.cc/networks/)收集了16個網絡數據,這些網絡的簡稱分別為LESM網絡、 USAI網絡、NSSM網絡、KING網絡、STMA網絡、FWEW網絡、FWMW網絡、FWFW網絡、ADJN網絡、FORU網絡、EMAI網絡、UCSO網絡、KARA網絡、POLB網絡、FOOT網絡和COMM網絡,它們的拓撲性質被列在了表1中,其中:n為節點數;m為邊數;d為網絡直徑;ρ為網絡密度;〈k〉為平均度;〈c〉為平均聚類系數。

表1 網絡的拓撲性質Table 1 Topological properties of networks

3.2 評價指標

本文使用受試者工作特征曲線下的面積(area under curve,AUC)值和精確度(Precision)進行評價,它們的定義分別如下。

AUC值為隨機地從測試集中選擇一條邊的相似性分數比從不存在邊集中選擇一條邊的相似性分數更高的概率。若在t次的分數比較中,有t1次是測試邊的分數大于不存在邊的分數,有t2次是二者分數相等,則AUC的值被定義為

其中:t被設置為10 000,衡量算法的性能。

Precision為排名靠前的邊被準確預測的比例,即在排名前L的邊中,若有l條邊是測試集中的邊,則Precision計算為

Precision=l/L,

其中:L被設置為100,衡量算法的性能。

4 算法驗證及結果分析

為探究NIRA指標的預測性能以及適用范圍,本文分析了NIRA指標與基準指標在多個網絡中的AUC值和Precision值。下面先分析NIRA指標的可行性。

4.1 可行性分析

圖3為NIRA指標在16個網絡中隨著平衡系數λ的變化而生成的AUC曲線和Precision曲線。由圖3(a)可知NIRA指標的AUC曲線具有以下兩個特點。

當λ∈(0,1)時,NIRA指標的AUC值在所有網絡中都達到了一個峰值點。這表明當共同鄰居和二級節點一起分配資源給兩端節點時,NIRA指標可以取得最優AUC值。在共同鄰居和二級節點的共同影響下,NIRA指標的AUC值達到了最優。

NIRA指標的AUC曲線在λ=0和λ=1處存在著較大的差異,在拓撲性質不同的網絡中表現得更明顯。如在LESM、USAI、NSSM和KING中,NIRA指標在λ=1時的AUC值遠遠大于其在λ=0時的AUC值,而在ADJN、FORU、EMAI、UCSO、STMA、FWEW和FWFW中,又呈現出相反的情況。這表明,在平均聚類系數較高的網絡中,共同鄰居對NIRA指標的AUC影響大于二級節點;然而二級節點在平均聚類系數較低的網絡和部分生態網絡中對NIRA指標的AUC影響大于共同鄰居。此外,在FWMW、POLB、FOOT和COMM等網絡中,共同鄰居的影響在提升NIRA指標的AUC上比二級節點更加具有優勢。

由圖3(b)可看出NIRA指標的Precision曲線與其AUC曲線具有相同的變化趨勢。即在LESM、USAI、NSSM、KING這4個平均聚類系數較高的網絡和POLB、FOOT、COMM等網絡中,共同鄰居對NIRA指標的Precision的影響大于二級節點;在STMA、FWEW、FWMW、FWFW這4個生態網絡和ADJN、FORU、UCSO等三個平均聚類系數較低的網絡中,二級節點對NIRA指標的Precision的影響更大。然而,在EMAI網絡中,共同鄰居對NIRA指標的Precision的提升更有優勢。此外,NIRA指標在NSSM、KING和FOOT網絡中的最優Precision值均在λ=1處。因此,在這三個網絡中,共同鄰居對相應算法的Precision的提升更有優勢。這表明,在多數網絡中考慮共同鄰居的影響來提升算法的Precision是可行的。上述的實驗結果表明,從資源分配的角度描述

圖3 NIRA指標在平衡系數λ影響下的AUC和Precision曲線Figure 3 The AUC and Precision curves of NIRA index with the influence of balance parameter λ

共同鄰居和二級節點在鏈路預測中的影響是可行的。

4.2 有效性分析

表2和表3為NIRA指標與基準指標之間的AUC值和Precision值,表中每一行的加粗數字為在該網絡中最高值。

表2 NIRA指標與9個基準指標之間的AUC值比較Table 2 Comparison of the AUC values between the NIRA index and nine benchmark indices

由表2中的結果可知,CCLP指標和CCLP2指標在拓撲性質不同的網絡中的預測性能表現出較大的差異。在LESM、USAI、NSSM和KING網絡中,CCLP指標比CCLP2指標的AUC值提升了7.47%～29.6%;然而在STMA、FWEW、FWFW、ADJN、FORU、EMAI和UCSO等網絡中,CCLP2指標比CCLP指標的AUC值提升了2.84%～17.44%。

從CCLP指標和CCLP2指標的AUC值可以看出,僅考慮了共同鄰居或二級節點的單一影響難以使得相應的算法在拓撲性質不同的網絡中展現出較好的性能。結合了兩類鄰居共同影響的NIRA指標不僅實現了普適性,在準確率方面也有大幅度提升。此外,相比RA指標和CRA指標,NIRA指標在較多的網絡中取得了最高AUC值,這表明考慮資源的雙向傳輸是更有效的。PA指標在四個生態網絡中表現良好,但在其余網絡中均不如NIRA指標。LP、Katz、MFI、ACT等指標的預測效果相對較好,但除了FOOT網絡中的MFI指標,其余三個指標在剩下的15個網絡中的AUC值均不如NIRA指標。

表3 NIRA指標與9個基準指標之間的Precision值比較Table 3 Comparison of the Precision values between the NIRA index and nine benchmark indices

由表3可知CCLP指標和CCLP2指標的Precision值與它們的AUC值具有相同現象。由此可見,僅考慮共同鄰居或二級節點的單一影響的確難以保證算法的普適性。值得一提的是,考慮共同鄰居影響的算法似乎更適合用Precision來評價,如RA指標在NSSM和POLB網絡中取得了最優Precision值,而CRA指標在EMAI和FOOT網絡中也取得了最優的Precision值。在大多數網絡中,CCLP、RA和CRA指標相比PA、LP、Katz、MFI和ACT等也都取得了更高的Precision值。

4.3 復雜度分析

在本文中,利用算法在各個網絡中運行時消耗的時間來分析它們的時間復雜度。為此,本文將算法a在網絡b中運行時所消耗的時間歸一化到區間[0, 1]來進行更為直觀的分析。此外,考慮基于局部結構的鏈路預測算法具有較低的復雜度,本文只在節點數大于800的網絡上分析Katz指標、MFI指標、ACT指標、NIRA指標和CCLP2指標的時間復雜度。

表4給出了Katz、MFI、ACT、NIRA和CCLP2等五個指標在KING、FORU、EMAI和UCSO網絡中的歸一化時間消耗。從表4中的結果可以看出,NIRA指標相比于CCLP2指標在運行時間上也具有一定的優勢,但相比其余三個基準指標,NIRA指標卻是在犧牲了一定的計算時間后換來性能上的提升。這是因為在構造NIRA指標和CCLP2指標的過程中,需要先找出兩個節點之間的二級節點集合,而這一步驟需要在MATLAB編程軟件中利用兩個for循環來完成,故NIRA指標和CCLP2指標的運行時間增加了。

表4 五個指標的歸一化時間消耗Table 4 Normalized time consumption of five indices 單位:s

5 結論

為了探究共同鄰居和二級節點在鏈路預測中的影響,本文借助節點之間的雙向資源傳輸,通過利用兩個節點接收由它們的共同鄰居和二級節點分配給它們的資源總量來度量它們的相似性。實驗結果表明,在平均聚類系數較高的網絡中,兩個節點接收更多由共同鄰居分配給它們的資源時,鏈路預測效果更佳;在平均聚類系數較低的網絡和生態網絡中,兩個節點接收更多由二級節點分配給它們的資源,鏈路預測效果更佳;在拓撲性質不同的多個網絡中,結合兩類鄰居的共同影響而提出的算法不僅具有較高的預測準確率,還實現了良好的普適性。

本文在后續的研究中將探究共同鄰居和二級節點之間的其余子節點對于提升鏈路預測算法性能的影響,從而進一步優化本文所提出的預測模型。