王本鈺，顧益軍，彭舒凡

中國(guó)人民公安大學(xué) 信息網(wǎng)絡(luò)安全學(xué)院，北京100032

近年來，隨著互聯(lián)網(wǎng)技術(shù)的高速發(fā)展，社交網(wǎng)絡(luò)的規(guī)模不斷增加，社交網(wǎng)絡(luò)分析任務(wù)也變得愈發(fā)重要，例如節(jié)點(diǎn)分類、鏈路預(yù)測(cè)等。節(jié)點(diǎn)分類任務(wù)可以對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行合理的劃分，在現(xiàn)實(shí)生活中具有重要的應(yīng)用價(jià)值，例如在社交平臺(tái)中，通過用戶的類別標(biāo)簽向用戶推薦好友；在智能廣告中，向可能感興趣的用戶精準(zhǔn)投放廣告。鏈路預(yù)測(cè)任務(wù)可以有效分析網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，預(yù)測(cè)網(wǎng)絡(luò)丟失的邊或者未來可能出現(xiàn)的邊，在社交網(wǎng)絡(luò)上應(yīng)用前景廣闊，例如社交平臺(tái)用戶拓展、電商營(yíng)銷等。各種各樣新穎的技術(shù)被用在社交網(wǎng)絡(luò)分析中來挖掘用戶潛在屬性，網(wǎng)絡(luò)嵌入[1]就是其中一種。

網(wǎng)絡(luò)嵌入旨在將高維稀疏數(shù)據(jù)映射到低維稠密向量空間，提取數(shù)據(jù)低維特征，以便于基于向量的機(jī)器學(xué)習(xí)方法進(jìn)行下游網(wǎng)絡(luò)分析任務(wù)。目前主流的網(wǎng)絡(luò)嵌入方法可以分為基于網(wǎng)絡(luò)結(jié)構(gòu)信息的網(wǎng)絡(luò)嵌入方法和基于網(wǎng)絡(luò)結(jié)構(gòu)信息和屬性信息相結(jié)合的網(wǎng)絡(luò)嵌入方法。

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

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

盡管現(xiàn)有的網(wǎng)絡(luò)嵌入方法在不同場(chǎng)景下展示了其有效性，但是本文在研究中發(fā)現(xiàn)，現(xiàn)有網(wǎng)絡(luò)嵌入方法應(yīng)用于社交網(wǎng)絡(luò)中仍存在以下幾個(gè)問題：

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

（2）未有效處理社交網(wǎng)絡(luò)屬性信息中存在的噪音。節(jié)點(diǎn)的屬性信息可以彌補(bǔ)網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)稀疏的問題，但是社交網(wǎng)絡(luò)中節(jié)點(diǎn)屬性信息大多基于用戶隨意設(shè)定的興趣愛好，具有很大的主觀性和不準(zhǔn)確性并且屬性網(wǎng)絡(luò)中具有很多的異常節(jié)點(diǎn)。多數(shù)基于網(wǎng)絡(luò)結(jié)構(gòu)信息和屬性信息相結(jié)合的網(wǎng)絡(luò)嵌入方法并沒有消除屬性網(wǎng)絡(luò)中存在的噪音，在社交網(wǎng)絡(luò)中實(shí)驗(yàn)效果不盡如人意。

為了解決上述問題，本文提出了一種融合節(jié)點(diǎn)屬性和無環(huán)路徑的社交網(wǎng)絡(luò)嵌入方法（social network embedding method combining loop-free path and attributes network embedding，LFNE）。本文的主要貢獻(xiàn)有以下幾點(diǎn)：

（1）給出計(jì)算社交網(wǎng)絡(luò)節(jié)點(diǎn)間六階內(nèi)無環(huán)路徑數(shù)量的數(shù)學(xué)表達(dá)式并提出基于節(jié)點(diǎn)間無環(huán)路徑的相似性度量指標(biāo)（similarity metrics based on loop-free path，SLP），消除環(huán)狀路徑、大度節(jié)點(diǎn)的影響，使得相似性指標(biāo)可以更好地融合社交網(wǎng)絡(luò)節(jié)點(diǎn)間的高階路徑信息，計(jì)算結(jié)果更加準(zhǔn)確。

（2）結(jié)合SLP 指標(biāo)改進(jìn)社交網(wǎng)絡(luò)節(jié)點(diǎn)屬性相似度，充分考慮節(jié)點(diǎn)結(jié)構(gòu)信息和屬性信息的相關(guān)性，降低社交網(wǎng)絡(luò)中節(jié)點(diǎn)屬性信息存在的噪音。

（3）將各階社交網(wǎng)絡(luò)無環(huán)路徑結(jié)構(gòu)信息和節(jié)點(diǎn)屬性信息融合，通過堆疊降噪自動(dòng)編碼器學(xué)習(xí)節(jié)點(diǎn)低維特征表示，不僅可以學(xué)習(xí)網(wǎng)絡(luò)中數(shù)據(jù)分布情況，而且可以獲得網(wǎng)絡(luò)高度非線性特征。公開數(shù)據(jù)集上的節(jié)點(diǎn)分類和鏈路預(yù)測(cè)實(shí)驗(yàn)結(jié)果表示，LFNE算法可以獲得更加全面的節(jié)點(diǎn)特征向量。

