基于共同鄰居懲罰的復雜網絡鏈路預測方法

鄔劍升，李玉珩

(1.浙江中煙工業有限責任公司，浙江 寧波 315504; 2.秦皇島煙草機械有限責任公司，河北 秦皇島 066004)

0 引言

隨著社會網絡中信息量的迅速擴大，鏈路預測已成為推薦系統、決策和刑事偵查等領域的重要而問題[1]。鏈路預測涉及計算網絡中節點間丟失或未來鏈路的可能性[2-3]。為精確定義鏈路預測問題，假設復雜網絡為無向圖G=(V,E)，其中V為一組節點，E表示節點對間的邊。考慮到在時間t處的網絡G的快照，鏈路預測問題涉及在時間t+Δ處形成的當前快照中定義丟失的子集[4]。

現有的復雜網絡鏈路預測問題面臨兩大挑戰：第一類是海量數據，需要低復雜度的預測方法；第二個挑戰是預測方法涉及高預測精度。而傳統的數據挖掘方法忽略了實體間關系，無法有效地解決鏈路預測問題?，F有研究采用不同方法來處理鏈路預測問題，其中多數基于節點間的相似性實現計算[6]。在相似性計算技術中，相似節點間更容易形成鏈接。此外，有一些鏈路預測方法考慮了共享更多鄰居的節點[7]。

在上述方法中，為給網絡中的每對節點分配相似性分數，首先定義函數s(x,y)，基于不同特征(如拓撲特征和在相似度評分)將網絡中的所有節點對按其得分的降序排列，并在丟失的鏈路列表中選擇具有最高等級的鏈路作為可預見鏈路?；谙嗨贫鹊逆溌奉A測方法根據計算相似度函數時所考慮的信息量可分為局部、全局和準局部三類[8]。在局部技術中，更多關注直接的鄰居節點信息，常適用于大型復雜網絡，與線性時間復雜度相比具有較高精度。利用整個網絡拓撲結構的全局技術能夠計算每對節點間的相似度，而不局限于節點共鄰。而與局部方法相比，全局方法由于對噪聲的敏感性和較高的計算復雜度具有較低精度。而準局部技術尋求利用局部和全局技術點，通過考慮鄰節點的鄰節點而不僅僅是直接鄰節點，并限制每對節點間的距離。

上述方法均可在考慮信息量和計算復雜度間找到平衡。鏈路預測范圍有兩個主要問題。第一個是引入一種低計算復雜度的鏈路預測方法，特別是在面對大規模數據集時；第二個是預測精度，故需高精度的鏈路預測方法。而鏈路預測的兩個主要挑戰是時間復雜度和準確性。由于傳統的鏈路預測方法不能有效地解決這一問題，還沒有一種既能獲得低復雜度又能獲得高準確度的方法被提出。本文提出了基于公共鄰域懲罰的相似度鏈路預測方法(similarity link prediction method for common neighborhood punishment, SLP-CNP)，根據網絡拓撲特征(包括每兩個節點的公共鄰域)和平均聚類系數確定相似度，與其它同類算法的主要區別在于區分節點的公共鄰域，是一種同時兼顧局部和全局特征的準局部相似方法。實驗結果表明，該方法在精度和計算復雜度方面優于同類方法。

1 相關工作

鏈路預測在鏈路分析、信息檢索和網絡演化等領域變得越來越重要。在社交網絡中，鏈路預測常被用于預測潛在的社交關系，并基于此為用戶推薦好友或信息。最經典的相似度鏈路預測方法為公共鄰居(CN)[9]、Adamaic Adar(AA)[10]和資源分配(RA)[11]。公共鄰居對每對節點給出的相似度得分涉及到這些節點間共享鄰居的數量，且假設如兩個節點有多個共鄰，則其間形成邊的概率將增加。Adamaic Adar法根據其程度對每個共享鄰居進行分組，并通過研究每個節點間的公共鄰居為節點分配相似性分數。資源分配法考慮了兩個非連接節點間通過其鄰居的資源分配，使得每個鄰居節點接收到一些資源并在其鄰居之間平均分配。兩個節點間的相似性準則可通過共享鄰居從一個節點從另一節點接收到的資源量表示。而Jaccard指數[12]、S0rensen指數[13]和Leicht-Holme-Newman指數[8]是鏈接預測中采用的其他基于相似性的度量。在鏈路預測范圍內，有幾種基于相似度的方法，其中兩個節點間的鏈路概率是根據其共享鄰居來確定。劉留等[14]提出了基于公共鄰居的動態社會網絡鏈路預測算法，使用3個特定度量為兩個節點間的所有邊分配權值，然后將其總和確定為所述節點間鏈接的概率。而Wu等[15]提出了節點耦合聚類系數，將節點間的公共鄰域部分與聚類信息相結合，采用每個節點相同的公共鄰域聚類系數。Dong等[16]建立了結合鄰居和群體信息的復雜網絡鏈路預測模型，其考慮了稱為基序的網絡結構單元，為確定每個公共鄰域的兩個節點間的相似度得分，將所有公共鄰域的結果匯總，并將結果劃分為這些公共鄰域的個數，最終實現對節點進行相似度評分。

