融合節點重要性的無監督鏈路預測算法

傅馨玉，顧益軍

中國人民公安大學 信息網絡安全學院，北京 102600

鏈路預測是研究復雜網絡[1]的核心內容之一，在生物研究[2]、電子商務[3]、合作推薦[4]、社會安全[5]等眾多領域得到廣泛的實際應用。在復雜網絡中，將個體稱為節點，節點間的關系稱為連接。鏈路預測，即根據網絡中的已知節點以及節點間的連接情況等信息，預測該網絡中任意兩個未連接節點之間可能會產生新連接的概率[6]。近年來，隨著機器學習、深度學習的不斷發展，一些有監督式鏈路預測方法[7]成為研究熱點，通過定義損失函數訓練模型或者利用先驗知識來進行鏈路預測，學習訓練的過程通常需要大量的時間成本。現實世界中網絡數據集多為“小世界”[8]模型下的加權復雜網絡，對于一些小規模、需要快速預測的網絡，往往不需要采用有監督式鏈路預測方法，消耗大量的訓練時間，并且小規模數據集下訓練的效果較差。反而一些無監督式鏈路預測方法，在保證預測精確度的同時，可以高效快速輸出預測結果，更適用于解決此類加權網絡鏈路預測問題。無監督式鏈路預測方法可以分為基于似然分析的預測方法[9]和基于相似性[10]的預測方法。基于似然分析的預測方法需要不斷更新樣本，時間復雜度較高，不具備普遍適用性。常用的基于相似性的預測方法，計算信息容易獲取，算法復雜度低，并根據網絡結構信息量的多少，可以劃分為基于局部網絡結構和基于全局網絡結構的預測指標。在真實加權網絡數據集中，存儲、計算權重信息和路徑信息會增加算法的時間復雜度，因此在一些小規模、需要及時解決的事件預測問題上，基于局部網絡結構的無監督預測方法更為適用。

然而，這類方法通常僅考慮節點度[11]、共同鄰居[12]、邊權值[13]、路徑[14]等信息，忽略了節點自身重要性對新連接產生的影響。“中心性”常用來刻畫網絡中節點的重要程度，應用到無權網絡的相關研究上[15-16]。在真實加權網絡上，受到親近關系、傳播阻塞等現實因素影響，會出現低中心性節點同樣具有高重要性的情況，對鏈路預測結果產生一定影響。

針對上述問題，將無權網絡上節點重要性的研究更多地延展到加權網絡上，分析節點重要性影響連接產生的方式以及不同中心性下的影響差異，并應用到加權網絡鏈路預測方法中。本文的主要貢獻包括：（1）證明了在現實加權網絡中，中心性小的節點反而越重要，產生新連接的可能性越大，節點重要性在鏈路預測問題研究中起到重要作用；（2）提出一種融合節點重要性的無監督鏈路預測算法FNI（unsupervised link prediction algorithm fusing node importance），相比同類基于局部網絡結構的無監督預測方法提高了精確度；（3）對比圖嵌入等有監督式鏈路預測方法，無監督的FNI算法能夠更加準確地解決現實里小規模加權數據集上的快速預測問題。

1 加權網絡鏈路預測相關研究

當前加權網絡鏈路預測相關研究方法相比無權網絡較少，可以分為有監督式和無監督式鏈路預測方法。

1.1 有監督式鏈路預測方法

機器學習、深度學習領域不斷提出各種有監督式方法用于解決鏈路預測問題，最為常用的就是圖嵌入方法，主要包括基于矩陣分解、隨機游走和深度學習的圖嵌入方法。Ou 等人[17]針對有向圖中的非對稱傳遞性，將嵌入分為源嵌入和目標嵌入，提出基于矩陣分解的HOPE（high-order proximity preserved embedding）算法；Grover等人[18]通過調整深度優先搜索和廣度優先搜索策略的參數，用Skip-Gram模型對生成的游走序列進行嵌入，提出基于隨機游走的Node2vec 方法；Wang 等人[19]提出基于深度學習的SDNE（structural deep network embedding）方法，保持一階和二階相似性，利用高度的非線性函數和優化目標函數生成嵌入向量。這些方法通過大量的迭代輪數，最小化各自定義的損失函數，得到最佳的嵌入向量表示，計算節點向量間的相似性輸出預測結果。然而，監督訓練過程往往需要大量的時間，且存在訓練結果較差的可能，在小規模加權網絡上并不具備訓練的必要性，時間成本投入和預測結果收益不成正比。

