融合節點屬性和無環路徑的社交網絡嵌入方法

王本鈺，顧益軍，彭舒凡

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

近年來，隨著互聯網技術的高速發展，社交網絡的規模不斷增加，社交網絡分析任務也變得愈發重要，例如節點分類、鏈路預測等。節點分類任務可以對網絡中的節點進行合理的劃分，在現實生活中具有重要的應用價值，例如在社交平臺中，通過用戶的類別標簽向用戶推薦好友；在智能廣告中，向可能感興趣的用戶精準投放廣告。鏈路預測任務可以有效分析網絡拓撲結構，預測網絡丟失的邊或者未來可能出現的邊，在社交網絡上應用前景廣闊，例如社交平臺用戶拓展、電商營銷等。各種各樣新穎的技術被用在社交網絡分析中來挖掘用戶潛在屬性，網絡嵌入[1]就是其中一種。

網絡嵌入旨在將高維稀疏數據映射到低維稠密向量空間，提取數據低維特征，以便于基于向量的機器學習方法進行下游網絡分析任務。目前主流的網絡嵌入方法可以分為基于網絡結構信息的網絡嵌入方法和基于網絡結構信息和屬性信息相結合的網絡嵌入方法。

基于網絡結構信息的網絡嵌入方法利用網絡拓撲結構捕獲節點低階甚至高階相似性，進而獲得網絡節點的低維特征表示。Perozzi 等提出DeepWalk算法[2]，將自然語言處理（natural language processing，NLP）中word2vec模型[3]運用到算法生成的隨機游走序列上，獲得基于節點上下文結構的嵌入表示。Tang等提出大規模信息網絡嵌入算法（large-scale information network embedding，LINE）[4]，結合網絡一階和二階結構信息，最小化KL 距離（Kullback-Leibler divergence）獲得網絡嵌入結果。Cao等提出GraRep算法[5]，將LINE 算法的一階和二階結構信息推廣到了高階結構信息。Grover等提出node2vec算法[6]，結合深度優先搜索和廣度優先搜索優化了DeepWalk中隨機游走序列生成方式。Cao 等提出學習圖表示的深度神經網絡算法（deep neural networks for learning graph representations，DNGR）[7]，通過隨機沖浪的方式獲得節點高階結構信息表示，然后通過棧式降噪自動編碼器進行網絡嵌入。Wang等提出深層結構網絡嵌入算法（structural deep network embedding，SDNE）[8]，通過深度自動編碼器獲得網絡嵌入結果。Ribeiro等提出struc2vec算法[9]，通過節點空間結構相似性定義節點相似性來獲得網絡嵌入結果。Wang 等提出Edge2vec 算法[10]，改進基于節點的網絡嵌入方法，通過網絡中的邊來獲得網絡嵌入結果。由于網絡結構信息稀疏，單一利用網絡結構信息的網絡嵌入方法在大型稀疏網絡中實驗效果并不是很好。而網絡屬性信息可以彌補結構信息稀疏的問題，因此近幾年，基于網絡結構信息和屬性信息相結合的網絡嵌入方法相繼被提出。

基于網絡結構信息和屬性信息相結合的網絡嵌入方法目的是融入屬性信息以獲得更好的網絡嵌入結果。Yang等提出基于豐富文本信息的網絡表示學習算法（network representation learning with rich text information，TADW）[11]，首次將文本信息特征引入了網絡嵌入，完善了以往僅依靠結構信息的網絡嵌入方法。Tu等提出用于關系模型的上下文感知網絡嵌入算法（context-aware network embedding for relation modeling，CANE）[12]，認為網絡中節點對于不同的鄰居節點具有不同的交互關系。該算法首先利用卷積神經網絡（convolutional neural network，CNN）對節點信息進行嵌入，之后對于鄰居節點進行不同程度的嵌入，有效解決網絡傳播中“中間人”問題。Huang等提出了加速網絡嵌入算法（accelerated attributed network embedding，AANE）[13]，通過聯合矩陣分解獲得屬性網絡的嵌入結果。Bandyopadhyay 等提出了基于離群點檢測的屬性網絡嵌入算法（outlier aware network embedding for attributed networks，ONE）[14]，減小異常節點對于屬性網絡嵌入結果的影響。Hong等提出保留結構和屬性信息的深度屬性網絡嵌入算法（deep attributed network embedding by preserving structure and attribute information，DANE）[15]，利用堆疊去噪自動編碼器學習網絡高階結構信息和屬性信息。實驗證明，該算法取得了良好的效果。Nozza等提出了約束深度屬性圖嵌入算法（constrained deep attributed graph embedding，CAGE）[16]，利用節點低階結構信息和屬性信息相互制約獲得更好的網絡嵌入效果。