而翟東升等[17]提出了合著網絡中鏈接預測概念和基于主題建模的鏈接預測算法，證明了經典轉移相似度區間的范圍，用模糊系統理論來表示相似度。復雜網絡圖中頂點的兩階段選擇鏈接預測方法[18]，旨在預測圖流中最有可能連接到目標頂點的top-k頂點。黃璐等[19]引入了時間鏈路預測方法，利用復雜網絡局部和全局拓撲結構，將科學家互引預測問題描述為引文網絡鏈接預測問題，其中鏈接預測方法通過使用時間鏈接預測度量來預測鏈接和鏈接權重。另外，有學者使用影響最大化算法從目標的當前影響用戶集合中確定一組可能的影響用戶[20]。而Bastami等[21]提出了基于無監督鏈路預測方法，利用節點特征、社區信息和圖特征組合來提高局部和全局預測精度。Grover等[22]以半監督方式使用這些信息進行節點聚類，并使用不同的統計抽樣方法來生成網絡中的節點上下文，但有時統計抽樣方法也無法有效保持節點的高階拓撲關系。而Cao等[23]提出的GraRep算法依賴于奇異值分解(singular value decomposition, SVD)和矩陣乘法法進行鏈路預測，但具有較高的時間復雜度。另外，Wang等[24]所提SEMAC法也是基于矩陣乘法進行鏈路預測優化，并應用于每個節點對應的子圖預測，Dharavath等[25]將鏈路預測定義為二分類問題，根據節點相似性選擇一組特征，而Aghabozorgi等[26]利用網絡圖作為監督學習下的結構特征來進行鏈路預測。所以綜上所述，在預測社交網絡中的鏈接時，不完整是另一個嚴峻的挑戰，這是由于幾乎所有的社交網絡數據都包含缺失值，這是出于匿名和隱私保護，通常只能收集部分數據，且當網絡規模較小或缺少嚴重時，冷啟動問題尤為嚴重，而在處理耦合網絡時也會遇到這種情況。所以在網絡中完善和實施鏈路預測方法是現在復雜網絡研究的核心問題之一。

2 算法設計

2.1 預備知識

鏈路預測方法旨在根據不同域上不同結構特征對網絡進行準確預測。自適應度懲罰算法根據復雜網絡聚類系數對公共鄰域的度進行懲罰，一般的相似度度量方法可定義為式(1)所示。

(1)

其中:α為常量，z為x和y間的公共鄰居，且Γz為z的度數。不同方法間的區別為α值。在自適應度懲罰算法中，α值通過考慮節點間最短路徑和平均聚類系數得出節點間是否存在較強相關性及聚類系數，作為兩個節點x和y間的鏈接概率可被表示如式(2)所示。

(2)

其中:C為平均聚類系數，β為常量值。將聚類系數作為復雜網絡結構屬性，對每對節點間共享鄰居的個數進行分組。自適應度懲罰算法可在多種網絡上進行，并取得良好性能。網絡中有幾個結構屬性，特征包括節點間最短路徑、節點間路徑的信息熵、網絡中最長最短路徑的網絡直徑及節點聚類系數。平均聚類系數是整個網絡的常數，可通過計算網絡中每個節點的聚類系數得到。故可根據式(3)計算節點x的聚類系數，且可得平均聚類系數如式(4)所示。

(3)

(4)

2.2 所提SLP-CNP法

基于相似度的鏈路預測方法具有相同的框架，節點間相似度是不同方法間的唯一區別。其主要目的是提供更準確的指標來估計網絡中節點間鏈路存在的概率，是每對節點間的相似度得分。而每兩個節點間的鏈接概率取決于其間的公共鄰居數量?，F有方法多沒有將處罰程度與網絡特征和結構進行聯系，而自適應度懲罰算法適當利用相似性指數中的平均聚類系數來關注復雜網絡特征和網絡結構，但其缺乏對公共鄰域形式的關注。為克服這一挑戰，本文提出了SLP-CNP法，從一個新的角度看待鄰域。通過區分公共鄰域對自適應度懲罰算法進行改進。如需計算節點x和y間的相似性得分，為提高鏈路預測的效率，在度量中考慮了這種差異。如節點x和y有已經是互為鄰節點的節點對，則節點x和y將來成為好友的概率將比節點x和y有不屬于朋友的的概率要大。需要注意，當公共鄰節點的數量增加時，鏈路預測方法的精度和效率提高。為此，所提方法以不同方式考慮共享鄰居，還可根據網絡結構進行調整，具體如式(5)所示。

