融合節點標簽與強弱關系的鏈路預測算法

王曙燕，鞏婧怡

西安郵電大學 計算機學院，西安710121

鏈路預測通過已知的網絡結構和節點信息等因素[1]，預測網絡中兩節點連接的可能性或發現已存在但未識別的隱式連邊。在社交網絡中，將用戶視為節點，各用戶社會關系視為連邊，對可能存在關系的用戶進行鏈路預測[2]。

常見的鏈路預測方法有：基于節點屬性信息、基于網絡結構和最大似然估計法[3]。然而，僅對網絡節點屬性的預測不能夠真實精確地反映出目標網絡的特性，并且與節點的屬性信息相比，更容易獲得網絡的結構信息，而且網絡的結構信息也相對比較可靠[4]。Liben-Nowell等[5]通過網絡節點的拓撲結構相似性分析社交網絡。后來出現的基于節點度的共同鄰居CN（common neighbors）[6]根據節點的共同鄰居進行推薦。王智強等[7]認為可借助鏈路預測檢測由于信息或數據的噪聲產生的不必要鏈接。

根據研究發現，僅考慮節點屬性或網絡拓撲結構的鏈路連接很難對節點信息進行較完全的刻畫并不能更加精確地對節點進行鏈路預測。本文提出一種融合節點標簽與強弱關系的鏈路預測（node labels and strong &weak relationships link prediction，NRLP）算法。該算法提取社交網絡部分子圖，通過對局部子圖生成的目標矩陣進行分解，并將子網絡結構融入節點標簽、文本屬性與關系強度的動態權重。該算法得到的節點向量兼顧網絡結構屬性、關系強弱與節點屬性，且通過局部子圖分析預測可能性比全圖降低算法運行時間。

1 相關工作

鏈路預測是預測網絡中的兩個節點是否可能具有鏈路[8]。鑒于網絡的普遍存在，它有許多應用，如朋友推薦[9-10]、知識圖完成[11]和代謝網絡重建[12]等。

一般來說，鏈路預測的研究可分為三大類：啟發式方法、基于網絡嵌入的方法和基于圖神經網絡的方法[4]。啟發式方法[13-14]側重于通過特定假設下節點之間的不同啟發式節點相似性來估計連邊的可能性。現有的啟發式算法通常包括基于共同鄰居CN 法[15]，當節點的共同鄰居越多則對其連邊，但此方法與現實生活情況不符。基于路徑的算法：余弦相似性法[16]、Jaccard法[17]、基于路徑的相似性法[18]（如Katz指標[19]、LHN-II指標[20]）等。基于共同鄰居的的算法比較簡單直觀，但未挖掘網絡所含有的豐富信息導致算法精確度受限，基于路徑的算法雖考慮節點間的路徑信息但計算復雜度較大。并且啟發式方法對節點何時可能存在鏈接有很強的假設，當其假設在目標場景中不成立時，可能會失敗[21]。

網絡表示學習通過將節點表示為低維向量保留網絡結構，然而在大型信息網絡中該方法計算復雜、效率較低。隨著skip-gram[22]算法出現的啟發，DeepWalk[23]將基于隨機游走產生的節點序列放入skip-gram模型輸出表示。張學佩[24]定義了局部隨機游走的節點相似度指標，并與其他相似性指標進行比較。結果表明，其提出的算法具有更低的計算復雜度。然而基于網絡嵌入大多數算法具有很高的精度，但在學習節點表示時沒有考慮到節點和邊緣的豐富屬性。

隨著現有網絡常用圖表示，其中節點表示個體或群體，邊表示個體或群體間的交互行為[25]，觀察節點和邊結構的內部特征，在保留復雜網絡本身特征的同時，可以生成其獨特的屬性。為了提高預測性能，劉樹新等[26]在網絡拓撲特征中增加附加信息，但在提升性能的同時會增加計算復雜性。并且由于網絡的復雜性，導致連接關系存在優劣性[27]，文獻[28]提出可以用權重矩陣衡量關系的方法。