盡管現有的網絡嵌入方法在不同場景下展示了其有效性，但是本文在研究中發現，現有網絡嵌入方法應用于社交網絡中仍存在以下幾個問題：

（1）社交網絡高階結構信息利用不足。高階結構信息可以充分體現節點間的連通能力，因此多數基于結構的網絡嵌入方法都融入了網絡高階結構信息來提高網絡嵌入效果。但是這些方法并沒有去除環狀路徑和大度節點的影響，使得各節點與大度節點具有更高的相似性，網絡嵌入效果不理想。

（2）未有效處理社交網絡屬性信息中存在的噪音。節點的屬性信息可以彌補網絡結構數據稀疏的問題，但是社交網絡中節點屬性信息大多基于用戶隨意設定的興趣愛好，具有很大的主觀性和不準確性并且屬性網絡中具有很多的異常節點。多數基于網絡結構信息和屬性信息相結合的網絡嵌入方法并沒有消除屬性網絡中存在的噪音，在社交網絡中實驗效果不盡如人意。

為了解決上述問題，本文提出了一種融合節點屬性和無環路徑的社交網絡嵌入方法（social network embedding method combining loop-free path and attributes network embedding，LFNE）。本文的主要貢獻有以下幾點：

（1）給出計算社交網絡節點間六階內無環路徑數量的數學表達式并提出基于節點間無環路徑的相似性度量指標（similarity metrics based on loop-free path，SLP），消除環狀路徑、大度節點的影響，使得相似性指標可以更好地融合社交網絡節點間的高階路徑信息，計算結果更加準確。

（2）結合SLP 指標改進社交網絡節點屬性相似度，充分考慮節點結構信息和屬性信息的相關性，降低社交網絡中節點屬性信息存在的噪音。

（3）將各階社交網絡無環路徑結構信息和節點屬性信息融合，通過堆疊降噪自動編碼器學習節點低維特征表示，不僅可以學習網絡中數據分布情況，而且可以獲得網絡高度非線性特征。公開數據集上的節點分類和鏈路預測實驗結果表示，LFNE算法可以獲得更加全面的節點特征向量。

1 相關工作

1.1 網絡基礎知識

給定一個復雜網絡G=(V,E)來表示社交網絡，網絡中個體的集合用節點集V={1,2,…,N} 來表示，|V(G)|=N，網絡中個體的聯系用邊集E={e=(i,j)|1 ≤i,j≤N，i≠j}來表示，用i-j表示邊e=(i,j)。

記網絡G的鄰接矩陣A∈RN×N，定義為：

記網絡G的屬性矩陣為W∈RN×F，F代表屬性元素的個數。

令S(i)={j|j∈V(i≠j)∧(i,j)∈E}，稱S(i)為節點i的鄰居節點。

令di=|j|j∈V(i≠j)∧(i,j)∈E|，其中，集合內元素的個數用|*|表示，稱di為節點i的度。

1.2 節點結構相似性指標

經典節點結構相似性度量指標主要是基于節點的公共鄰居，例如CN 指標（common neighbours index）[17]、Salton指標[18]、HPI指標（hub promoted index）[19]、LHN-I 指標（Leicht-Holme-Newman index）[20]等，此類指標最主要的缺陷是沒有關注節點間的高階結構關系。

基于節點間連通能力的相似性度量指標在考慮了節點低階結構信息的同時，也融入了節點間高階結構信息，準確性更高，例如Katz 指標[21]、LP 指標（local path index）[22]、LS指標（local similarity index）[23]。

Katz 指標利用節點各階連通路徑來衡量節點間相似性，Katz 指標對于節點間高階路徑賦予更小的權重，對于節點間的低階路徑賦予更大的權值。在Katz指標的基礎上，LP指標、LS指標被提出。