(5)

其中:z為兩個節點x和y的公共鄰居，|Cz|為鄰居數量，除節點x和y外還包括其公共鄰居。Γz為z的鄰域數量，C為平均聚類系數。本文所提SLP-CNP法的具體步驟如算法1所示。首先計算每個節點的平均聚類系數，將網絡分成訓練集和測試集(10%和90%)，采用5次交叉驗證將原網絡的總邊劃分為5個等邊。計算每個邊的相似度得分按降序排列，然后將排列列表中的邊添加到序列列表中。在列車網絡圖的邊上添加與測試集完全相同的邊數，并從主網絡中任意減去。這些添加的邊是預測邊。最后，確定真陽性(正確預測)和假陽性(錯誤預測)數量，并基于此計算精度。

算法1:本文所提SLP-CNP算法

輸入：復雜網絡圖G

輸出：平均精度與AUC

01:for每個節點ido

02: 對于節點i計算簇系數

03:endfor

04: 基于簇系數之和與簇數量的商計算平均簇系數

05: 將圖G按5-fold切分為訓練網絡Gtrain與測試網絡Gtest

06:for訓練網絡Gtrain中的每條邊(x,y)do

07: 對每條邊(x,y)計算相似性得分Sxy

08:endFor

09: 按降序排列所有相似性得分Sxy

10: 基于有序列表插入邊至訓練網絡Gtrain

11: 基于式(6)和式(7)計算精度和AUC值

12: 基于上述精度和AUC值結果，并使用式(8)和式(9)計算平均精度和AUC值

(6)

(7)

其中:n′是錯誤鏈接分數大于不存在鏈接分數的次數，n″為兩個分數相等的次數，n為比較總次數。如得分來自獨立分布，則AUC值預計為0.5，故如AUC值高于0.5表示性能優于純隨機情況。為獲得預測精度，對不存在的鏈接分數計算精度，并將得到值可按降序排序。然后，選擇得分最高的L條鏈接，得到l作為正確預測的鏈接數量。

(8)

(9)

3 實驗設計

為證明本研究所提SLP-CNP算法的有效性，本研究使用3個真實社交網絡數據集進行數值模擬，以便觀察算法對現實情況的適應度(實驗中使用的真實社交網絡數據集特征如表1所示)。其中，激活率根據網絡圖的稀疏性進行設置，并基于社交網絡中節點度和二階度的平均值進行計算。本文使用Python軟件以近期的熱點事件“HUAWEI event”和“華為事件”的30個熱點評論用戶節點作為初始節點，爬取了知乎、CSDN和新浪微博的社交網絡用戶數據集作為實驗仿真的基礎數據(爬取時間為2020年4月23日-2020年9月6日)。本研究將每個用戶作為一個節點，使用節點間的邊界表示用戶間關系。本研究選擇了10個具有較強影響力的用戶及其好友列表作為社交網絡初始節點，以此生成了簡單社交網絡。實驗在MATLAB 2017b環境下實施，并都是在Windows10操作系統的服務器(Intel Xeon處理器(34 GHz)和32 GB內存)上進行。首先隨機選擇10%的鏈接并從網絡中刪除。為了獲得更精確的結果并避免算法的隨機行為，此選擇將執行五次。接下來，應用5倍交叉驗證方法，將網絡劃分為5個相等的部分，每次將一個部分視為測試集或信用集。

表1 社交網絡數據集說明

為評估本文所提SLP-CNP鏈路預測算法的性能，將其結果與現有較為成熟的重要節點識別算法進行比較。其中包括4種中心度算法：即度中心性法[15](degree centricity, DC)、k-shell法[27]、PageRank法[18]和介數中心性法[16](intermediate centrality, IC)。兩種啟發式算法：雙折扣法[16](double discount, DD)和啟發式聚類法[22](heuristic clustering, HC)。兩種元啟發式算法：度遞減搜索策略(degree descending search strategy, DDSE)[23]和自適應度懲罰算法(ADP)[19]。由于實驗中SLP-CNP鏈路預測算法預測列表在每次運行時的結果都有可能不同，故設置評估結果為迭代100次運行后的平均值，運行的平均標準差為1.524。如前所述，β為一個常數參數，該參數值影響兩個節點間存在鏈路的概率，而該參數在一定程度上決定了該方法的性能。故考慮到所提用于計算兩個節點間存在鏈路的可能性的指標，為每個節點設置不同的值。本文采用試錯法，首先評估標準的應用基于參數γ為每個網絡，然后最好的表現γ對于不同的網絡可獲得的多個γ∈[-1.0,1.5]范圍內，每個網絡的性能最好γ實現價值。然后在網絡的聚類系數和最佳性能γ值間進行線性回歸以確定β數值，故對于精密測量而言β=1.74(合成網絡圖如圖1所示)。

