一種基于密度峰值聚類的鏈路預測算法

邵 豪，王倫文，鄧 健

1(國防科技大學 電子對抗學院，合肥 230031)

2(陸軍工程大學 石家莊校區二系，石家莊 050003)

E-mail：shaohao64@outlook.com

1 引 言

隨著復雜網絡理論的迅速發展，網絡在社交、軍事、信息等領域得到廣泛應用[1].獲取完整的網絡拓撲結構是分析、控制網絡的基礎[2]，但條件的局限會導致網絡重構不完整.鏈路預測不但預測網絡中的丟失鏈接，而且也可預測演進網絡中可能出現的未來鏈路.社交網絡中，推薦尚未存在的鏈接作為潛在的友誼關系，可以幫助用戶尋找新朋友[3].戰場通信網中，鏈路預測作為網絡拓撲偵察的補充，預測敵方通信網絡還未偵察到的鏈接，以及敵方通信節點間的隱藏鏈接，為網絡對抗提供條件[4].

最常用的鏈路預測算法是衡量兩節點的相似性，相似性更高的節點間更可能存在鏈接[5].相似性指標作為衡量節點相似的標準，不同指標直接影響鏈路預測的精度.分析節點外部屬性已被廣泛使用且有較高的預測精度[6]，但實際中，節點的屬性信息通常是難以獲取的.例如，社交網絡中用戶的個人信息受到隱私保護；戰場通信網中，敵方節點信息是加密的[7].考慮到網絡結構信息更容易獲得，近年來，基于網絡結構的鏈路預測方法逐漸成為研究的熱點，劉大偉等人[8]提出局部差異融合算法，共同考慮節點共同鄰居集合的相似性與差異性以提高預測精度；許忠齊等人[9]提出加權路徑熵(WPE)，比較路徑熵對預測精度的貢獻；此外，姚亞兵等人[10]提出利用“層相關性”來對多層網絡進行鏈路預測.

上述算法都提出了一個改進的相似性指標來預測鏈路，在特定網絡中有較好的預測性能.事實上，不同網絡具有截然不同的結構特征，甚至同一網絡不同部位的結構也是明顯不同的[11].因此，單個相似性指標不可能在所有網絡中都有很好的預測性能.Ma C[12]提出一種結合多種結構指標的方法，首先定義一個包含多個結構指標的函數，然后利用已知結構信息來確定函數中每個特征的權重.在本文中，我們提出一種自適應融合多個相似性指標的鏈接預測算法，利用無監督機器學習對未知鏈路進行分類，依據分類結果完成鏈路預測.實驗結果表明，在不同網絡中，本文提出的自適應鏈路預測算法普遍具有良好的預測性能.

2 相關知識

2.1 網絡定義

無向網絡G(N，E)，N是節點集，E是鏈路集.若節點i、j之間存在鏈接，則aij=1；反之aij=0.Γ(i)表示節點i的鄰居節點集合，ki表示節點i的度.

聚類系數ci表示節點i的鄰居節點間連接的緊密度[13]，其定義為某節點所有鄰居節點間的鏈接數目與可能產生的最大鏈接數目之比.

(1)

其中，li表示ki個鄰居節點間存在的鏈路數目.當ci=1時，節點i所有鄰居節點兩兩鏈接.

2.2 密度峰值聚類

①密度大，即被不超過其密度的節點包圍；

②與其它更高密度的節點間有更大的距離.

本文使用密度峰值聚類對節點間的未知鏈路進行分類，主要考慮以下幾方面：

①不同網絡的結構差別很大，未知鏈路的屬性分布不是凸 型的.與層次聚類和劃分式聚類不同，密度聚類可以發現各種形狀和各種大小的簇[15].

②傳統密度聚類DBSCAN算法的性能對于半徑、閾值這兩個初始參數敏感，且難以發現不同密度的簇；OPTICS算法在可視化圖中尋找“山谷”來確定簇，處理方式復雜，運算速度慢.考慮不同網絡的結構，很難有一個固定的合適參數.