基于節點間連通能力的相似性度量指標雖然將節點的高階結構信息考慮在內，但是節點各階路徑中存在環狀路徑，尤其是節點間的高階路徑中存在大量的環狀路徑，并且大度節點會經常出現在環狀路徑中，使得各個節點與大度節點具有更高的相似性，導致Katz指標、LP指標、LS指標不能準確衡量節點間連通能力，指標度量性能差。

1.3 無環路徑算法

去除節點各階路徑中的環狀路徑，使得節點連通路徑中各個節點互不相同，可以有效降低各個節點對于大度節點的依賴性，因此可以通過節點間無環路徑來衡量節點間的連通能力。

Wu等[24]引入一個中間矩陣來計算節點間各階無環路徑數量。對于路徑階數小于等于5的情況，其給出準確的數學表達式。對于路徑階數大于等于6 的情況，由于6階以上路徑的復雜性，Chen等未能給出準確的數學表達式。

給定一個網絡G的鄰接矩陣A，Ak表示鄰接矩陣A的k次冪。Ak給出了網絡G中任意節點間各階路徑的數目（包含環狀路徑）。定義Pk表示網絡G中各階路徑中無環路徑的數量。

對于網絡的一階路徑，即為網絡的鄰接矩陣，不存在環狀路徑，因此A1=P1。

對于網絡的二階路徑，即為節點間的共同鄰居，也不存在環狀路徑，因此A2=P2。

對于網絡的三階及以上路徑，節點間路徑中便可能會出現環狀路徑，為了便于計算三階及以上節點間無環路徑數量，Chen等引入了中間矩陣Qk。Qk表示在k-1 階無環路徑后加上一階路徑組成的k階路徑，定義如式（2）和式（3）所示：

同理，可以求得五階無環路徑數量，定義如下：

2 六階無環路徑算法

Lü等證明了基于節點間連通能力的相似性度量指標中路徑的長度與網絡節點間平均路徑長度呈正相關[25]，因此基于節點間連通能力的相似性度量指標中路徑的長度應近似于網絡節點間平均路徑長度。據數據分析報告，社交平臺Twitter 中用戶間平均路徑長度為4.67，在Facebook 中為4.74，因此當前社交網絡中節點平均路徑長度近似為5。依據Lü等證明的理論，社交網絡中基于節點間連通能力的相似性度量指標的路徑長度應取值為5，因此為了使得基于節點間連通能力的相似性度量指標可以更好地融合社交網絡節點間的高階結構信息，需計算節點間六階（路徑長度為5）無環路徑數量。然而Chen 等[24]只給出了計算節點間五階（路徑長度為4）內無環路徑數量的數學表達式，未能給出計算節點間六階（路徑長度為5）無環路徑數量的數學表達式，因此本文給出計算節點間六階（路徑長度為5）無環路徑數量的準確數學表達式。

圖1 六階無環路徑Fig.1 Loop-free 6-hop paths

3 LFNE算法

為了消除社交網絡中環狀路徑、大度節點對于節點結構相似度的影響，降低網絡屬性信息存在的噪音，使得網絡嵌入方法可以更好地融合社交網絡高階結構信息和屬性信息，本文提出一種融合節點屬性和無環路徑的社交網絡嵌入方法LFNE。LFNE主要包括4個步驟：根據基于節點間無環路徑的相似性度量指標SLP 計算社交網絡節點間的結構相似度生成結構概率矩陣；結合社交網絡節點結構相似度計算節點間屬性相似度生成屬性概率矩陣；構建結構-屬性概率矩陣；構建堆疊降噪自動編碼器對矩陣進行特征提取，獲取網絡的低維特征表示。

3.1 節點結構相似性計算

為了使得相似性指標可以更好地融合社交網絡高階結構信息，本文提出了基于節點間無環路徑的相似性度量指標SLP，定義如下：

其中，路徑長度K由基于區域中心點距離（centers distance of zone，CDZ）[26]的最短路徑算法計算網絡平均路徑長度確定，是節點間k階無環路徑數量，β(k)是減函數。在社交網絡中，兩個節點直接產生連接或者連通路徑越短，則兩個節點間的相似度會越高，聯系越緊密。SLP指標中相較于高階的節點路徑信息會更多考慮低階的節點路徑信息。因此，引入權重衰減函數，當節點間路徑增加時，路徑權重會相應減小。本文使用指數函數作為SLP 指標的權重衰減函數，權重衰減函數如式（8）所示：