圖1 合成網絡圖結果

4 實驗結果與分析

4.1 基準實驗結果

首先隨機選擇10%的鏈接從網絡中刪除，為獲得更精確的結果并避免算法的隨機行為，并應用5-fold交叉驗證法將網絡劃分為5個相等部分，為保證算法的正確性在圖1所示的合成網絡結構中進行。在網絡中提出的鏈路預測方法后，該算法將最相似的分數賦予所提邊，實際上可被視為預測邊。在上述情況下精度值是1，作為正確的預測邊相對于預測邊數量的比率，這與邊的正確預測完全相同。此外AUC值為0.939，且根據精度和AUC值，并以該方法提供的邊作為結果，可知該方法能正確地預測丟失鏈路。

將本文所提SLP-CNP算法與現有算法進行性能比較。用于比較的鏈路預測方法都是基于相似度的，由于本文所采用的數據集是無向的，故通過考慮已經與邊相連的每對節點之間的兩個方向來施加測度，并將其結果與所提方法進行比較。實驗結果表明，本研究所提度量方法較其他方法更為有效。表2通過選擇3個真實網絡中20%的邊來說明不同算法的性能。結果表明，本研究所提SLP-CNP算在所有狀態下的性能都最優。表3報告了不同真實網絡的5-fold交叉驗證，展示了不同算法的性能，可知本文所提SLP-CNP算法較其他算法更優。

4.2 時間復雜度

如前所述，計算復雜度和執行時間是鏈路預測方法的關鍵挑戰，故當一種方法能夠在基于評估標準的執行時間和效率間取得良好平衡時更為優越?？偟膩碚f，所有基于鄰域的相似性度量都有相同過程，所有這些方法間的唯一區別是計算相似性的過程。在進行SLP-CNP法計算時，對于節點x首先搜索x的所有鄰節點。遍歷節點鄰域的時間復雜度僅為k，而本文所提SLP-CNP法的時間復雜度為O(nk2)，n表示節點數量，k表示平均度。除時間復雜度外，內存空間是算法實現面臨的另一個限制。在進行SLP-CNP法計算時，所需的內存約為O(nk)，顧所需內存和CPU時間相對較少。表4報告了本文所提SLP-CNP法與其他方法的運行時間(以秒為單位)比較結果。由結果可知，本文為所提方法的時間復雜度較其他方法較優。總的來說，本文所提方法的主要優點是獲得了高性能，比基于相似性的方法更好，計算復雜度非常低，這大大減少了基準數據集中的運行時間。

表2 不同真實復雜網絡中選擇10%邊的算法比較結果

表3 不同真實復雜網絡中通過5-fold的算法比較結果

表4 不同真實復雜網絡中算法時間復雜度比較結果

表5 不同算法的Friedman檢驗比較結果

4.3 統計性檢驗

本研究使用Friedman檢驗[27]，分析了從不同相似性鏈路預測方法獲得的結果。Friedman檢驗是一種非參數統計檢驗，用于發現多種方法的行為差異。非參數(無分布)意味著測試不假設數據來自特定的分布。Friedman檢驗可用于評價N種不同方法對K個數據集的結果。在這個測試中，這些方法是根據它們的性能標準來排序的。本文以精密度和AUC為評價標準，以高階方法的評價效果最好。表4報告了上述鏈路預測方法的排名?？芍疚乃酳LP-CNP法的分類精度和AUC分別為4.00和3.77，高于其他基于相似度的分類方法，且P值小于0.05。故可知上述結果通過統計性檢驗是顯著的。

5 結束語

本文提出了新的鏈路預測度量方法，將聚類系數作為網絡的結構屬性加以考慮，該方法除考慮每對節點的共享鄰居，還考慮了共享鄰節點的鄰節點，故比其他類似鏈路預測方法具有更好性能。為驗證該方法的有效性，在多個真實網絡上進行對比實驗。結合在知乎、CSDN與新浪微博等社交網絡環境中的實驗結果可知，本研究所提SLP-CNP法較其他算法具有更優精度與效率。在未來的工作中，將嘗試提出新的系統化方法，提出并行算法顯著提高效率的方法來改進所提出的方法。其次，還可嘗試本文所提方法在加權網絡、有向網絡和二部網絡中的適用性。再次，可嘗試使用不同的操作符，以有效提升鏈路預測算法的時間復雜度，以提升算法的運行效率。另外，可嘗試使用深度學習等先進技術以提升復雜網絡鏈路方法的效率與精度。最后，可提出鏈路預測方法以確定適當參數值，以優化相似度方法。在應用場景方面，可嘗試在如蛋白質網絡、恐怖分子網絡、科研合作網絡、多層網絡等其他復雜網絡結構中對本文所提算法的適用性進行驗證。