1.2 無監督式鏈路預測方法

基于似然分析的預測方法通常適用于規模龐大的網絡，在加權網絡上邊的存在性可以用泊松的似然程度來表示。具有代表性的是泊松隨機分塊模型、度修正的泊松隨機分塊模型以及非負矩陣因子分解模型。這類算法的時間復雜度較高，且不適用于小規模網絡的連邊預測。

基于局部網絡結構的預測方法主要可以分為基于局部信息、路徑信息以及局部與路徑相結合的三類指標。在基于局部信息的預測指標中，Lv等人[20]將經典相似性指標拓展到加權網絡上，提出了WCN（weighted common neighbors）、WAA（weighted Adamic-Adar）、WRA（weighted resource allocation）三種經典指標。在共同鄰居的基礎上考慮兩端節點度的影響，WCN 指標從不同角度衍生出WSalton、WS?rensen、WHPI（weighted hub promoted index）、WHDI（weighted hub depressed index）、WLHN-I 五種加權指標。這一類指標很好地結合了節點強度和權重值，計算復雜度低，但計算方式僅限于存在共同鄰居的兩階路徑下，高階相似性并沒有得到充分計算。

基于路徑的預測指標可以寫成統一的形式：

其中，Sxy表示節點相似性，α表示可調參數，A為含權鄰接矩陣。區別在于路徑的步長限制不同，最為常用的是加權局部路徑指標WLP（weighted local path），其將路徑步長限制在三步之內。這一類指標從路徑的角度出發，全面考慮多路徑、高階路徑對節點相似性的貢獻，反而忽略了節點自身屬性在鏈路預測問題中的重要作用。

綜合上述兩類指標各自的優缺點，學者們不斷提出局部與路徑信息相結合的指標。Zhao 等人[21]通過路徑權重的乘積衡量該路徑對節點間相似性的貢獻程度，定義可信路徑加權指標rWCN（reliable-route WCN）、rWAA（reliable-route WAA）和rWRA（reliable-route WRA）。Bai等人[22]提出了節點與路徑相結合的半局部預測指標WRALP（weighted resource allocation along local path）。劉苗苗等人[23]定義邊權強度、路徑相似性貢獻，并限制路徑長度來計算相似性得分，提出了基于多路徑節點相似性的預測指標STNMP（similarity based on transmission nodes of multi-path）。白楊等人[24]提出了將可靠路徑與WRALP相結合的預測指標PWRALP（product-WRALP）。雖然這一類預測指標，相比前兩類指標具有更高的預測精確度，但僅憑相似程度來判斷節點間建立新連接的可能性，忽略了節點重要性作為節點的重要屬性之一，同樣會影響新連接產生的可能性。

2 FNI算法

2.1 節點重要性對連接產生的影響

真實網絡中，新連接的產生具有一定的隨機性，并非任意產生。鏈路預測是在遵循概率分布的基礎上，區分不同連接產生的可能性，從而給出預測結果。節點重要性則會在一定程度上影響到這種可能性，原因在于一些親密關系強、傳播信息快的重要節點，往往更容易與其他節點建立通話接觸、信息傳遞、合作互利等不同現實意義上的關系，增強了該節點產生新連接的可能性，促使網絡結構發生變化。尤其是在當尚未連接的節點對間根據相似性計算的連接可能性相同時，重要性高的節點更有可能產生新連接。根據節點的度數大小、對網絡連通性的貢獻作用、在網絡結構中的位置以及鄰居節點的重要程度等定義的中心性，均可以用來評估該節點的重要性。在一些傳播網絡中普遍認為，一個新加入的節點更容易選擇網絡中已有的大度節點建立單向行為的新連接，例如微博新用戶在注冊后會單方面關注明星博主。然而在現實網絡中，更多的是在已有網絡結構信息下，解決現存節點間產生新連接的預測問題，這種連接主要表示合作、溝通等雙向行為，會受到親密關系、傳播阻塞等因素的影響。因此，一些中心性高的節點由于連接關系較為固定，不易產生新連接，反而是中心性低的節點間更容易拓展新的雙向行為關系，在判斷新連接產生時其節點重要性更高。