③密度峰值聚類算法基于相對距離和相對密度來分析數據點，能夠分類不同密度的簇，且時間復雜度比其他密度聚類算法更低，針對不同結構的網絡更具適用性.

密度峰值聚類中，如果一個簇密度分布均勻或有多個高密度點，可能會把某些簇分成幾個子簇.本文鏈路預測算法中，分類結果為有鏈接、無鏈接兩類，因此即使發生簇過分類，通過對比簇中心節點的相似性指標，進行簇合并，得到正確的聚類個數，避開了密度峰值聚類可能產生的過分類的缺陷.

3 鏈路預測算法與實現

3.1 鏈路預測問題描述

U表示一個無權向網絡G(N，E)中包含所有可能鏈接的集合，即|U|=[|N|·(|N|-1)]/2.網絡中未知鏈接的集合(存在但未被發現的鏈接)是V，已被發現的鏈路集是U-V，鏈接預測的任務就是找出未知鏈接.傳統的鏈路預測算法，通過計算出節點間的相似指標值sij，將所有未知鏈接以值從大到小排列.sij越高，兩節點間存在鏈接的可能性也越大.一些基于鄰居節點的局部相似性指標[16]如表1所示.

表1 部分基于鄰居節點的局部相似性指標

表1中，CN認為節點間存在鏈接的概率隨著其二階路徑的個數增加而增加，JC、AA、RA在不同方面改進CN指標.JC認為應該考慮二階路徑個數的比例，AA、RA認為即使是相同個數的鄰居點，不同鄰居節點會存在不同貢獻度，即不同的二階路徑擁有不同的貢獻度，通過懲罰度更大的鄰居節點來區分相同的二階路徑.

除上述指標外，本文還考慮局部隨機游走的相似性指標LRW[5].定義πxy是一個隨機游走粒子t時刻在節點x處，t+1到節點y處的概率，得

πx(t+1)=PTπx(t)t≥0

(2)

其中，πx(0)是第x個元素值為1，其余值為0的向量，P是馬爾可夫概率轉移矩陣.網絡節點最初資源分布為qx，則LRW指標可表示為：

sij(t)=qx·πxy(t)+qy·πyx(t)

(3)

本文認為網絡節點最初的資源分布是平均的，即qx=kx/|E|.最終：

(4)

本節介紹了鏈路預測的目的，以及部分節點相似性指標，分別是基于鄰居節點相似性和局部隨機游走.雖然這兩個指標在特定網絡中有較好的性能，但由于網絡的多樣性，單個相似性指標不可能在結構不同的網絡中都有很好的預測精度.因此，將上述介紹到的相似性指標作為節點對的某一維度的參數綜合考慮.除上文介紹到的相似性指標之外，本文還提出改進的路徑相似性指標進行預測.

3.2 改進的路徑局部相似性指標PLD和INR

全路徑相似性指標Katz分析網絡中節點間所有路徑的數量，預測精度較高，但因需要網絡全路徑信息，時間復雜度很高[7].局部路徑指標LP考慮有限長度的路徑，綜合預測精度和時間復雜度，但其只分析中間節點的鄰居數量，未完全挖掘路徑結構信息[8].為此，本文提出兩個改進的路徑局部相似性指標PLD(Path Link Degree)及INR(Intermediate Node Ring)，分別考慮路徑中間鏈接及中間節點連通性對預測的貢獻，相比傳統局部路徑預測指標，考慮了更多的路徑信息，提升了預測精度.

3.2.1 PLD指標

網絡G(N，E)中，若某條鏈路exy存在，定義鏈接exy的度為：

kexy=kx·ky

(5)

其中，kx、ky表示為鏈接exy兩端節點x、y的度.文獻[17]表明，節點度與鏈路預測精度成反比關系.即已存在的鏈接會對相應的節點對的鏈路預測成功率產生影響.因此首先定義 SLD(Single Link Degree)指標衡量一條鏈路對預測精度的貢獻：