其中，ω為權重衰減函數因子，ω∈(0,1)。借助權重衰減函數可以使得SLP 指標在融入節點高階結構信息的同時會更多考慮節點低階結構信息。

接著，對SLP 指標下節點相似度進行歸一化處理，獲得節點間結構概率矩陣，節點i和節點j的結構概率定義如下：

3.2 節點屬性相似度計算

給定一個網絡G的屬性網絡W∈RN×F，F是屬性元素個數。通過余弦相似度公式將屬性網絡W轉換成節點屬性概率矩陣C，節點i和節點j的屬性概率定義如下：

多數基于網絡結構信息和屬性信息相結合的網絡嵌入方法應用于社交網絡中的實驗效果并不理想，分析原因是雖然節點的屬性信息可以很好地彌補網絡結構數據稀疏的問題，但是社交網絡中節點屬性信息大多基于用戶隨意設定的興趣愛好，具有很大的主觀性和不準確性，存在噪音，如圖2所示。

圖2 屬性網絡噪音示意圖Fig.2 Schematic diagram of attribute network noise

節點v1和節點v7在網絡結構上相距甚遠，在SLP 指標下，兩節點的結構相似度為0，節點v7對于節點v1是相對孤立點，但是節點v1和v7的屬性信息相似，在先前的網絡嵌入模型，沒有考慮節點結構信息和屬性信息的相關性，會認為這兩個節點具有相似的網絡嵌入表示。而實際上節點v7對于節點v1而言是屬性異常節點，存在屬性信息噪音，兩節點具有相似的網絡嵌入表示可能性相對較小，因此降低節點屬性信息中的噪音對于社交網絡嵌入具有重要意義。本文結合SLP 指標改進社交網絡節點屬性相似度計算方法，充分考慮節點結構信息和屬性信息的相關性，降低社交網絡中節點屬性信息存在的噪音，解決大多數模型沒有考慮節點結構信息和屬性信息相關性的問題。本文改進的屬性相似性度量指標定義如下：

其中，α的取值范圍在[0,1]之間，用于判斷節點j是否為節點i網絡平均路徑長度內可到達的節點，若節點j不是節點i網絡平均路徑長度內可以到達的節點，則兩個節點的連通性較差，給予兩個節點間屬性相似度相對更小的權重。通過改進后的節點屬性相似度計算方式可以有效降低屬性網絡中存在的噪音。

對節點屬性相似度Bij進行歸一化處理，獲得節點屬性概率矩陣，節點i和j的屬性概率定義如下：

3.3 節點結構-屬性相似度矩陣

給定一個網絡G，節點結構-屬性相似度矩陣X∈RN×N定義如下：

其中，λ的取值范圍在[0,1]之間。λ用來平衡節點結構相似度和屬性相似度對于節點相似度的影響程度。當λ為0時，節點相似度僅受到屬性相似度的影響，當λ為1 時，節點相似度僅受到結構相似度的影響。λ的取值越大，節點相似度受結構相似度的影響越大。相應的，λ的取值越小，節點相似度受屬性相似度的影響越大。

當獲得節點的高維特征表示后，需要通過降維的方式獲得低維特征表示，捕獲高度非線性的網絡結構。本文通過堆疊降噪自動編碼器對節點結構-屬性概率矩陣進行降維，獲得低維特征表示。

3.4 堆疊降噪自動編碼器

自動編碼器可以高效提取數據特征，已廣泛用于多個領域的表示學習任務中。傳統自動編碼器由輸入層、隱藏層、輸出層三部分組成。通過編碼器將輸入層數據映射到隱藏層空間，然后通過解碼器將隱藏層空間數據映射成輸出層的重構數據，通過減小輸入數據和重構數據的誤差來達到特征提取的目的。降噪自動編碼器是基于傳統自動編碼器的一個變形。降噪自動編碼器通過噪聲污染訓練數據，并通過訓練來預測沒有污染的原始數據，可以很好地增強自動編碼器的魯棒性。降噪自動編碼器首先將原始輸入數據xi∈RN中的一些單元置零加入噪音得到∈RN，然后通過編碼器部分將映射到隱藏層空間得到hi∈Rd，之后通過解碼器部分將hi映射成重構數據zi∈RN。通過優化度量xi和zi之間的損失函數來訓練降噪自動編碼器，定義如下：