1 相關(guān)工作

1.1 網(wǎng)絡(luò)基礎(chǔ)知識(shí)

給定一個(gè)復(fù)雜網(wǎng)絡(luò)G=(V,E)來表示社交網(wǎng)絡(luò)，網(wǎng)絡(luò)中個(gè)體的集合用節(jié)點(diǎn)集V={1,2,…,N} 來表示，|V(G)|=N，網(wǎng)絡(luò)中個(gè)體的聯(lián)系用邊集E={e=(i,j)|1 ≤i,j≤N，i≠j}來表示，用i-j表示邊e=(i,j)。

記網(wǎng)絡(luò)G的鄰接矩陣A∈RN×N，定義為：

記網(wǎng)絡(luò)G的屬性矩陣為W∈RN×F，F(xiàn)代表屬性元素的個(gè)數(shù)。

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

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

1.2 節(jié)點(diǎn)結(jié)構(gòu)相似性指標(biāo)

經(jīng)典節(jié)點(diǎn)結(jié)構(gòu)相似性度量指標(biāo)主要是基于節(jié)點(diǎn)的公共鄰居，例如CN 指標(biāo)（common neighbours index）[17]、Salton指標(biāo)[18]、HPI指標(biāo)（hub promoted index）[19]、LHN-I 指標(biāo)（Leicht-Holme-Newman index）[20]等，此類指標(biāo)最主要的缺陷是沒有關(guān)注節(jié)點(diǎn)間的高階結(jié)構(gòu)關(guān)系。

基于節(jié)點(diǎn)間連通能力的相似性度量指標(biāo)在考慮了節(jié)點(diǎn)低階結(jié)構(gòu)信息的同時(shí)，也融入了節(jié)點(diǎn)間高階結(jié)構(gòu)信息，準(zhǔn)確性更高，例如Katz 指標(biāo)[21]、LP 指標(biāo)（local path index）[22]、LS指標(biāo)（local similarity index）[23]。

Katz 指標(biāo)利用節(jié)點(diǎn)各階連通路徑來衡量節(jié)點(diǎn)間相似性，Katz 指標(biāo)對(duì)于節(jié)點(diǎn)間高階路徑賦予更小的權(quán)重，對(duì)于節(jié)點(diǎn)間的低階路徑賦予更大的權(quán)值。在Katz指標(biāo)的基礎(chǔ)上，LP指標(biāo)、LS指標(biāo)被提出。

基于節(jié)點(diǎn)間連通能力的相似性度量指標(biāo)雖然將節(jié)點(diǎn)的高階結(jié)構(gòu)信息考慮在內(nèi)，但是節(jié)點(diǎn)各階路徑中存在環(huán)狀路徑，尤其是節(jié)點(diǎn)間的高階路徑中存在大量的環(huán)狀路徑，并且大度節(jié)點(diǎn)會(huì)經(jīng)常出現(xiàn)在環(huán)狀路徑中，使得各個(gè)節(jié)點(diǎn)與大度節(jié)點(diǎn)具有更高的相似性，導(dǎo)致Katz指標(biāo)、LP指標(biāo)、LS指標(biāo)不能準(zhǔn)確衡量節(jié)點(diǎn)間連通能力，指標(biāo)度量性能差。

1.3 無環(huán)路徑算法

去除節(jié)點(diǎn)各階路徑中的環(huán)狀路徑，使得節(jié)點(diǎn)連通路徑中各個(gè)節(jié)點(diǎn)互不相同，可以有效降低各個(gè)節(jié)點(diǎn)對(duì)于大度節(jié)點(diǎn)的依賴性，因此可以通過節(jié)點(diǎn)間無環(huán)路徑來衡量節(jié)點(diǎn)間的連通能力。

Wu等[24]引入一個(gè)中間矩陣來計(jì)算節(jié)點(diǎn)間各階無環(huán)路徑數(shù)量。對(duì)于路徑階數(shù)小于等于5的情況，其給出準(zhǔn)確的數(shù)學(xué)表達(dá)式。對(duì)于路徑階數(shù)大于等于6 的情況，由于6階以上路徑的復(fù)雜性，Chen等未能給出準(zhǔn)確的數(shù)學(xué)表達(dá)式。

給定一個(gè)網(wǎng)絡(luò)G的鄰接矩陣A，Ak表示鄰接矩陣A的k次冪。Ak給出了網(wǎng)絡(luò)G中任意節(jié)點(diǎn)間各階路徑的數(shù)目（包含環(huán)狀路徑）。定義Pk表示網(wǎng)絡(luò)G中各階路徑中無環(huán)路徑的數(shù)量。

對(duì)于網(wǎng)絡(luò)的一階路徑，即為網(wǎng)絡(luò)的鄰接矩陣，不存在環(huán)狀路徑，因此A1=P1。

對(duì)于網(wǎng)絡(luò)的二階路徑，即為節(jié)點(diǎn)間的共同鄰居，也不存在環(huán)狀路徑，因此A2=P2。

對(duì)于網(wǎng)絡(luò)的三階及以上路徑，節(jié)點(diǎn)間路徑中便可能會(huì)出現(xiàn)環(huán)狀路徑，為了便于計(jì)算三階及以上節(jié)點(diǎn)間無環(huán)路徑數(shù)量，Chen等引入了中間矩陣Qk。Qk表示在k-1 階無環(huán)路徑后加上一階路徑組成的k階路徑，定義如式（2）和式（3）所示：

