融合節(jié)點重要性的無監(jiān)督鏈路預測算法

傅馨玉，顧益軍

中國人民公安大學 信息網(wǎng)絡安全學院，北京 102600

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

然而，這類方法通常僅考慮節(jié)點度[11]、共同鄰居[12]、邊權值[13]、路徑[14]等信息，忽略了節(jié)點自身重要性對新連接產生的影響?！爸行男浴背Ｓ脕砜坍嬀W(wǎng)絡中節(jié)點的重要程度，應用到無權網(wǎng)絡的相關研究上[15-16]。在真實加權網(wǎng)絡上，受到親近關系、傳播阻塞等現(xiàn)實因素影響，會出現(xiàn)低中心性節(jié)點同樣具有高重要性的情況，對鏈路預測結果產生一定影響。

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

1 加權網(wǎng)絡鏈路預測相關研究

當前加權網(wǎng)絡鏈路預測相關研究方法相比無權網(wǎng)絡較少，可以分為有監(jiān)督式和無監(jiān)督式鏈路預測方法。

1.1 有監(jiān)督式鏈路預測方法

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

1.2 無監(jiān)督式鏈路預測方法

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

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

基于路徑的預測指標可以寫成統(tǒng)一的形式：

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

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

2 FNI算法

2.1 節(jié)點重要性對連接產生的影響

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

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

圖1 4個簡單加權網(wǎng)絡示例圖Fig.1 4 simple weighted network sample diagrams

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

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

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

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

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

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

2.3 FNI算法描述

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

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

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

算法1 FNI算法

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

3 實驗驗證與結果分析

3.1 實驗設置

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

表2 各數(shù)據(jù)集的拓撲結構Table 2 Datasets topology

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

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

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

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

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

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

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

3.3 FNI算法預測結果

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

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

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

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

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

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

表5 FNI算法的參數(shù)取值Table 5 Parameter values of FNI algorithm

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

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

3.4 FNI算法的必要性評估

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

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

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

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

4 結束語

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

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