其中，W和b是編碼器的權重矩陣和偏置向量，W′和b′是解碼器的權重矩陣和偏置向量。f(·)是激活函數，本文中采用ReLU函數，定義如下：

損失函數采用交叉熵函數，定義如下：

為了獲得輸入數據更好的低維特征表示，本文使用堆疊降噪自動編碼器，構建一個完整的深度降噪自動編碼器來學習輸入數據的低維特征表示。堆疊降噪自動編碼器由若干個降噪自動編碼器組成。在堆疊降噪自動編碼器的訓練過程中，每當訓練完一個降噪自動編碼器則去除其輸出層及相關的參數，將隱藏層作為下一個降噪自動編碼器的輸入，依次連接訓練每一個降噪自動編碼器，形成一個堆疊降噪自動編碼器。最后一個降噪自動編碼器隱藏層表示即為輸入數據的低維特征表示。

3.5 算法流程

融合節點屬性和無環路徑的社交網絡嵌入方法LFNE具體方法流程見算法1。

算法1LFNE算法

輸入：社交網絡G，網絡鄰接矩陣A，節點屬性矩陣W以及設置相關參數。

輸出：低維特征矩陣Z。

首先，LFNE 算法的輸入部分包括三部分：社交網絡G，網絡鄰接矩陣A，節點屬性矩陣W；計算結構-屬性概率轉移矩陣所需參數，包括路徑權重參數β，節點間路徑長度k，屬性相似度權重參數α，結構-屬性平衡參數λ；堆疊降噪自動編碼器特征提取階段所需參數，包括堆疊降噪自動編碼器個數n，維度d，訓練次數m。

算法1的第1行～第6行，首先通過矩陣A得到節點間基于無環路徑的相似度Sslp，捕獲社交網絡高階結構相似性，然后生成矩陣H。接下來通過矩陣W和Sslp得到節點間屬性相似度B，充分利用社交網絡結構信息和屬性信息的相關性，然后生成矩陣M。最后，通過矩陣H和M得到矩陣X。

算法1 的第7 行～第11 行，構建了一個堆疊降噪自動編碼器，輸入矩陣X，學習X的低維特征表示，循環執行m次，最終得到X的低維特征矩陣Z。

3.6 時間復雜度

LFNE 算法中計算社交網絡節點間的結構相似度需要通過無環路徑算法計算節點間無環路徑數量。在計算k階無環路徑數量時需知道k-1 階無環路徑的數量來根據式（5）計算Qk。因此計算k階無環路徑時需要計算k階前每一階無環路徑的數量。Qk的計算是一個矩陣相乘的計算，目前計算兩個大小為n×n的矩陣相乘的時間復雜度為O(n2.372)[27]，因此計算社交網絡節點間的結構相似度的總時間復雜度為O((1+2+…+k)N2.372)=O(0.5(1+k)kN2.372)≈O(k2N2.372)，N為網絡中節點數量。計算節點間屬性相似度和構建結構-屬性概率矩陣的時間復雜度為O(N)。對于構建堆疊降噪自動編碼器獲得網絡的低維特征表示部分，時間復雜度為O(d|E|)，其中d為節點特征向量維度，|E|為網絡中邊的數量。由于復雜網絡通常是稀疏的，|E|?N2.372，LFNE 算法的時間復雜度為O(k2N2.372)。

4 實驗

為測試本文算法的可行性與有效性，將LFNE算法在3 個真實社交網絡數據集進行性能評價。首先介紹實驗數據集、對比算法、實驗評價指標和實驗環境，之后進行參數分析實驗，最后進行節點分類實驗和鏈路預測實驗。

4.1 實驗數據集

實驗中所用數據集具體信息如表1所示。

表1 真實網絡數據集基本信息Table 1 Basic information of real network datasets

BlogCatalog[13]：一個在線博客社交網絡。網絡由5 196名博主和博主間關注產生的交互關系組成。博主發布的博客關鍵詞作為博主的屬性信息。根據博主的興趣愛好，將博主分為6組。