通過對現有研究成果的觀察，時間效率和精確度都是鏈路預測中重要的因素?？紤]現有研究在信息與屬性方面的挖掘不足，本文采用雙半徑節點標簽（double radius node label，DRNL）算法[29]，借鑒TELP 算法的思想，在分解目標網絡的同時融入節點屬性信息，并在其中考慮同一節點對于不同中心節點的關系強弱，賦予不同的動態權值，提出一種融合節點標簽與強弱關系的鏈路預測NRLP 算法。其不僅通過局部子圖可以更快速地挖掘網絡所含節點位置信息，且在學習節點表示時考慮到節點和邊緣的關系屬性映射現實生活中的不同關系強度。最后，在三個數據上進行驗證，并與常見鏈路預測算法進行對比，結果證明本文算法預測效果較好。

2 算法設計

對于網絡圖G=(V,E),其中，V為點集，E為邊集，屬性矩陣為T∈ft為屬性特征的維度。由文獻[30]的結果表明，局部子圖保留了與鏈接相關的豐富信息，所以給定兩個節點x,y∈V，生成(x,y)的h深度局部子圖。

2.1 節點標簽

為每個節點生成節點標簽，表示為函數fl:V→N。對于在局部子圖的每一個節點i，為其生成一個整數標簽f(i)，在局部子圖中使用不同的標簽來標記中心節點與其他節點。通過節點表示差異性，在網絡中準確找到目標節點并獲得其相應結構信息[31]。

節點i在一個局部子圖中的拓撲位置可以用它相對于兩個中心節點的半徑(d(i,x),d(i,y))表述。如果d(i,x)=d(j,x)并且d(i,y)=d(j,y)，則節點i和節點j在圖中擁有相同標簽。

首先，將中心節點標簽設置為1。然后，對于(d(i,x),d(i,y))=(1,1)的任何節點，設置標簽f(i)=2。半徑為（1，2）或（2，1）的節點標簽為3，以此類推。

兩個中心節點，其中標簽f(i)和雙半徑(d(i,x),d(i,y))滿足：

（1）如果d(i,x)+d(i,y)≠d(j,x)+d(j,y)，則

（2）如果d(i,x)+d(i,y)=d(j,x)+d(j,y)，則

使用DRNL算法生成一個整數標簽fl(i)函數，如公式（1）所示：

其中，dx=d(i,x)，dy=d(i,y)，d=dx-dy。對于d(i,x)=∞或d(i,y)=∞的節點，將其記做空標簽0。

2.2 基于網絡節點文本增強的鏈路預測算法

DeepWalk算法其實質為矩陣分解，因此，DeepWalk算法的目標函數為[4]：

其中，W∈?,H∈?,Ω則為矩陣M的觀測集，‖?‖F是矩陣M的F-范數，λ是平衡因子，它主要用來優化分解后的W和H矩陣，其原理等同于L2范數。

曹蓉等[4]提出了基于網絡節點文本增強的鏈路預測算法TELP，在基于文本信息（text associated Deep-Walk，TADW）算法的基礎上對目標矩陣M進行分解，并根據余弦相似性算法，計算出任意兩個節點的相似度，從而構建出最終的相似度矩陣。

在目標矩陣M的分解過程中，使得下式達到最小：

2.3 融合節點標簽與強弱關系的鏈路預測算法

定義1（余弦相似度）圖中任意兩個節點的相似度可用余弦相似度表示為sim(x,y)=cos(x,y)+a，其中，x和y分別為目標節點和對比節點，a為調節參數，避免相似度過低導致的無效狀態。

然而根據關系相關理論[32-33]，本文在余弦相似度計算公式的基礎上根據關系強弱的特點，提出了一種融合節點標簽與強弱關系的鏈路預測NRLP算法，其具體框架如圖1所示。

圖1 融合節點標簽的屬性增強鏈路預測方法框架Fig.1 Attribute-enhanced link prediction method framework for fusion node labels