同理，可以求得五階無環(huán)路徑數(shù)量，定義如下：

2 六階無環(huán)路徑算法

Lü等證明了基于節(jié)點(diǎn)間連通能力的相似性度量指標(biāo)中路徑的長(zhǎng)度與網(wǎng)絡(luò)節(jié)點(diǎn)間平均路徑長(zhǎng)度呈正相關(guān)[25]，因此基于節(jié)點(diǎn)間連通能力的相似性度量指標(biāo)中路徑的長(zhǎng)度應(yīng)近似于網(wǎng)絡(luò)節(jié)點(diǎn)間平均路徑長(zhǎng)度。據(jù)數(shù)據(jù)分析報(bào)告，社交平臺(tái)Twitter 中用戶間平均路徑長(zhǎng)度為4.67，在Facebook 中為4.74，因此當(dāng)前社交網(wǎng)絡(luò)中節(jié)點(diǎn)平均路徑長(zhǎng)度近似為5。依據(jù)Lü等證明的理論，社交網(wǎng)絡(luò)中基于節(jié)點(diǎn)間連通能力的相似性度量指標(biāo)的路徑長(zhǎng)度應(yīng)取值為5，因此為了使得基于節(jié)點(diǎn)間連通能力的相似性度量指標(biāo)可以更好地融合社交網(wǎng)絡(luò)節(jié)點(diǎn)間的高階結(jié)構(gòu)信息，需計(jì)算節(jié)點(diǎn)間六階（路徑長(zhǎng)度為5）無環(huán)路徑數(shù)量。然而Chen 等[24]只給出了計(jì)算節(jié)點(diǎn)間五階（路徑長(zhǎng)度為4）內(nèi)無環(huán)路徑數(shù)量的數(shù)學(xué)表達(dá)式，未能給出計(jì)算節(jié)點(diǎn)間六階（路徑長(zhǎng)度為5）無環(huán)路徑數(shù)量的數(shù)學(xué)表達(dá)式，因此本文給出計(jì)算節(jié)點(diǎn)間六階（路徑長(zhǎng)度為5）無環(huán)路徑數(shù)量的準(zhǔn)確數(shù)學(xué)表達(dá)式。

圖1 六階無環(huán)路徑Fig.1 Loop-free 6-hop paths

3 LFNE算法

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

3.1 節(jié)點(diǎn)結(jié)構(gòu)相似性計(jì)算

為了使得相似性指標(biāo)可以更好地融合社交網(wǎng)絡(luò)高階結(jié)構(gòu)信息，本文提出了基于節(jié)點(diǎn)間無環(huán)路徑的相似性度量指標(biāo)SLP，定義如下：

其中，路徑長(zhǎng)度K由基于區(qū)域中心點(diǎn)距離（centers distance of zone，CDZ）[26]的最短路徑算法計(jì)算網(wǎng)絡(luò)平均路徑長(zhǎng)度確定，是節(jié)點(diǎn)間k階無環(huán)路徑數(shù)量，β(k)是減函數(shù)。在社交網(wǎng)絡(luò)中，兩個(gè)節(jié)點(diǎn)直接產(chǎn)生連接或者連通路徑越短，則兩個(gè)節(jié)點(diǎn)間的相似度會(huì)越高，聯(lián)系越緊密。SLP指標(biāo)中相較于高階的節(jié)點(diǎn)路徑信息會(huì)更多考慮低階的節(jié)點(diǎn)路徑信息。因此，引入權(quán)重衰減函數(shù)，當(dāng)節(jié)點(diǎn)間路徑增加時(shí)，路徑權(quán)重會(huì)相應(yīng)減小。本文使用指數(shù)函數(shù)作為SLP 指標(biāo)的權(quán)重衰減函數(shù)，權(quán)重衰減函數(shù)如式（8）所示：

其中，ω為權(quán)重衰減函數(shù)因子，ω∈(0,1)。借助權(quán)重衰減函數(shù)可以使得SLP 指標(biāo)在融入節(jié)點(diǎn)高階結(jié)構(gòu)信息的同時(shí)會(huì)更多考慮節(jié)點(diǎn)低階結(jié)構(gòu)信息。

接著，對(duì)SLP 指標(biāo)下節(jié)點(diǎn)相似度進(jìn)行歸一化處理，獲得節(jié)點(diǎn)間結(jié)構(gòu)概率矩陣，節(jié)點(diǎn)i和節(jié)點(diǎn)j的結(jié)構(gòu)概率定義如下：

3.2 節(jié)點(diǎn)屬性相似度計(jì)算

給定一個(gè)網(wǎng)絡(luò)G的屬性網(wǎng)絡(luò)W∈RN×F，F(xiàn)是屬性元素個(gè)數(shù)。通過余弦相似度公式將屬性網(wǎng)絡(luò)W轉(zhuǎn)換成節(jié)點(diǎn)屬性概率矩陣C，節(jié)點(diǎn)i和節(jié)點(diǎn)j的屬性概率定義如下：