Flickr[28]：一個在線圖片分享網站。該網絡是一個由7 575 名用戶和用戶間共享照片產生的交互關系組成的社交網絡。用戶發布的圖像標簽信息和用戶的個人愛好作為用戶的屬性信息。根據加入的預定義組，將用戶分為9組。

Email[28]：歐洲研究機構成員電子郵件通信網絡。該網絡由1 005 名研究人員和研究人員間通過電子郵件產生的交互組成的社交網絡。研究人員的屬性信息對應所屬部門。

4.2 對比算法

將LFNE 算法與近幾年代表性算法進行對比實驗，其中DeepWalk[2]、node2vec[6]、DNGR[7]、SDNE[8]是基于網絡結構信息的網絡嵌入方法，TADW[11]、DANE[15]是基于網絡結構信息和屬性信息相結合的網絡嵌入方法。

DeepWalk：通過隨機游走方式獲得節點的序列表示，然后通過word2vec模型[3]獲得基于節點上下文結構的嵌入表示。

node2vec：結合深度優先搜索和廣度優先搜索優化了隨機游走序列生成方式，然后通過最大化保留節點網絡鄰域的可能性學習節點表示。

DNGR：通過隨機沖浪獲得節點高階結構信息，然后通過棧式降噪自動編碼器進行網絡嵌入。

SDNE：通過深度自動編碼器捕捉高度非線性的網絡結構，然后通過聯合優化節點一階和二階相似性保留網絡局部和全局結構特征來獲得節點的嵌入結果。

TADW：通過矩陣分解學習網絡結構和屬性信息獲得節點的低維特征表示。

DANE：通過個性化隨機游走模型學習網絡高階結構信息和屬性信息獲得全局信息矩陣，然后通過深度自動編碼器學習節點全局信息獲得節點的嵌入表示。

4.3 實驗評價指標和實驗環境

本文中使用的實驗評價指標分別是Micro-F1[29]、Macro-F1[29]和AUC（area under the curve）[30]。Micro-F1 指標表示對于數據集建立全局混淆矩陣，計算相應的指標。Macro-F1指標表示對于數據集各個標簽建立混淆矩陣，計算各標簽下的Micro-F1 指標的算數平均值。Micro-F1和Macro-F1指標常用作評價節點分類任務效果，值越高，實驗效果越好。Micro-F1和Macro-F1指標定義如下：

其中，P表示精確率，R表示召回率，M是標簽數量。TPi表示將實際標簽為i的樣本預測為標簽i的樣本數量；FPi表示將實際標簽為非i的樣本預測為標簽i的樣本數量；FNi表示將實際標簽為i的樣本預測為非i標簽的樣本數量。

AUC指標表示ROC（receiver operating characteristic curve）曲線下所圍成的面積大小，常用作鏈路預測實驗的評價指標。在鏈路預測實驗中體現為每次從網絡中不存在邊的集合和測試集邊的集合中各自隨機選擇一條邊進行比較，后者比前者分數高的概率。定義如下：

其中，n表示比較的次數，n′表示測試集中邊鏈路預測值高于網絡中不存在邊的次數，n″表示測試集中邊鏈路預測值等于不存在邊的次數。一般認為，AUC的值越高，算法鏈路預測效果越好。

本文的實驗環境為：處理器為Intel?CoreTMi7-8750H CPU@2.20 GHz，內存為16 GB，操作系統為Windows 10 64 bit。

4.4 參數設置

本文算法使用堆疊降噪自動編碼器學習節點低維特征表示。為了使堆疊自動降噪自動編碼器可以更好地獲取節點低維特征表示，對于不同數據集采用不同的自動編碼器結構。各數據集對應的自動編碼器結構如表2所示。

表2 不同數據集下堆疊降噪自動編碼器結構Table 2 Structure of stacked denoising autoencoder under different datasets

實驗中采用的對比算法輸出的節點向量維度和本文算法輸出的向量維度一致。本文算法中SLP 指標參數ω參照文獻[24]取值為0.3。堆疊降噪自動編碼器模型使用Adam優化器進行訓練，迭代次數設置為500，學習率為0.002。本文中需要被討論的參數是節點間路徑長度k、屬性相似度權重參數α和結構-屬性平衡參數λ。