SLD=(kexy)-θ=(kx·ky)-θ

(6)

其中，θ是一個固定的參數.本文中θ=1，即LD=(keij)-1=(ki·kj)-1.由此定義了一條鏈路對于鏈路預測的貢獻.

(7)

式(7)可看出，一條路徑的SPLD指標值等于該條路徑中每條鏈路的SLD指標值之和.遍歷節點i、j間的所有路徑，最終PLD指標定義如下：

(8)

(9)

3.2.2 INR指標

(10)

(11)

3.3 鏈路預測算法與實現

3.3.1 算法思想與指標篩選

前文介紹，通過單個相似性指標得到的網絡預測性能與網絡結構直接相關.針對于同一網絡，不同相似性指標基于不同的角度，會得到不同預測結果，存在相應交集.文獻[12]指出，不同指標得到的預測性能是無法通過簡單的合并或求交集來提升的.例如，圖1中左右兩個圓分別表示CN，JC兩個指標在Hep-ph網絡上的預測結果的集合[12].表2表示這兩指標預測準確率及并集、交集后的準確率.

圖1 CN，JC指標預測結果集合

表2可得，預測準確率、并集準確率、交集準確率無直接關系.隨意將不同相似性指標的預測結果求并集，會大大增加虛警率(將沒有鏈接的節點對誤判為有鏈接)；將不同相似性指標的預測結果求交集，會大大增加漏警率(忽略有鏈接的節點).

表2 CN、JC指標預測并集、交集準確率

與單純的并集或交集不同，本文提出一種利用無監督機器學習的鏈路預測算法，將不同的相似性指標作為節點的多維參數，利用密度峰值聚類，綜合各指標對節點進行分類.以下討論選取哪些相似性指標作為節點的聚類參數，統籌效率與預測精度.

本文算法中，考慮到聚類分類精度，盡可能使用相對獨立的指標作為各維參數.本文使用JC，RA，LRW，PLD，INR這5個指標作為節點間的聚類參數，主要考慮以下幾方面：

①所有指標都只考慮局部相似性特征，全局特征會增加復雜度，且預測性能提升有限，不適用于大規模網絡.

②JC、RA基于節點局部相似性，特別是兩端節點的鄰居節點性質；LRW基于隨機游走模型； PLD、INR分別考慮到節點對之間路徑與節點信息.這5個參數盡可能包含節點多的信息.

③JC是CN指標的改進，RA和AA都以共同鄰居的度作為懲罰指標，因此二選其一，避免指標重復.

3.3.2 聚類結果屬性判定

本文聚類結果應分為有鏈接或無鏈接，其有無鏈接的屬性判定遵循以下兩個標準：聚類結果包含的對象數目以及聚類結果中的特殊鏈路.以下進行具體分析：

① 網絡中的節點普遍只與部分鄰居節點相連，即|E|?[|N|·(|N|-1)]/2，網絡中存在鏈接的節點對數目遠小于節點對總數.更重要的是，在鏈路預測的仿真與實際應用中，大部分鏈路已知，未知鏈路只占所有鏈路的小部分.因此聚類后，兩節點間存在鏈接的分類包含的對象數目應遠小于不存在鏈接的數目.例如，若聚類后兩類中對象數目分別占總數的5%與95%，則將5%的分類作為有鏈接的分類.

② 對于兩個節點，指標值sij越大，則鏈接存在的可能性越高.如果這兩節點的所有指標值都很高，則可以認為鏈路是存在的，其所在聚類結果的屬性也可以確定.

綜上所述，在本文算法中，將聚類中對象數目少、存在所有指標值都很高的對象的分類判定為鏈路存在.

3.3.3 算法步驟

本文提出的基于密度峰值聚類算法步驟如下：

輸入：無權向網絡G(N，E)，所有未知鏈路集合V(集合元素vij表示節點i、j組成的節點對).

輸出：未鏈接節點對是否存在鏈路.