多數(shù)基于網(wǎng)絡(luò)結(jié)構(gòu)信息和屬性信息相結(jié)合的網(wǎng)絡(luò)嵌入方法應(yīng)用于社交網(wǎng)絡(luò)中的實(shí)驗(yàn)效果并不理想，分析原因是雖然節(jié)點(diǎn)的屬性信息可以很好地彌補(bǔ)網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)稀疏的問題，但是社交網(wǎng)絡(luò)中節(jié)點(diǎn)屬性信息大多基于用戶隨意設(shè)定的興趣愛好，具有很大的主觀性和不準(zhǔn)確性，存在噪音，如圖2所示。

圖2 屬性網(wǎng)絡(luò)噪音示意圖Fig.2 Schematic diagram of attribute network noise

節(jié)點(diǎn)v1和節(jié)點(diǎn)v7在網(wǎng)絡(luò)結(jié)構(gòu)上相距甚遠(yuǎn)，在SLP 指標(biāo)下，兩節(jié)點(diǎn)的結(jié)構(gòu)相似度為0，節(jié)點(diǎn)v7對(duì)于節(jié)點(diǎn)v1是相對(duì)孤立點(diǎn)，但是節(jié)點(diǎn)v1和v7的屬性信息相似，在先前的網(wǎng)絡(luò)嵌入模型，沒有考慮節(jié)點(diǎn)結(jié)構(gòu)信息和屬性信息的相關(guān)性，會(huì)認(rèn)為這兩個(gè)節(jié)點(diǎn)具有相似的網(wǎng)絡(luò)嵌入表示。而實(shí)際上節(jié)點(diǎn)v7對(duì)于節(jié)點(diǎn)v1而言是屬性異常節(jié)點(diǎn)，存在屬性信息噪音，兩節(jié)點(diǎn)具有相似的網(wǎng)絡(luò)嵌入表示可能性相對(duì)較小，因此降低節(jié)點(diǎn)屬性信息中的噪音對(duì)于社交網(wǎng)絡(luò)嵌入具有重要意義。本文結(jié)合SLP 指標(biāo)改進(jìn)社交網(wǎng)絡(luò)節(jié)點(diǎn)屬性相似度計(jì)算方法，充分考慮節(jié)點(diǎn)結(jié)構(gòu)信息和屬性信息的相關(guān)性，降低社交網(wǎng)絡(luò)中節(jié)點(diǎn)屬性信息存在的噪音，解決大多數(shù)模型沒有考慮節(jié)點(diǎn)結(jié)構(gòu)信息和屬性信息相關(guān)性的問題。本文改進(jìn)的屬性相似性度量指標(biāo)定義如下：

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

對(duì)節(jié)點(diǎn)屬性相似度Bij進(jìn)行歸一化處理，獲得節(jié)點(diǎn)屬性概率矩陣，節(jié)點(diǎn)i和j的屬性概率定義如下：

3.3 節(jié)點(diǎn)結(jié)構(gòu)-屬性相似度矩陣

給定一個(gè)網(wǎng)絡(luò)G，節(jié)點(diǎn)結(jié)構(gòu)-屬性相似度矩陣X∈RN×N定義如下：

其中，λ的取值范圍在[0,1]之間。λ用來平衡節(jié)點(diǎn)結(jié)構(gòu)相似度和屬性相似度對(duì)于節(jié)點(diǎn)相似度的影響程度。當(dāng)λ為0時(shí)，節(jié)點(diǎn)相似度僅受到屬性相似度的影響，當(dāng)λ為1 時(shí)，節(jié)點(diǎn)相似度僅受到結(jié)構(gòu)相似度的影響。λ的取值越大，節(jié)點(diǎn)相似度受結(jié)構(gòu)相似度的影響越大。相應(yīng)的，λ的取值越小，節(jié)點(diǎn)相似度受屬性相似度的影響越大。

當(dāng)獲得節(jié)點(diǎn)的高維特征表示后，需要通過降維的方式獲得低維特征表示，捕獲高度非線性的網(wǎng)絡(luò)結(jié)構(gòu)。本文通過堆疊降噪自動(dòng)編碼器對(duì)節(jié)點(diǎn)結(jié)構(gòu)-屬性概率矩陣進(jìn)行降維，獲得低維特征表示。

3.4 堆疊降噪自動(dòng)編碼器

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

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

損失函數(shù)采用交叉熵函數(shù)，定義如下：

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

3.5 算法流程

融合節(jié)點(diǎn)屬性和無環(huán)路徑的社交網(wǎng)絡(luò)嵌入方法LFNE具體方法流程見算法1。

算法1LFNE算法

輸入：社交網(wǎng)絡(luò)G，網(wǎng)絡(luò)鄰接矩陣A，節(jié)點(diǎn)屬性矩陣W以及設(shè)置相關(guān)參數(shù)。

輸出：低維特征矩陣Z。

首先，LFNE 算法的輸入部分包括三部分：社交網(wǎng)絡(luò)G，網(wǎng)絡(luò)鄰接矩陣A，節(jié)點(diǎn)屬性矩陣W；計(jì)算結(jié)構(gòu)-屬性概率轉(zhuǎn)移矩陣所需參數(shù)，包括路徑權(quán)重參數(shù)β，節(jié)點(diǎn)間路徑長(zhǎng)度k，屬性相似度權(quán)重參數(shù)α，結(jié)構(gòu)-屬性平衡參數(shù)λ；堆疊降噪自動(dòng)編碼器特征提取階段所需參數(shù)，包括堆疊降噪自動(dòng)編碼器個(gè)數(shù)n，維度d，訓(xùn)練次數(shù)m。