節點間路徑長度k體現了節點間的連通性，節點間路徑長度過低會使得算法僅考慮節點局部結構信息，不能充分利用網絡結構信息，導致節點相似度衡量不準確。而節點間路徑長度過高會使得節點間連通路徑間存在大量結構噪音信息。因此，確定合理的節點間路徑長度，對于衡量節點間相似度至關重要。為充分體現節點間路徑長度對于LFNE 算法的影響，實驗中節點間路徑長度k取值為1 至10，步長為1。六階內節點間無環路徑數量采用本文算法進行計算，六階以上節點間無環路徑數量采用文獻[24]中的計算方法進行近似計算。節點間路徑長度k影響實驗中采用BlogCatalog、Flickr、Email 三個數據集進行鏈路預測任務，評價指標是AUC。實驗中隨機選取10%的連接數據和未連接數據作為測試，10%的連接數據作為驗證，其余數據用作訓練。實驗結果如圖3所示。

圖3 參數k 對算法的影響Fig.3 Influence of parameter k on algorithm

實驗結果表明，在BlogCatalog和Flickr大型社交網絡數據集中，路徑長度取值為6時，AUC值最高，鏈路預測效果最好，可以證明節點間六階路徑能充分體現大型社交網絡中節點間的連通性，可以獲得較好的實驗效果。而對于Email數據集，路徑長度取值為4時，鏈路預測效果最好。分析原因是節點間最佳路徑距離與節點間平均距離呈正相關，由于Email數據集網絡規模較小，節點間平均最短距離相對較小，故k取值較小時實驗效果最好。

屬性相似度權重參數α用于降低社交網絡中節點屬性信息存在的噪音，當α取值過高時，會使得網絡節點中存在大量的屬性噪音，當α取值過低時，不能充分考慮節點屬性信息，因此確定合理的屬性相似度權重參數α可以提高社交網絡嵌入效果。實驗中，α取0至1，步長為0.1，采用BlogCatalog、Flickr兩個數據集進行節點分類任務，評價指標是Micro-F1分數和Macro-F1 分數，隨機選取30%節點作為標記節點進行訓練，其余節點用作測試。實驗結果如圖4所示。

圖4 參數α 對算法的影響Fig.4 Influence of parameter α on algorithm

實驗結果表明，當屬性相似度權重參數α取值為0.3時，在BlogCatalog、Flickr數據集上節點分類效果最好。當參數從0.3 至1.0 時，屬性信息存在的噪音影響越來越大，節點分類效果越來越差，可見降低節點屬性信息中存在的噪音確實可以有效提高算法網絡嵌入能力。而當參數小于0.3時，未能充分考慮節點屬性信息，節點分類效果也變差。

結構-屬性平衡參數λ用于平衡節點間結構相似度和屬性相似度。實驗中，λ取0.5 至1.0，步長為0.1，采用BlogCatalog、Flickr 兩個數據集進行節點分類任務，評價指標是Micro-F1分數和Macro-F1分數，隨機選取10%節點作為標記節點進行訓練，其余節點用作測試。實驗結果如圖5所示。

圖5 參數λ 對算法的影響Fig.5 Influence of parameter λ on algorithm

實驗結果表明，當結構-屬性平衡參數λ取值為0.7 時，在BlogCatalog、Flickr 兩個數據集上節點分類效果最好。當參數從0.7 至1.0 時，節點相似度受節點屬性相似度影響越來越小，節點分類效果越來越差，可見節點屬性信息確實可以有效提高算法網絡嵌入能力。而當參數小于0.7時，節點相似度受節點結構相似度影響越來越小，節點分類效果也變差。因此，當λ取值為0.7時效果最好。本文在后續的實驗中，節點間路徑長度k由CDZ 算法[26]計算網絡平均路徑長度確定，屬性相似度權重參數α取值為0.3，結構-屬性平衡參數λ取值為0.7。

4.5 節點分類

節點分類是社交網絡分析一項重要任務，通過已被標記的節點來預測網絡中未被標記的節點標簽種類，常用于評價網絡嵌入方法的性能。本文節點分類實驗選取的數據集是BlogCatalog 和Flickr 數據集，評價指標是Micro-F1 分數和Macro-F1 分數。實驗中首先通過各算法學習節點的低維特征表示，然后隨機抽取10%至90%（步長為20%）節點作為標記節點進行訓練，其余節點用作測試。實驗結果如表3～表6所示。