1.fori=1to|N|forj=1to|N|；

3.form=1to|V|forn=1to|V|；

5.按照聚類結果，確定被分類為有鏈接的節點對并輸出.

4 實驗分析

4.1 實驗數據與流程

為分析本文算法的性能，本文使用6種網絡結構進行實驗分析，分別是美國航空網絡US Air(機場間的航線信息)，海豚網絡Dolphins(海豚間的親密關系)，政治博客網絡Political Blogs(博客頁面間的鏈接)，鐵線蟲神經網絡Celegans(鐵線蟲神經突觸)，爵士樂Jazz網絡(音樂家的合作關系)，科學家網絡NS(科學家的合作關系).網絡數據來源：http://konect.uni-koblenz.de/networks/；http://www-personal.umich.edu/～mejn/netdata/；http://networkrepository.com/networks.php.網絡參數如表3所示.

在實驗中，為測試算法性能，將網絡G(N，E)中的鏈接分為兩部分：訓練集ET和測試集EP.ET∪EP=E，ET∩EP=?.首先，有權向的網絡改為無權向，將6個網絡中部分鏈接劃分為ET，其余作為EP.隨后，分別計算6個網絡U-ET中所有未知鏈路CN、JC、RA、AA、LRW、PLD、INR指數，得 到各指標的相似性值；再以JC、RA、LRW、PLD、INR指數作為未知鏈路的多維參數，標準化與歸一化后，使用本文提出的基于密度峰值聚類的預測算法，對未知鏈路進行無監督分類，得到所有節點對的連接情況.有鏈接的節點間相似性指標值sij為1，反之為0.

表3 網絡參數性質

AUC是一種廣泛使用的鏈路預測算法評價標準[18].AUC表示從測試集EP中隨機選擇一條鏈路的相似性指標值sij比從預測節點對集合U-E中隨機選擇一條鏈路的sij值高的概率，即：

(12)

其中，n是隨機選擇的次數n′是測試集sij值大于U-E集合的次數，n″是值相等的次數.本文算法最終得到聚類結果，sij是定性的二進制值(0、1)，因此本文算法的AUC可等效為未知鏈路集合U-E的預測準確率，即：

(13)

4.2 實驗結果

4.2.1λ對PLD、INR指標的影響

本文提出兩種路徑相似性指標PLD和INR.3.2節已介紹二階路徑信息對預測貢獻度大于三階路徑，故λ∈(0，1).λ值直接影響PLD和INR的預測準確率.為確定合適的λ值，在(0，1)范圍內，以0.1作為步長，選取不同λ值，以PLD和INR指標進行預測，并計算相應預測評價標準AUC.

圖2 各網絡中λ對PLD、INR指標的影響

圖2表示PLD、INR指標在各網絡中的預測性能，AUC值越高，預測準確率更高.λ=0時，只考慮網絡的二階路徑信息.隨著λ增大，網絡的三階路徑信息在指標中的地位越發重要，直至λ=1時，地位與二階相同.在λ增大的初始階段，PLD、INR指標的AUC在不同網絡中都上升，說明與僅使用二階路徑信息相比，適當考慮三階路徑信息是有必要的，能夠提升預測準確率.但隨著λ繼續上升.US Air、Dolphins、PB、Celegans、NS網絡的預測性能都發生不同程度下降，這是因為這些網絡平均密度較低，網絡稀疏，三階路徑信息成為了預測的噪聲信息.而在NS網絡中，高密度意味著節點間的聯系緊密，兩節點間三階路徑較為普遍，因此三階路徑信息有利于提高預測準確率.

理論上，短路徑對預測的貢獻高于長路徑，λ在[0，1]的范圍內，預測性能有一個高點，考慮到各網絡結構不同，最優λ不同.根據圖2，取λ=0.2作為式(9)、式(11)的三階路徑信息權重，此時在不同網絡中，PLD、INR指標都能有較好的預測結果.

4.2.2 算法性能對比