例如圖1所示，A、B節點和A、C節點在相似性指標計算下的連接可能性相同，然而在現實情境下，節點重要性會從不同角度改變兩個節點對間產生新連接的可能性。圖1（a）表示微博關注關系網絡時，C節點的度中心性小于B節點，由于A更容易去關注朋友的親密朋友C，而不是朋友所關注的流量明星B，因此C節點對于A節點而言更重要，產生新連接可能性更大。圖1（b）表示科學合作網絡時，核心成員B的合作關系較為固定，產生新連接的可能性較小，反而是C節點的介數中心性更低，對同為外層成員的A而言，是建立新合作的重要伙伴，使得網絡進一步擴大其連通范圍。圖1（c）表示機場航班網絡時，B節點屬于中轉樞紐，當負載量達到一定程度時，與小機場A開通新航班的可能性不高，而C節點接近中心性較低，即使處于網絡邊緣，在新航線的備選名單中地位也格外重要。圖1（d）表示涉密信息傳播網絡時，實心節點表示影響力較大的信息傳播點，當A節點傳播私密信息時，更可能會選擇特征向量中心性小的C節點，認可其在信息傳遞過程中的重要性。

圖1 4個簡單加權網絡示例圖Fig.1 4 simple weighted network sample diagrams

綜上所述，新連接的產生沒有遵循可限定概率分布，利用結構相似性計算新連接可能性這一方式并不嚴謹，節點重要性正是通過改變這種可能性來影響連接的產生，且中心性小的節點可能更為重要。因此，FNI 算法從結構相似性和節點重要性兩個角度出發，更加準確地計算新連接產生的可能性，按照可能性從高到低排序作為預測結果。

2.2 不同中心性對連接產生的影響差異

節點重要性可以影響連接產生的可能性，但是從不同角度衡量節點重要性時，影響程度也會有差異。以常用的度中心性（degree centrality，DC）、介數中心性（betweenness centrality，BC）、接近中心性（closeness centrality，CC）、特征向量中心性（eigenvector centrality，EC）為代表，在10 個經過無向加權處理后的數據集上，綜合分析不同中心性對連接產生的影響差異。分別計算平均節點中心性值cˉ和平均連接中心性值-cl，二者的差值Δc可以量化表示出中心性對連接的影響程度，Δc ＞0 則說明中心性對新連接的產生具有一定影響，具體計算方式為：

其中，kx表示節點度，E為邊集合，| |E為連邊數，V為節點集合，| |V為節點數。Δc越大說明該中心性對連接產生的影響越大，Δc值較小即表示對連接產生的影響不夠明顯。表1 展示了各數據集在不同中心性下的Δc值，括號內序號表示同一數據集上Δc值由大到小的排序。

表1 各數據集上不同中心性的Δc 值Table 1 Δc values of different centrality on datasets

分析表1 可知，由于網絡數據集的拓撲結構差異，不同中心性對連接產生的影響差異較大。具體表現為DC在70%的數據集上Δc值同比最高，對連接產生的影響最為明顯。根據度中心性的大小來衡量節點重要性，可以有效區分各連接產生的可能性，對鏈路預測結果產生影響。根據表中排序順序可知，CC 和EC 相比DC 而言總體表現相對較差，BC對連接產生的影響最小，在相似性得分相同的情況下，難以區分連接產生的可能性。因此，FNI 算法選取度中心性值來衡量節點重要性，最大程度地區分不同節點對間連接產生的可能性，充分發揮節點重要性對鏈路預測結果的影響作用。

2.3 FNI算法描述