表3 BlogCatalog數據集節點分類Micro-F1分數Table 3 Micro-F1 of node classification on BlogCatalog dataset

表4 BlogCatalog數據集節點分類Macro-F1分數Table 4 Macro-F1 of node classification on BlogCatalog dataset

表5 Flickr數據集節點分類Micro-F1分數Table 5 Micro-F1 of node classification on Flickr dataset

表6 Flickr數據集節點分類Macro-F1分數Table 6 Macro-F1 of node classification on Flickr dataset

根據實驗結果，LFNE算法學習出的節點低維特征向量在各數據集上相較于其他算法可以獲得更好的節點分類效果。TADW、DANE、LFNE等融合節點屬性的網絡嵌入方法相較于DNGR、SDNE等僅考慮節點結構信息的網絡嵌入方法取得了更好的節點分類效果，在各個數據集上都有較大幅度的提升，可以證明屬性信息可以改進社交網絡的網絡嵌入學習效果。DANE 算法融入了節點間高階結構信息，而TADW 算法僅考慮節點低階結構信息，實驗結果表明DANE 算法相較于TADW 算法在BlogCatalog、Flickr 數據集上節點分類Micro-F1 分數分別平均提升1.5%、1.8%。可以證明高階結構信息可以改進社交網絡的網絡嵌入效果。由于DANE算法并沒有消除環狀路徑和大度節點對于結構信息的影響，提升效果并不顯著。而LFNE 算法相較于DANE 算法在BlogCatalog、Flickr 數據集上節點分類Micro-F1 分數平均提升4.3%、4.1%，Macro-F1分數平均提升4.5%、3.9%，可以證明消除環狀路徑和大度節點可以使得算法更好地融合高階結構信息，獲得更好的網絡嵌入效果。

4.6 鏈路預測

鏈路預測亦是社交網絡分析的一項重要任務，根據已有的網絡連接預測節點間潛在或者未來的連接過程。鏈路預測也常用于評價網絡嵌入學習方法的性能。本節鏈路預測實驗選取的數據集是BlogCatalog、Flickr和Email，評價指標是AUC。實驗中隨機選取10%的連接數據和未連接數據作為測試，10%的連接數據作為驗證，其余數據用作訓練。實驗結果如圖6所示。

圖6 不同算法鏈路預測AUC指標結果Fig.6 AUC index results of link prediction with different algorithms

根據實驗結果，TADW 和DANE 等融合結構和屬性信息的網絡嵌入方法相較于單一融合結構信息的SDNE、DNGR算法在BlogCatalog、Email并沒有取得更好的鏈路預測效果。在BlogCatalog 數據集上TADW 算法的鏈路預測效果最差，DNGR 算法相較于TADW 算法AUC 指標提升30.2%，可以證明社交網絡中屬性信息確實存在噪音。而本文提出的LFNE 算法在各個數據集上都取得了不錯的鏈路預測效果，在BlogCatalog、Flickr、Email 數據集上相較于DNGR 算法AUC 指標分別提升5.2%、15.9%、3.9%。實驗表明，LFNE算法充分考慮節點屬性信息和結構信息的相關性，降低社交網絡屬性信息存在的噪音，可以獲得更好的鏈路預測效果。

5 結束語

本文提出了一種融合節點屬性和無環路徑的社交網絡嵌入方法LFNE。該算法可以消除環狀路徑和大度節點對于節點相似性的影響并且有效降低節點屬性信息中存在的噪音，提高社交網絡嵌入效果。實驗結果表明，該算法具有可行性和有效性。但是本文仍有幾個方面不足：首先，對于無環路徑數量計算方面，本文雖然拓展到了六階無環路徑數量計算，但是并沒有找到一個普適性的算法可以計算更高階的無環路徑數量。其次，對于網絡嵌入方面，本文考慮的是節點的結構信息和屬性信息，并沒有考慮節點之間的交互信息。下一步將嘗試找到一個普適性的算法計算更高階的無環路徑數量，提高無環路徑算法的可拓展性，并嘗試將節點間的交互信息融入網絡嵌入中獲得更好的網絡嵌入效果。

附錄1