算法1的第1行～第6行，首先通過矩陣A得到節(jié)點(diǎn)間基于無環(huán)路徑的相似度Sslp，捕獲社交網(wǎng)絡(luò)高階結(jié)構(gòu)相似性，然后生成矩陣H。接下來通過矩陣W和Sslp得到節(jié)點(diǎn)間屬性相似度B，充分利用社交網(wǎng)絡(luò)結(jié)構(gòu)信息和屬性信息的相關(guān)性，然后生成矩陣M。最后，通過矩陣H和M得到矩陣X。

算法1 的第7 行～第11 行，構(gòu)建了一個(gè)堆疊降噪自動(dòng)編碼器，輸入矩陣X，學(xué)習(xí)X的低維特征表示，循環(huán)執(zhí)行m次，最終得到X的低維特征矩陣Z。

3.6 時(shí)間復(fù)雜度

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

4 實(shí)驗(yàn)

為測(cè)試本文算法的可行性與有效性，將LFNE算法在3 個(gè)真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行性能評(píng)價(jià)。首先介紹實(shí)驗(yàn)數(shù)據(jù)集、對(duì)比算法、實(shí)驗(yàn)評(píng)價(jià)指標(biāo)和實(shí)驗(yàn)環(huán)境，之后進(jìn)行參數(shù)分析實(shí)驗(yàn)，最后進(jìn)行節(jié)點(diǎn)分類實(shí)驗(yàn)和鏈路預(yù)測(cè)實(shí)驗(yàn)。

4.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)中所用數(shù)據(jù)集具體信息如表1所示。

表1 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集基本信息Table 1 Basic information of real network datasets

BlogCatalog[13]：一個(gè)在線博客社交網(wǎng)絡(luò)。網(wǎng)絡(luò)由5 196名博主和博主間關(guān)注產(chǎn)生的交互關(guān)系組成。博主發(fā)布的博客關(guān)鍵詞作為博主的屬性信息。根據(jù)博主的興趣愛好，將博主分為6組。

Flickr[28]：一個(gè)在線圖片分享網(wǎng)站。該網(wǎng)絡(luò)是一個(gè)由7 575 名用戶和用戶間共享照片產(chǎn)生的交互關(guān)系組成的社交網(wǎng)絡(luò)。用戶發(fā)布的圖像標(biāo)簽信息和用戶的個(gè)人愛好作為用戶的屬性信息。根據(jù)加入的預(yù)定義組，將用戶分為9組。

Email[28]：歐洲研究機(jī)構(gòu)成員電子郵件通信網(wǎng)絡(luò)。該網(wǎng)絡(luò)由1 005 名研究人員和研究人員間通過電子郵件產(chǎn)生的交互組成的社交網(wǎng)絡(luò)。研究人員的屬性信息對(duì)應(yīng)所屬部門。

4.2 對(duì)比算法

將LFNE 算法與近幾年代表性算法進(jìn)行對(duì)比實(shí)驗(yàn)，其中DeepWalk[2]、node2vec[6]、DNGR[7]、SDNE[8]是基于網(wǎng)絡(luò)結(jié)構(gòu)信息的網(wǎng)絡(luò)嵌入方法，TADW[11]、DANE[15]是基于網(wǎng)絡(luò)結(jié)構(gòu)信息和屬性信息相結(jié)合的網(wǎng)絡(luò)嵌入方法。

DeepWalk：通過隨機(jī)游走方式獲得節(jié)點(diǎn)的序列表示，然后通過word2vec模型[3]獲得基于節(jié)點(diǎn)上下文結(jié)構(gòu)的嵌入表示。

node2vec：結(jié)合深度優(yōu)先搜索和廣度優(yōu)先搜索優(yōu)化了隨機(jī)游走序列生成方式，然后通過最大化保留節(jié)點(diǎn)網(wǎng)絡(luò)鄰域的可能性學(xué)習(xí)節(jié)點(diǎn)表示。

DNGR：通過隨機(jī)沖浪獲得節(jié)點(diǎn)高階結(jié)構(gòu)信息，然后通過棧式降噪自動(dòng)編碼器進(jìn)行網(wǎng)絡(luò)嵌入。

SDNE：通過深度自動(dòng)編碼器捕捉高度非線性的網(wǎng)絡(luò)結(jié)構(gòu)，然后通過聯(lián)合優(yōu)化節(jié)點(diǎn)一階和二階相似性保留網(wǎng)絡(luò)局部和全局結(jié)構(gòu)特征來獲得節(jié)點(diǎn)的嵌入結(jié)果。

TADW：通過矩陣分解學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)和屬性信息獲得節(jié)點(diǎn)的低維特征表示。

DANE：通過個(gè)性化隨機(jī)游走模型學(xué)習(xí)網(wǎng)絡(luò)高階結(jié)構(gòu)信息和屬性信息獲得全局信息矩陣，然后通過深度自動(dòng)編碼器學(xué)習(xí)節(jié)點(diǎn)全局信息獲得節(jié)點(diǎn)的嵌入表示。