將網絡中90%的鏈路作為訓練集ET，其余10%作為測試集EP.按照4.1節介紹的實驗流程，得到各算法的預測結果，并計算相應AUC值，以衡量本文算法的預測性能，具體AUC值如表4所示.

表4 各預測算法在不同網絡上的AUC值(90%訓練集)

表4表示訓練集比例為90%時，不同算法的預測精度.一方面，本文提出的改進路徑局部指標PLD和INR，與傳統局部路徑指標LP相比，預測準確率分別提高1.2%、1.0%，這說明PLD、INR指標通過考慮路徑中間鏈接及中間節點連通性對預測的貢獻，克服傳統LP指標只考慮中間節點的鄰居數量，未能完全挖掘路徑信息的缺陷，有效提高了預測的精度.另一方面，與傳統的鏈路預測算法相比，本文提出的基于密度峰值聚類的預測算法的精度在各網絡中都有提高.較節點局部相似性CN、JC、RA、AA算法，本文算法分別提高3.7%、3.5%、1.7%、2.1%；較隨機游走模型LRW算法提高3.0%，較路徑相似性LP、PLD、INR算法分別提高2.2%、1.0%、1.1%.本文算法在各網絡中都能達到最佳的鏈路預測性能，說明利用密度峰值聚類的算法，融合考慮不同節點相似性指標，在預測時獲得更加全面的網絡結構信息，從而有效地提高了預測精度.

為綜合衡量算法性能，將訓練集ET的比例由90%改為80%，重新進行上述實驗流程，得到各預測算法的AUC值，如表5所示.為詳細比較各預測算法在不同比例訓練集時的差別，將表4與表5中各AUC值相減，得到不同訓練集比例時各預測算法精度的差值，如圖3所示.

表5 預測算法在不同網絡上的AUC值(80%訓練集)

表5表示80%訓練集時，各算法在不同網絡下的預測精度AUC.當訓練集從90%減少到80%時，所有預測算法的AUC都降低，這是因為訓練集比例減小，導致預測時獲取網絡信息減少.例如CN算法中，訓練集中鄰居節點的減少，致使共同鄰居數目減少，預測精度降低.對比而言，無論訓練集比例是80%還是90%，本文算法都有很好的預測精度.

圖3 各算法在90%與80%訓練集的AUC差值

圖3表示各算法在訓練集分別為90%與80%比例時AUC差值，數值越小，說明在訓練集減少的情況下，預測性能降低越小.橫向來看，在Jazz網絡中，所有算法AUC都下降最小，這是因為Jazz網絡擁有較高的網絡密度，在80%訓練集的情況下，節點間能夠有較好的連通性，預測時存在更多的鏈路信息.縱向來看， CN、JC、RA、AA算法都下降幅度明顯，說明訓練集減少對節點鄰居的相似性指標影響較大，基于路徑的PLD、INR算法較隨機游走LRW算法受訓練集減少影響較少.基于密度峰值聚類的算法與其他所有算法相比，在各個網絡中AUC差值最小，說明本文算法在訓練集降低的情況下，預測性能下降很小，更能適應復雜環境.

5 總 結

由于鏈路預測不同指標具有互補性，不同的相似性指標綜合可以有效地提高鏈路預測的精度.為此，本文提出一種基于無監督機器學習的鏈路預測算法，給出兩種改進的路徑相似性指標以提升預測性能，并將這兩指標與節點鄰居局部相似性指標、隨機游走指標作為未知鏈路的不同維度信息，然后使用密度峰值聚類對所有未知鏈路進行無監督學習，進行每條未知鏈路的鏈路預測.仿真實驗表明，相較傳統預測指標，本文算法在不同的網絡中都具有很高的識別精度，證明了算法的有效性.在訓練樣本占總樣本比例較小的情況下依然能夠得到較高的預測精度.本文的主要貢獻是將無監督的機器學習引入到了鏈路預測中，下一步，將考慮引進其他相似性指標進一步提高鏈路預測精度.