如圖1所示，該方法在已有的關系網絡中任意選擇兩個節點記為中心節點A、B，對關系網絡使用DRNL算法生成節點i相對于中心節點A、B構建節點標簽圖G。其次基于γ衰減理論局部子圖保存了豐富節點的信息，則以節點A、B 為中心構建深度為h的局部子圖，提取局部子圖中節點的特征矩陣M，基于式（2）對生成的特征矩陣M進行分解，并在矩陣分解過程中，引入屬性特征矩陣T，對每個節點進行向量表示并使其融入節點屬性因子，使分解后的矩陣、Hn×ft分別包含矩陣M、T的分解因子。其中，| |V1為h深度的局部子圖中節點個數，n為向量長度。最后使用矩陣WT作為節點的向量表示，結合NRLP 算法，得到任意兩個節點之間的相似度，對相似度高的中心節點進行連接，實現鏈路預測。

對所有分解得到的矩陣WT按比例分為訓練集和測試集，并使用AUC評價指標，對本文算法性能進行評估。本算法的通過DRNL 算法計算節點標簽其時間復雜度為O(|V|2)及TELP 模型學習節點向量表示其訓練復雜度為O(|V|2)，但本文在節點表示向量的訓練中才用局部子圖進行訓練，其復雜度明顯小于原模型全圖所有節點進行訓練。所以本文提出的NRLP 算法時間復雜度為O(|V|2)。

NRLP 算法考慮節點之間存在強弱關系，賦予其不同的權重，表示節點i相對于兩個中心節點x、y的不同關系程度。在局部子圖中，當節點i的dx=1,dy=1,f(i)=2 時，則節點i對于中心節點x、y為強關系，反之則為弱關系。若節點i的中心節點的半徑dx＜dy，則節點i相對于節點y與節點x有著更強的關系程度，反之亦然。而當dx=dy，則節點i與節點x、y有著相同的關系程度。由于節點i，對于不同中心節點生成的局部子圖會擁有不同的強弱關系，所以對其賦予不同的動態權值，其計算表達式如下所示：

公式（4）～（9）參數含義如表1。

表1 NRLP算法參數說明Table 1 NRLP algorithm parameter description

對于節點標簽為1的節點x、y，生成各自的相似度矩陣Sx=[Six]、Sy=[Siy]。構建Sx、Sy的相似度矩陣差S=Sx-Sy，在局部子圖中，當除中心節點x、y以外的節點標簽全為0時，則兩個節點完全不相似，其|SST|=0也認定兩節點不能連接。當其余節點標簽不全為0，且|SST|<ε時，對節點x、y進行鏈路連接。其中ε為相似閾值，只有相似度小于閾值時，認為兩個節點可能成為好友。

2.4 NRLP算法

NRLP算法描述如下：

3 實驗結果與分析

3.1 數據集和實驗設計

根據第2章所述一種融合節點標簽與強弱關系的鏈路預測算法，對數據進行驗證。實驗環境為Windows 10系統、Intel Core i7 處理器、32 GB 內存，采用PyCharm開發環境，Python 3.6進行算法實現。采用三個常見的數據集Citeseer、DBLP和Cora數據集進行實驗，驗證本文提出的算法有效性。數據集包含了節點之間的連邊關系和每個節點的屬性類類別。數據集信息如表2所示。

表2 數據集信息Table 2 Data set information

通過表2 可以看出，當節點個數大致相同時，邊的個數影響了圖的稠密度、平均度及平均聚類系數的大小。本文提出的NRLP 算法建模帶有屬性節點之間的關系，且對社會關系設置動態權重，得到的表示向量包含關系因子，結構因子及屬性因子。

3.2 評價指標

常見的鏈路預算精確度衡量指標有AUC、準確率、排序分等。本文采用AUC 評價指標衡量算法的準確性。鏈路預測算法在經過訓練后可以得到網絡中每一對節點的相似值。AUC評價指標即是基于測試集中邊的相似值和不存在的邊的相似值的比較，如果測試集中邊的相似值大于不存在邊的相似值，則證明算法預測效果好。將數據集劃分為測試集和訓練集，其中90%作為訓練集，10%作為測試集。從測試集中每次隨機選一條存在的連邊，再隨機選一條不存在的連邊。若存在的連邊分值大于不存在的連邊分值，則加1；相等則加0.5。通過n次獨立比較，若有n′次大于的情況，n″次相等的情況，則AUC表示為：