4.3 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)和實(shí)驗(yàn)環(huán)境

本文中使用的實(shí)驗(yàn)評(píng)價(jià)指標(biāo)分別是Micro-F1[29]、Macro-F1[29]和AUC（area under the curve）[30]。Micro-F1 指標(biāo)表示對(duì)于數(shù)據(jù)集建立全局混淆矩陣，計(jì)算相應(yīng)的指標(biāo)。Macro-F1指標(biāo)表示對(duì)于數(shù)據(jù)集各個(gè)標(biāo)簽建立混淆矩陣，計(jì)算各標(biāo)簽下的Micro-F1 指標(biāo)的算數(shù)平均值。Micro-F1和Macro-F1指標(biāo)常用作評(píng)價(jià)節(jié)點(diǎn)分類任務(wù)效果，值越高，實(shí)驗(yàn)效果越好。Micro-F1和Macro-F1指標(biāo)定義如下：

其中，P表示精確率，R表示召回率，M是標(biāo)簽數(shù)量。TPi表示將實(shí)際標(biāo)簽為i的樣本預(yù)測(cè)為標(biāo)簽i的樣本數(shù)量；FPi表示將實(shí)際標(biāo)簽為非i的樣本預(yù)測(cè)為標(biāo)簽i的樣本數(shù)量；FNi表示將實(shí)際標(biāo)簽為i的樣本預(yù)測(cè)為非i標(biāo)簽的樣本數(shù)量。

AUC指標(biāo)表示ROC（receiver operating characteristic curve）曲線下所圍成的面積大小，常用作鏈路預(yù)測(cè)實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)。在鏈路預(yù)測(cè)實(shí)驗(yàn)中體現(xiàn)為每次從網(wǎng)絡(luò)中不存在邊的集合和測(cè)試集邊的集合中各自隨機(jī)選擇一條邊進(jìn)行比較，后者比前者分?jǐn)?shù)高的概率。定義如下：

其中，n表示比較的次數(shù)，n′表示測(cè)試集中邊鏈路預(yù)測(cè)值高于網(wǎng)絡(luò)中不存在邊的次數(shù)，n″表示測(cè)試集中邊鏈路預(yù)測(cè)值等于不存在邊的次數(shù)。一般認(rèn)為，AUC的值越高，算法鏈路預(yù)測(cè)效果越好。

本文的實(shí)驗(yàn)環(huán)境為：處理器為Intel?CoreTMi7-8750H CPU@2.20 GHz，內(nèi)存為16 GB，操作系統(tǒng)為Windows 10 64 bit。

4.4 參數(shù)設(shè)置

本文算法使用堆疊降噪自動(dòng)編碼器學(xué)習(xí)節(jié)點(diǎn)低維特征表示。為了使堆疊自動(dòng)降噪自動(dòng)編碼器可以更好地獲取節(jié)點(diǎn)低維特征表示，對(duì)于不同數(shù)據(jù)集采用不同的自動(dòng)編碼器結(jié)構(gòu)。各數(shù)據(jù)集對(duì)應(yīng)的自動(dòng)編碼器結(jié)構(gòu)如表2所示。

表2 不同數(shù)據(jù)集下堆疊降噪自動(dòng)編碼器結(jié)構(gòu)Table 2 Structure of stacked denoising autoencoder under different datasets

實(shí)驗(yàn)中采用的對(duì)比算法輸出的節(jié)點(diǎn)向量維度和本文算法輸出的向量維度一致。本文算法中SLP 指標(biāo)參數(shù)ω參照文獻(xiàn)[24]取值為0.3。堆疊降噪自動(dòng)編碼器模型使用Adam優(yōu)化器進(jìn)行訓(xùn)練，迭代次數(shù)設(shè)置為500，學(xué)習(xí)率為0.002。本文中需要被討論的參數(shù)是節(jié)點(diǎn)間路徑長(zhǎng)度k、屬性相似度權(quán)重參數(shù)α和結(jié)構(gòu)-屬性平衡參數(shù)λ。

節(jié)點(diǎn)間路徑長(zhǎng)度k體現(xiàn)了節(jié)點(diǎn)間的連通性，節(jié)點(diǎn)間路徑長(zhǎng)度過低會(huì)使得算法僅考慮節(jié)點(diǎn)局部結(jié)構(gòu)信息，不能充分利用網(wǎng)絡(luò)結(jié)構(gòu)信息，導(dǎo)致節(jié)點(diǎn)相似度衡量不準(zhǔn)確。而節(jié)點(diǎn)間路徑長(zhǎng)度過高會(huì)使得節(jié)點(diǎn)間連通路徑間存在大量結(jié)構(gòu)噪音信息。因此，確定合理的節(jié)點(diǎn)間路徑長(zhǎng)度，對(duì)于衡量節(jié)點(diǎn)間相似度至關(guān)重要。為充分體現(xiàn)節(jié)點(diǎn)間路徑長(zhǎng)度對(duì)于LFNE 算法的影響，實(shí)驗(yàn)中節(jié)點(diǎn)間路徑長(zhǎng)度k取值為1 至10，步長(zhǎng)為1。六階內(nèi)節(jié)點(diǎn)間無環(huán)路徑數(shù)量采用本文算法進(jìn)行計(jì)算，六階以上節(jié)點(diǎn)間無環(huán)路徑數(shù)量采用文獻(xiàn)[24]中的計(jì)算方法進(jìn)行近似計(jì)算。節(jié)點(diǎn)間路徑長(zhǎng)度k影響實(shí)驗(yàn)中采用BlogCatalog、Flickr、Email 三個(gè)數(shù)據(jù)集進(jìn)行鏈路預(yù)測(cè)任務(wù)，評(píng)價(jià)指標(biāo)是AUC。實(shí)驗(yàn)中隨機(jī)選取10%的連接數(shù)據(jù)和未連接數(shù)據(jù)作為測(cè)試，10%的連接數(shù)據(jù)作為驗(yàn)證，其余數(shù)據(jù)用作訓(xùn)練。實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 參數(shù)k 對(duì)算法的影響Fig.3 Influence of parameter k on algorithm