通過分析節點重要性對連接產生的影響，總結出在加權網絡中重要性越高的節點與其他節點建立新連接的可能性越大；通過分析不同中心性對連接產生的影響差異，總結出度中心性對連接產生的影響最大，因此提出一種融合節點重要性的無監督鏈路預測算法FNI。首先，通過計算邊權強度simxy和路徑貢獻Sxy_path來計算節點對的相似性得分Sxy，并且計算節點對的中心性得分Cxy以衡量節點重要性。

其次，由于相似性得分與中心性得分的數量級存在差異，如果直接用原始數值進行分析，就會突出數值較高的一方得分在綜合分析中的作用，相對削弱數值水平較低得分的作用。為了保證結果的可靠性，結合MinMaxScaler 函數對Sxy和Cxy進行歸一化處理，映射到[0，1]區間，分別表示為New_Sxy和New_Cxy。

最后，由于相似性得分和中心性得分均是從衡量建立新連接可能性的角度出發，通過調節系數的方式將二者相加，實現雙方共同作用的最大效益，使算法達到預測效果的最優化。對相似性得分分配系數α，對中心性得分分配系數β，計算節點對建立新連接的可能性Pxy。若系數β為負值，則表明該數據集上中心性小的節點更為重要，增加新連接產生的可能性，而中心性高的節點反而會抑制新連接的產生；若系數β為正值，則表明該數據集上節點的中心性越高，其重要性越高。如算法1所示。

算法1 FNI算法

節點數量為n的網絡數據集中，總節點對數量為n(n-1)/2 個。現有的基于局部結構信息的無監督預測方法均需要計算每對節點之間的相似度，時間復雜度為O(n2)。FNI算法首先計算每個節點對的相似性得分和中心性得分，時間復雜度為O(n2)；隨后利用歸一化函數在自定義參數下，計算節點間的連接可能性，時間復雜度仍為O(n2)。因此FNI算法的總時間復雜度為O(n2)，在保證算法運行效率的同時，綜合節點重要性和結構相似性對連接產生可能性的影響，在解決小規模加權網絡數據集的快速預測問題上，相比同類方法考慮更為全面。

3 實驗驗證與結果分析

3.1 實驗設置

實驗選取5個不同領域的典型真實數據集，均為小規模加權網絡。將每一個數據集對應到各自需要做出快速預測結果的真實情景中，解決實際問題。美國航空公司網絡US Air（US）：受天氣等突發情況影響需要臨時增設新航班；神經網絡C Elegans（CE）：生物實驗需要不斷預測下一突觸的產生；科學家合作網絡Net Science（NS）：科學家快速鎖定下一次學術合作中的預選對象；爆炸案恐怖分子聯系網絡Train Bombing（TB）：第一時間掌握恐怖分子間的聯系傾向以便采取行動；小說人物關系網絡Lesmis（LE）：即時預測小說人物間關系走向。將實驗數據集預處理后按照csv 格式存儲，借助可視化網絡分析工具Gephi，呈現出相應數據集的網絡拓撲結構圖，每個網絡的結構信息如表2所示。

表2 各數據集的拓撲結構Table 2 Datasets topology

采用隨機抽樣的方式對每個數據集進行100 次隨機劃分，抽取其中90%為訓練集，10%為測試集，計算AUC值來表示預測結果的精確度。實驗共分為以下三部分：（1）驗證不同中心性對連接產生的影響差異，確保FNI 算法以度中心性衡量節點重要性的合理性；（2）橫向對比其他基于局部網絡結構的無監督預測方法，驗證FNI 算法提高預測結果精確度的有效性；（3）縱向對比三種基于圖嵌入的有監督式鏈路預測方法，針對小規模加權網絡快速預測問題，分析FNI算法的必要性。

3.2 驗證不同中心性的影響差異

不同中心性從多角度衡量節點重要性，對連接產生的影響差異很大，勢必也會體現在對鏈路預測結果精確度的影響上。參考FNI算法的核心思想：Pxy=αNew_Sxy+βNew_Cxy，實驗利用WCN、WAA、WRA 以及WLP 四種經典相似性指標計算Sxy，利用DC、BC、CC、EC四種中心性指標計算Cxy，并按照WCN 對應的新指標分別WCN_DC、WCN_BC、WCN_CC、WCN_EC 的方式，以此類推進行命名。