AUC評價指標取值范圍應為[0.5，1）。當訓練集越大，對應的AUC值越高，則算法的精確度越高。

3.3 對比分析

為進一步驗證本文提出的算法有效性，將本文算法與現有的多種預測方法進行對比。在實驗中，對三個數據集設置訓練比例為0.7、0.8、0.9，子圖深度h為2，向量長度為200，相似閾值為0.000 16，實驗鏈路預測結果如表3所示。

從表3 可以得出，將本文所提出的NRLP 算法與常見的鏈路預測方法比較，通過對比結果得出本文提出的NRLP 算法在三個數據集上的性能優于表3 中多種方法，并在Citeseer數據集性能最佳。由結果分析可知：本文所提出的NRLP算法優于目前大多數鏈路預測方法，其原因在于考慮節點的連接與屬性信息；并考慮連接關系的強弱，區分其關系強度與程度生成新的相似度計算方法；并通過無監督學習訓練節點表示向量，快速提取節點信息及其結構特征。

表3 數據集不同訓練比例鏈路預測AUCTable 3 Link prediction AUC with different training ratios in data set %

3.4 調參與分析

在本文實驗中，需要設置訓練比例、向量長度n和局部子圖深度h的值。通過調整局部子圖的深度，獲取兩中心節點的不同鄰居節點及其局部子圖范圍內的各節點屬性，比較局部子圖與原圖之間的差異。

由圖2 可知，本文對三個數據集在深度h為1～5 的局部子圖性能進行評估，當h=2 時，均達到最佳性能。AUC 值在h>2 時減小，這表明子圖越深可能會從遠處節點引入噪聲。當h=1 時，因為路徑較短時，節點及屬性信息較少導致差異較大。當長度變大時，引入路徑信息減少局部子圖與原圖之間的差異。

圖2 局部子圖與原圖對比圖Fig.2 Comparison of partial sub-image and original image

不同的訓練比例與向量長度對精確度擁有不同的影響，當局部子圖深度為2，相似閾值為0.000 16，得到的訓練率及向量長度對預測結果如圖3所示。

通過分析圖3 可以得出，向量長度為50、100、150、200、300，訓練集比例為0.70、0.75、0.80、0.85、0.90、0.95，Citeseer數據集和Cora數據集為較稀疏圖。當向量長度分別為300、150，訓練率分別為0.75、0.90 時，AUC 指標最優；DBLP 數據集為較稠密圖，向量長度大于100，訓練率在0.75～0.95之間，AUC幅度相差不大，基本在一定范圍波動。對于稀疏圖，向量長度與訓練率對AUC 影響較大，對于稠密圖，影響相對較小。

圖3 訓練率、向量長度與預測結果的關系Fig.3 Relationship between training rate，vector length and prediction result

為了證明NRLP 算法的效率，同時對比TELP 算法在原圖和本文算法在局部子圖上進行的時間見表4。

從表4 中可以看出，數據量較大時，在局部子圖上算法效率更高，局部子圖的噪音少于原圖且表示向量更加高效，所以表現明顯優勢。

表4 算法運行時間對比Table 4 Comparison of algorithm running time s

4 結束語

本文通過對節點生成標簽構造h深度子圖在鏈路預測時提高算法運行時間與效率，并采用TELP模型為基礎，分析不同關系強度對鏈路連接的重要性，并將余弦相似度算法與動態權重相融合，提出一種融合節點標簽與強弱關系的鏈路預測NRLP 算法。該算法同時考慮網絡結構、節點屬性及連接關系強弱對鏈接的影響，通過隨機選擇兩個中心節點判斷其成功鏈接的可能性。實驗結果通過在三種文獻的集成數據庫Citeseer、DBLP 和Cora 數據集驗證NRLP 算法的準確性和高效性。下一步工作將考慮對新聞資訊相關性或社交網絡人際關系預測實現鏈路預測，并嘗試將模型拓展融合更豐富的屬性進行教育資訊的社會化推薦。