實(shí)驗(yàn)結(jié)果表明，在BlogCatalog和Flickr大型社交網(wǎng)絡(luò)數(shù)據(jù)集中，路徑長(zhǎng)度取值為6時(shí)，AUC值最高，鏈路預(yù)測(cè)效果最好，可以證明節(jié)點(diǎn)間六階路徑能充分體現(xiàn)大型社交網(wǎng)絡(luò)中節(jié)點(diǎn)間的連通性，可以獲得較好的實(shí)驗(yàn)效果。而對(duì)于Email數(shù)據(jù)集，路徑長(zhǎng)度取值為4時(shí)，鏈路預(yù)測(cè)效果最好。分析原因是節(jié)點(diǎn)間最佳路徑距離與節(jié)點(diǎn)間平均距離呈正相關(guān)，由于Email數(shù)據(jù)集網(wǎng)絡(luò)規(guī)模較小，節(jié)點(diǎn)間平均最短距離相對(duì)較小，故k取值較小時(shí)實(shí)驗(yàn)效果最好。

屬性相似度權(quán)重參數(shù)α用于降低社交網(wǎng)絡(luò)中節(jié)點(diǎn)屬性信息存在的噪音，當(dāng)α取值過高時(shí)，會(huì)使得網(wǎng)絡(luò)節(jié)點(diǎn)中存在大量的屬性噪音，當(dāng)α取值過低時(shí)，不能充分考慮節(jié)點(diǎn)屬性信息，因此確定合理的屬性相似度權(quán)重參數(shù)α可以提高社交網(wǎng)絡(luò)嵌入效果。實(shí)驗(yàn)中，α取0至1，步長(zhǎng)為0.1，采用BlogCatalog、Flickr兩個(gè)數(shù)據(jù)集進(jìn)行節(jié)點(diǎn)分類任務(wù)，評(píng)價(jià)指標(biāo)是Micro-F1分?jǐn)?shù)和Macro-F1 分?jǐn)?shù)，隨機(jī)選取30%節(jié)點(diǎn)作為標(biāo)記節(jié)點(diǎn)進(jìn)行訓(xùn)練，其余節(jié)點(diǎn)用作測(cè)試。實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 參數(shù)α 對(duì)算法的影響Fig.4 Influence of parameter α on algorithm

實(shí)驗(yàn)結(jié)果表明，當(dāng)屬性相似度權(quán)重參數(shù)α取值為0.3時(shí)，在BlogCatalog、Flickr數(shù)據(jù)集上節(jié)點(diǎn)分類效果最好。當(dāng)參數(shù)從0.3 至1.0 時(shí)，屬性信息存在的噪音影響越來越大，節(jié)點(diǎn)分類效果越來越差，可見降低節(jié)點(diǎn)屬性信息中存在的噪音確實(shí)可以有效提高算法網(wǎng)絡(luò)嵌入能力。而當(dāng)參數(shù)小于0.3時(shí)，未能充分考慮節(jié)點(diǎn)屬性信息，節(jié)點(diǎn)分類效果也變差。

結(jié)構(gòu)-屬性平衡參數(shù)λ用于平衡節(jié)點(diǎn)間結(jié)構(gòu)相似度和屬性相似度。實(shí)驗(yàn)中，λ取0.5 至1.0，步長(zhǎng)為0.1，采用BlogCatalog、Flickr 兩個(gè)數(shù)據(jù)集進(jìn)行節(jié)點(diǎn)分類任務(wù)，評(píng)價(jià)指標(biāo)是Micro-F1分?jǐn)?shù)和Macro-F1分?jǐn)?shù)，隨機(jī)選取10%節(jié)點(diǎn)作為標(biāo)記節(jié)點(diǎn)進(jìn)行訓(xùn)練，其余節(jié)點(diǎn)用作測(cè)試。實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 參數(shù)λ 對(duì)算法的影響Fig.5 Influence of parameter λ on algorithm