在實驗過程中，為快速找到相應α、β值，結合梯度下降更新參數，得到最終的預測AUC 值。本次實驗的重點在于證實相比其他中心性指標，度中心性度量節點重要性時，對鏈路預測結果具有最大程度上的積極影響。表3 總結了每一種新指標在不同數據集上的預測精確度，括號內數字代表同一數據集、不同中心性下，新指標AUC 值的排名情況，下劃線標注代表預測效果不如原指標。

表3 不同中心性對預測結果AUC值的影響Table 3 Influence of different centrality on AUC values of predicted results

分析表3 可知，DC 在5 個數據集上均表現良好，能夠提高原有指標1%～2%的預測精確度，在其相應20 組實驗中，達到同比最高精確度12次，對連接產生的影響最大，新指標的預測結果更為精準；BC 在應用到WLP指標上時，使兩個數據集下的精確度與原指標持平，除此之外其他新指標的精確度均明顯下降；CC在其20組實驗數據中，有3 組實驗的精確度略低于原有指標，并在2 組實驗上實現了預測結果最優化，總體表現相比DC 較差；EC 在TB 和LE 數據集上表現較為優異，在其20 組實驗中，6 次實現最優預測結果，但在7 組實驗中，大幅降低了原有指標精確度，不具有相對穩定性和普適性。

綜上所述，節點重要性對連接產生具有一定的影響，其度量方式對預測結果的作用差異較大，實驗結果基本符合上文理論分析。即DC相比其他三種度量方式整體對連接產生的影響最大，能夠體現在鏈路預測的結果中，以度中心性度量節點重要性，并以此計算新連接產生的可能性，能夠穩定有效地提高預測精確度。CC和EC 的影響效果波動較大，適用性弱于DC，無法解決不同結構類型數據集的鏈路預測問題，而BC 完全不適用。因此，在四種經典相似性指標上的大量實驗，結果足以證明度中心性對新連接產生的影響最大，對鏈路預測結果準確性的提高效果最為明顯，確保了FNI算法以度中心性大小衡量節點重要性，具有理論正確性和實踐可行性。

3.3 FNI算法預測結果

針對小規模加權網絡的快速預測問題，將FNI算法與同類基于局部網絡結構的無監督預測方法進行橫向對比實驗，預測精確度結果如表4所示。

表4 FNI算法橫向對比實驗AUC值Table 4 AUC values of transverse contrast experiment of FNI algorithm

分析表4 可知，4 個數據集上FNI 算法預測精確度AUC 值，明顯高于同類其他11 種基于局部網絡結構的無監督預測方法。只有在Lesmis（LE）數據集上由于數據集特性，局部信息相比路徑信息更有效，FNI 算法的精確度與rWRA指標近乎持平，但仍明顯高于其他預測指標。分析其具體原因，FNI算法首先合理考慮了節點重要性對連接產生的影響；其次，利用度中心性來計算中心性得分，更加精準地計算了不同節點對間產生新連接的可能性；最后，通過自定義系數最優化結構相似性和節點重要性對預測結果的影響程度。因此，實驗結果證實了在小規模加權網絡數據集上，FNI算法相比現有其他同類方法整體提高了預測結果AUC 值，可以達到最佳預測效果。

在證實FNI算法預測結果的有效性后，進一步分析FNI 算法中的參數選取。在計算產生新連接可能性Pxy=αNew_Sxy+βNew_Cxy這一步驟里，參數α和參數β均為自定義參數。實驗中為快速找到相應α和β值，選取α初始值為1，β初始值為-1，采用梯度下降思想來更新參數取值，將預測精確度與期望精確度差值定義為損失函數并使其最小化。圖2 表示隨著參數的迭代更新，各數據集上的損失Loss值不斷下降，AUC值保持上升趨勢，逐步趨于穩定，最終得到所需參數α、β。

圖2 各數據集上Loss值和AUC值變化情況Fig.2 Loss value and AUC value changes on datasets