實(shí)驗(yàn)結(jié)果表明，當(dāng)結(jié)構(gòu)-屬性平衡參數(shù)λ取值為0.7 時(shí)，在BlogCatalog、Flickr 兩個(gè)數(shù)據(jù)集上節(jié)點(diǎn)分類效果最好。當(dāng)參數(shù)從0.7 至1.0 時(shí)，節(jié)點(diǎn)相似度受節(jié)點(diǎn)屬性相似度影響越來越小，節(jié)點(diǎn)分類效果越來越差，可見節(jié)點(diǎn)屬性信息確實(shí)可以有效提高算法網(wǎng)絡(luò)嵌入能力。而當(dāng)參數(shù)小于0.7時(shí)，節(jié)點(diǎn)相似度受節(jié)點(diǎn)結(jié)構(gòu)相似度影響越來越小，節(jié)點(diǎn)分類效果也變差。因此，當(dāng)λ取值為0.7時(shí)效果最好。本文在后續(xù)的實(shí)驗(yàn)中，節(jié)點(diǎn)間路徑長(zhǎng)度k由CDZ 算法[26]計(jì)算網(wǎng)絡(luò)平均路徑長(zhǎng)度確定，屬性相似度權(quán)重參數(shù)α取值為0.3，結(jié)構(gòu)-屬性平衡參數(shù)λ取值為0.7。

4.5 節(jié)點(diǎn)分類

節(jié)點(diǎn)分類是社交網(wǎng)絡(luò)分析一項(xiàng)重要任務(wù)，通過已被標(biāo)記的節(jié)點(diǎn)來預(yù)測(cè)網(wǎng)絡(luò)中未被標(biāo)記的節(jié)點(diǎn)標(biāo)簽種類，常用于評(píng)價(jià)網(wǎng)絡(luò)嵌入方法的性能。本文節(jié)點(diǎn)分類實(shí)驗(yàn)選取的數(shù)據(jù)集是BlogCatalog 和Flickr 數(shù)據(jù)集，評(píng)價(jià)指標(biāo)是Micro-F1 分?jǐn)?shù)和Macro-F1 分?jǐn)?shù)。實(shí)驗(yàn)中首先通過各算法學(xué)習(xí)節(jié)點(diǎn)的低維特征表示，然后隨機(jī)抽取10%至90%（步長(zhǎng)為20%）節(jié)點(diǎn)作為標(biāo)記節(jié)點(diǎn)進(jìn)行訓(xùn)練，其余節(jié)點(diǎn)用作測(cè)試。實(shí)驗(yàn)結(jié)果如表3～表6所示。

表3 BlogCatalog數(shù)據(jù)集節(jié)點(diǎn)分類Micro-F1分?jǐn)?shù)Table 3 Micro-F1 of node classification on BlogCatalog dataset

表4 BlogCatalog數(shù)據(jù)集節(jié)點(diǎn)分類Macro-F1分?jǐn)?shù)Table 4 Macro-F1 of node classification on BlogCatalog dataset

表5 Flickr數(shù)據(jù)集節(jié)點(diǎn)分類Micro-F1分?jǐn)?shù)Table 5 Micro-F1 of node classification on Flickr dataset

表6 Flickr數(shù)據(jù)集節(jié)點(diǎn)分類Macro-F1分?jǐn)?shù)Table 6 Macro-F1 of node classification on Flickr dataset

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

4.6 鏈路預(yù)測(cè)

鏈路預(yù)測(cè)亦是社交網(wǎng)絡(luò)分析的一項(xiàng)重要任務(wù)，根據(jù)已有的網(wǎng)絡(luò)連接預(yù)測(cè)節(jié)點(diǎn)間潛在或者未來的連接過程。鏈路預(yù)測(cè)也常用于評(píng)價(jià)網(wǎng)絡(luò)嵌入學(xué)習(xí)方法的性能。本節(jié)鏈路預(yù)測(cè)實(shí)驗(yàn)選取的數(shù)據(jù)集是BlogCatalog、Flickr和Email，評(píng)價(jià)指標(biāo)是AUC。實(shí)驗(yàn)中隨機(jī)選取10%的連接數(shù)據(jù)和未連接數(shù)據(jù)作為測(cè)試，10%的連接數(shù)據(jù)作為驗(yàn)證，其余數(shù)據(jù)用作訓(xùn)練。實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 不同算法鏈路預(yù)測(cè)AUC指標(biāo)結(jié)果Fig.6 AUC index results of link prediction with different algorithms

根據(jù)實(shí)驗(yàn)結(jié)果，TADW 和DANE 等融合結(jié)構(gòu)和屬性信息的網(wǎng)絡(luò)嵌入方法相較于單一融合結(jié)構(gòu)信息的SDNE、DNGR算法在BlogCatalog、Email并沒有取得更好的鏈路預(yù)測(cè)效果。在BlogCatalog 數(shù)據(jù)集上TADW 算法的鏈路預(yù)測(cè)效果最差，DNGR 算法相較于TADW 算法AUC 指標(biāo)提升30.2%，可以證明社交網(wǎng)絡(luò)中屬性信息確實(shí)存在噪音。而本文提出的LFNE 算法在各個(gè)數(shù)據(jù)集上都取得了不錯(cuò)的鏈路預(yù)測(cè)效果，在BlogCatalog、Flickr、Email 數(shù)據(jù)集上相較于DNGR 算法AUC 指標(biāo)分別提升5.2%、15.9%、3.9%。實(shí)驗(yàn)表明，LFNE算法充分考慮節(jié)點(diǎn)屬性信息和結(jié)構(gòu)信息的相關(guān)性，降低社交網(wǎng)絡(luò)屬性信息存在的噪音，可以獲得更好的鏈路預(yù)測(cè)效果。

5 結(jié)束語

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

附錄1