表5展示出FNI 算法在不同數據集上的相應參數α、β值。β在5個數據集上最終取值全部為負值，驗證了中心性小的節點，在其局部網絡結構中地位更加重要，與其他節點產生新連接的可能性更高。對應到5個數據的具體情境中可以理解為，航空網絡里中心性大的中轉樞紐可能行程較滿，班次較少的小機場間更容易新建航班；神經網絡里一些高中心性的神經元接受傳遞信息通常具有重復性，一些傳遞作用較少的神經元更容易傳遞出新信息；科學家合作網絡里兩個團隊的權威人物間的合作概率要小于其各自同自己團隊伙伴合作的概率；恐怖分子聯系網絡里主謀的聯系關系較為隱秘固定，遠離核心的幫兇間更容易彼此聯系；小說人物關系網絡里主要角色關系已經充分介紹，小人物間會發生更多關系碰撞的故事。

表5 FNI算法的參數取值Table 5 Parameter values of FNI algorithm

綜合5個數據集上的取值表現，α穩定在區間（1.0，1.5]，β穩定在區間(-0.4,0)，說明在小規模加權網絡上，結構相似性同比節點重要性對產生連接可能性的影響程度更大，但節點重要性的影響程度同樣不可忽略。

FNI算法預測結果的對比實驗，證實了本文的兩個貢獻：一是中心性小的節點反而更重要，節點重要性在鏈路預測問題中具有重要研究意義；二是本文提出的FNI 算法相比同類基于局部網絡結構的無監督式鏈路預測方法，預測結果AUC值整體更高。

3.4 FNI算法的必要性評估

近年來，一些基于機器學習和深度學習的圖嵌入方法在鏈路預測問題研究中較為常用。縱向對比無監督式FNI 算法與三種不同類型的有監督式圖嵌入方法的整體性能，確保FNI 算法在當前加權網絡鏈路預測的相關研究中具有必要性和特定優越性，實驗結果如表6所示。

表6 FNI算法縱向對比實驗AUC值Table 6 AUC values of longitudinal contrast experiment of FNI algorithm

由表6 可知，FNI 算法在US 數據集上相較于Node2vec 方法AUC 值提升最多，約提升27 個百分點；在NS數據集上相較于HOPE方法AUC值提升最少，約提升3 個百分點。因此，綜合FNI 算法在5 個數據集上的表現，其AUC 值總體比有監督式的圖嵌入方法高3～27個百分點。分析其具體原因：首先，在規模較小的數據集上監督訓練的效果往往較差，稀疏網絡所對應的可用特征有限，學習生成的網絡表示存在較大偏差。其次，在短路徑網絡中，存在連接和不存在連接的嵌入向量不易區分其距離分布[25]，嵌入模型的訓練效果并不理想。實驗數據集除NS外，均為平均距離小于3的“小世界”網絡，實驗結果也表明NS數據集上圖嵌入方法整體的精確度更接近于FNI算法。

針對小規模加權網絡的快速預測，有監督式圖嵌入方法存在一定的弊端，不僅需要額外的監督訓練時間，最為主要的是其預測精確度普遍較低。FNI 算法的整體性能明顯優于有監督式的圖嵌入方法，故FNI算法的提出和運用具備解決實際問題的必要性。

4 結束語

節點重要性對連接產生的影響并未在現有基于局部網絡結構的無監督預測方法中得到體現，并且在真實網絡里中心性越小節點往往更加重要。本文從結構相似性和節點重要性兩個角度計算連接可能性，提出一種融合節點重要性的無監督鏈路預測算法FNI。大量實驗結果證明，在解決小規模加權網絡的快速預測問題上，FNI 算法在同類預測方法中的預測精確度更高，且相比有監督式的鏈路預測方法更具研究必要性。

本文所提算法在后續研究過程中，仍有需要不斷優化的方面：一是該算法雖然很好地利用中心性度量節點重要性，但是針對加權網絡節點重要性的研究仍需不斷探索；二是該算法在尋找路徑信息時較為復雜，后續會結合降維方法，降低算法的時間復雜度，實現算法性能的進一步優化。