基于節(jié)點(diǎn)嵌入的權(quán)重符號社交網(wǎng)絡(luò)高效鏈路預(yù)測算法

楊 威 王軼彤

(復(fù)旦大學(xué)計算機(jī)科學(xué)技術(shù)學(xué)院 上海201203)

0 引 言

隨著在線社交網(wǎng)絡(luò)的快速發(fā)展，許多系統(tǒng)能夠建模成WSSN[1]，以便更細(xì)粒度地反映節(jié)點(diǎn)之間的關(guān)系。在一個權(quán)重符號社交網(wǎng)絡(luò)中，每條邊上的權(quán)值可以同時反映情感的傾向(正或負(fù))以及關(guān)系的強(qiáng)弱(具體的數(shù)值)。例如，考慮邊權(quán)重為+3、+2或-2，不僅具有符號以反映情感的傾向：喜歡/不喜歡、信任/猜忌、朋友/敵人、合作/競爭等，還能抓取關(guān)系的強(qiáng)度，如喜歡的程度、猜忌的程度等。在一些在線社交媒體中，邊的符號和權(quán)重值是直接給定的。例如，在比特幣的交易平臺(Alpha或OTC)中，用戶能夠使用-10(完全不信任)到10(完全信任)的分?jǐn)?shù)值來評價其他用戶，以此來表達(dá)對于其他用戶的態(tài)度。與此同時，現(xiàn)實(shí)中也存在一些在線的社交網(wǎng)絡(luò)，它們給定了邊的符號，但邊的權(quán)重需要隱式抽取。例如，在維基百科管理員申請網(wǎng)絡(luò)(RfA)中，如果一個維基百科的編輯者想要成為一個管理員，他需要先提交一個申請，而其他的用戶使用三個標(biāo)簽(支持、中性或反對)中的一個來對這個申請進(jìn)行投票，輔之以簡短的投票理由。因此，能夠使用一些語義分析工具從投票附加的文本中隱式的抽取出邊的權(quán)重并且形成一個權(quán)重符號社交網(wǎng)絡(luò)[1]。顯然，權(quán)重符號網(wǎng)絡(luò)能在更細(xì)的粒度上反映社交網(wǎng)絡(luò)中節(jié)點(diǎn)之間的信息。在無權(quán)無符號的社交網(wǎng)絡(luò)中，鏈路預(yù)測問題主要關(guān)注于邊存在性的預(yù)測，可以擴(kuò)展為對邊符號(正或負(fù))的預(yù)測(符號網(wǎng)絡(luò))。本文專注于權(quán)重符號社交網(wǎng)絡(luò)的鏈路預(yù)測問題，即預(yù)測邊上的權(quán)重信息，包含符號和數(shù)值，反映關(guān)系的方向和強(qiáng)弱。目前主要的鏈路預(yù)測研究都集中在如何能更好地獲取節(jié)點(diǎn)的信息及正確度量節(jié)點(diǎn)之間的近似性，但這種思想并不完全適用于權(quán)重符號網(wǎng)絡(luò)，需要進(jìn)一步結(jié)合社會學(xué)理論和網(wǎng)絡(luò)結(jié)構(gòu)來提高邊上權(quán)重的預(yù)測性能。

對于許多社交網(wǎng)絡(luò)應(yīng)用，如鏈路預(yù)測[2]和節(jié)點(diǎn)分類[3]，其網(wǎng)絡(luò)特征的提取是非常重要的。許多算法的性能極大地取決于對輸入網(wǎng)絡(luò)特征提取的有效性，節(jié)點(diǎn)和網(wǎng)絡(luò)結(jié)構(gòu)重要的特征需要盡可能保存。不同于傳統(tǒng)的特征工程方法，網(wǎng)絡(luò)嵌入為網(wǎng)絡(luò)中的節(jié)點(diǎn)學(xué)習(xí)一個低維度的潛在特征，從而保存網(wǎng)絡(luò)的結(jié)構(gòu)信息。網(wǎng)絡(luò)嵌入是自動的特征提取，許多研究已經(jīng)證明此方法優(yōu)于一些特征工程的方法。特別是近幾年，網(wǎng)絡(luò)嵌入方法被廣泛地應(yīng)用于社交網(wǎng)絡(luò)分析領(lǐng)域。本文將基于節(jié)點(diǎn)嵌入對權(quán)重符號網(wǎng)絡(luò)中的邊進(jìn)行權(quán)重預(yù)測。

目前的網(wǎng)絡(luò)嵌入方法，主要集中在無符號/無權(quán)重社交網(wǎng)絡(luò)。在無符號社交網(wǎng)絡(luò)中，邊被標(biāo)記為1或者0(1代表存在，0代表不存在)。大多數(shù)無符號網(wǎng)絡(luò)嵌入的方法基于同構(gòu)性原理和skip-gram模型[4]。在設(shè)計目標(biāo)函數(shù)的過程中，并未考慮邊的符號或權(quán)重。文獻(xiàn)[5,15]已經(jīng)證明負(fù)邊具有額外的價值，考慮負(fù)邊能夠提高正邊的預(yù)測精度。由于負(fù)邊的存在，同構(gòu)性原理不再適用。一些基于平衡理論的方法[6]應(yīng)用隨機(jī)游走策略生成帶有符號的共現(xiàn)對，以此來嵌入符號網(wǎng)絡(luò)。這些方法并未直接擬合邊的權(quán)重信息，如果將它們直接用于嵌入權(quán)重符號社交網(wǎng)絡(luò)，將會導(dǎo)致社交鏈路預(yù)測的性能不佳。邊的權(quán)重在度量節(jié)點(diǎn)間關(guān)系強(qiáng)度上是一個關(guān)鍵要素，它給出了節(jié)點(diǎn)間關(guān)系的更細(xì)粒度信息，并且能更準(zhǔn)確地反映網(wǎng)絡(luò)結(jié)構(gòu)。同時，在嵌入空間中保存邊的權(quán)重信息將會取得更優(yōu)的邊權(quán)重預(yù)測性能。

本文提出一種權(quán)重符號社交網(wǎng)絡(luò)嵌入方法(Weighted Signed Network Embedding，WSNE)，以此來獲得更優(yōu)的邊權(quán)預(yù)測性能。WSNE為網(wǎng)絡(luò)中的節(jié)點(diǎn)學(xué)習(xí)潛在特征表示，并且在學(xué)得的潛在特征空間中盡可能地保存邊的權(quán)重和符號信息。在一個權(quán)重符號社交網(wǎng)絡(luò)中，一條邊eij能夠考慮作為從用戶i到用戶j“主觀性”觀點(diǎn)/評價的傳遞。從用戶j的視角來看，這個觀點(diǎn)/評價是客觀的。因此，對于一個節(jié)點(diǎn)i去學(xué)習(xí)它作為一條邊起始節(jié)點(diǎn)的“主觀”潛在特征表示si和作為一條邊終止節(jié)點(diǎn)的“客觀”潛在特征表示oi。參照矩陣分解的方法[7]，對于一條邊eij，使用si和oj的點(diǎn)積擬合邊的權(quán)重信息。同時在一個權(quán)重符號社交網(wǎng)絡(luò)中，邊的符號也是非常重要的，因?yàn)樗从沉瞬煌那楦?。例如，如果一條邊的權(quán)重是1，擬合值-1和3將會產(chǎn)生同樣的誤差。但是3明顯是更優(yōu)的擬合值，因?yàn)樗从沉藴?zhǔn)確的情感傾向。因此，本文基于擴(kuò)展的結(jié)構(gòu)平衡理論[8]添加對于邊的符號約束。

本文主要貢獻(xiàn)如下：

1) 提出了一個權(quán)重符號社交網(wǎng)絡(luò)嵌入方法WSNE來獲得更優(yōu)的邊權(quán)重預(yù)測性能。

2) 設(shè)計了一個目標(biāo)函數(shù)來學(xué)習(xí)網(wǎng)絡(luò)中節(jié)點(diǎn)的“主觀”及“客觀”潛在特征表示。在學(xué)得的潛在特征空間中，保存了邊的權(quán)重和符號信息。

3) 在三個真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行社交鏈路預(yù)測任務(wù)。使用根均方誤差、相關(guān)系數(shù)、符號預(yù)測準(zhǔn)確率等多個評價指標(biāo)，與多個相關(guān)且優(yōu)秀的算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，WSNE在上述評價指標(biāo)上實(shí)現(xiàn)了更優(yōu)的權(quán)重預(yù)測性能。

1 相關(guān)工作

本文使用網(wǎng)絡(luò)嵌入的方法解決權(quán)重符號社交網(wǎng)絡(luò)中的社交鏈路預(yù)測問題，因此主要關(guān)注于網(wǎng)絡(luò)嵌入方法和權(quán)重預(yù)測方法。

1.1 社交網(wǎng)絡(luò)分析中的網(wǎng)絡(luò)嵌入

大多數(shù)網(wǎng)絡(luò)嵌入方法主要關(guān)注于無符號網(wǎng)絡(luò)[4,9-12]和無權(quán)帶符號社交網(wǎng)絡(luò)[13-18]。對于無符號社交網(wǎng)絡(luò)，許多方法是基于同構(gòu)性原理并且參考skip-gram模型[4,10]來學(xué)習(xí)節(jié)點(diǎn)的嵌入。Perozzi等[4]通過將截斷隨機(jī)游走生成的節(jié)點(diǎn)序列和語料庫中的句子等價，來學(xué)習(xí)節(jié)點(diǎn)的潛在特征表示。Tang等[9]設(shè)計了一個目標(biāo)函數(shù)來保存局部和全局的網(wǎng)絡(luò)結(jié)構(gòu)，同時還提出了一個邊抽樣技術(shù)來解決經(jīng)典隨機(jī)梯度下降方法的限制。Grover等[10]提出了一個靈活的節(jié)點(diǎn)鄰居概念，并且設(shè)計了一個偏好隨機(jī)游走程序來獲得多樣性的鄰居。此外，Ou等[11]關(guān)注有向無符號網(wǎng)絡(luò)，提出HOPE方法在學(xué)得的嵌入空間中保存邊的不對稱傳遞性。Wang等[12]提出一個半監(jiān)督的深度學(xué)習(xí)模型來優(yōu)化一序和二序鄰近性。但上述嵌入方法并未考慮到邊的符號和權(quán)重信息。

對于無權(quán)符號網(wǎng)絡(luò)，文獻(xiàn)[13]使用log-bilinear模型，通過最大化在給定路徑下生成目標(biāo)節(jié)點(diǎn)的條件概率來學(xué)習(xí)節(jié)點(diǎn)的源嵌入和目標(biāo)嵌入。文獻(xiàn)[14]使用word2vec嵌入方法，并提出一個目標(biāo)節(jié)點(diǎn)抽樣策略來維持高序鄰居間的結(jié)構(gòu)平衡。文獻(xiàn)[15]提出了一個深度學(xué)習(xí)框架SiNE來學(xué)習(xí)節(jié)點(diǎn)的潛在特征表示，優(yōu)化一個結(jié)構(gòu)平衡理論指導(dǎo)的目標(biāo)函數(shù)。文獻(xiàn)[16]采用多個信息源：情緒信息、社交信息和簡歷信息，并且使用多個自編碼器來訓(xùn)練每一個信息源。文獻(xiàn)[17]利用網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)的屬性來學(xué)習(xí)符號社交網(wǎng)絡(luò)的嵌入。文獻(xiàn)[18]提出一個網(wǎng)絡(luò)嵌入方法SIDE，完善編碼邊的符號和方向信息。但上述方法并未直接擬合邊的權(quán)重信息，如果直接用于解決權(quán)重符號社交網(wǎng)絡(luò)的社交鏈路預(yù)測任務(wù)，將不會獲得最佳的性能。

1.2 權(quán)重預(yù)測任務(wù)

在邊權(quán)預(yù)測中，大部分的相關(guān)工作關(guān)注于無符號社交網(wǎng)絡(luò)。Gilbert[19]提出了一個Twitter應(yīng)用——We Middle，其核心是Facebook鏈接強(qiáng)度模型的設(shè)計，以此來評估鏈接的強(qiáng)度。Xiang等[20]使用交互信息(例如社區(qū)和標(biāo)簽)和用戶的相似性開發(fā)了一個無監(jiān)督模型來獲取關(guān)系的強(qiáng)度。在權(quán)重符號社交網(wǎng)絡(luò)的邊權(quán)預(yù)測中，Kumar等[1]提出Fairness和Goodness兩個特征來預(yù)測邊的權(quán)重。還有多個方法也能夠應(yīng)用于權(quán)重符號社交網(wǎng)絡(luò)中的權(quán)重預(yù)測，例如：reciprocal，PageRank，signed eigenvector centrality，bias and deserve，EigenTrust和signed-HITS[1]。但文獻(xiàn)[1]已經(jīng)證明Fairness和Goodness(FG)能夠取得更優(yōu)的權(quán)重預(yù)測性能，因此本文方法主要與FG方法進(jìn)行比較。

2 問題描述

一個權(quán)重符號社交網(wǎng)絡(luò)被建模成一個有向的加權(quán)圖G=(V，E，E+，E-，W)，其中：V是節(jié)點(diǎn)集合；E是邊集合；E+是正邊集合；E-是負(fù)邊集合；W∈R|V|×|V|是一個邊權(quán)矩陣。在W中每一個元素Wij表示一條從i到j(luò)的有向邊的權(quán)重。當(dāng)談?wù)撘粭l邊的權(quán)重時，例如-5，它實(shí)際上指示著邊的符號和關(guān)系的強(qiáng)度。本文嘗試為網(wǎng)絡(luò)中的節(jié)點(diǎn)學(xué)習(xí)“主觀”潛在特征S和“客觀”潛在特征O，以此來擬合邊的權(quán)重信息。即本文想要學(xué)習(xí)一個轉(zhuǎn)移函數(shù)f(·)，使得：

f(V,E,W)→(S,O)

(1)

式中：S和O的維度是|V|×K(K?|V|)，|V|是節(jié)點(diǎn)的數(shù)目，K是潛在特征的維度。問題的關(guān)鍵在于如何設(shè)計一個有效目標(biāo)函數(shù)來學(xué)習(xí)更好的節(jié)點(diǎn)嵌入。

3 算法設(shè)計

3.1 邊權(quán)重的擬合

(2)

3.2 添加符號約束

在一個權(quán)重符號社交網(wǎng)絡(luò)中，符號擬合的一致性是非常重要的。對于一條真實(shí)權(quán)重為1的邊，即使有著相同的誤差，擬合值為-1或者3是完全不同的結(jié)果。顯然3是更好的擬合值，因?yàn)樗鼫?zhǔn)確地擬合了情感的傾向。因此，對于網(wǎng)絡(luò)中每一條存在的有向邊，在擬合其權(quán)重時，不僅需要擬合權(quán)重的數(shù)值，還需要準(zhǔn)確擬合符號，本文添加一個局部的符號約束來滿足這一點(diǎn)，目標(biāo)是最小化擬合值和真實(shí)值之間誤差的同時，保持符號的一致。同時，實(shí)驗(yàn)結(jié)果表明權(quán)重預(yù)測中符號和數(shù)值之間是相互提高的，既提高擬合值和真實(shí)值之間符號的一致性，也能夠進(jìn)一步提高社交鏈路預(yù)測的性能。

符號約束是基于社會學(xué)中的擴(kuò)展的結(jié)構(gòu)平衡理論[8]，即正邊端點(diǎn)之間的相似性大于負(fù)邊端點(diǎn)之間的相似性：

sim(i,j)>sim(h,k)eij∈E+,enk∈E-

(3)

式中：sim(·，·)是一個相似性度量函數(shù)。與文獻(xiàn)[18]相同，本文使用Sigmoid函數(shù)度量兩個端點(diǎn)之間的相似性：

(4)

式中：si表示“主觀”矩陣S中第i行;oj表示“客觀”矩陣中的第j行。

(5)

使用對數(shù)運(yùn)算來簡化上式的計算，并且為了與擬合權(quán)重中最小化目標(biāo)函數(shù)一致，將轉(zhuǎn)換式(5)為：

(6)

結(jié)合式(2)和式(6)，WSNE方法總的目標(biāo)函數(shù)為：

L(S,O)=M+γ×C

(7)

式中：γ為參數(shù)，控制著符號約束的貢獻(xiàn)。本文使用隨機(jī)梯度下降算法來獲得目標(biāo)函數(shù)的局部最優(yōu)值。

3.3 算法步驟

將數(shù)據(jù)集劃分為兩個部分：當(dāng)前網(wǎng)絡(luò)中存在的正邊集合和負(fù)邊集合。對于每一個部分，分別描述其優(yōu)化過程。

對于集合E+中的邊eij，求解si和oj的梯度：

(8)

對于集合E-中的邊eij，求解si和oj的梯度：

(9)

基于式(10)迭代地更新si和oj，這里α為學(xué)習(xí)速率(本文設(shè)定α=0.005)。

(10)

當(dāng)目標(biāo)函數(shù)連續(xù)兩次平均值之差小于預(yù)先定義的閾值(本文設(shè)定為0.005)時，則認(rèn)為算法收斂。WSNE的詳細(xì)描述如算法1所示，其時間復(fù)雜度為：

o(t×|E|×K)

(11)

式中：t是迭代的次數(shù);|E|是邊數(shù);K是潛在特征的維度。

算法1WSNE

輸入：G、β、γ。

輸出：S、O。

隨機(jī)初始化S、O;

While 不收斂do:

Foreij∈(E+∪E-):

Ifeij∈E+:

根據(jù)式(8)計算si和oj的梯度;

Ifeij∈E-:

根據(jù)式(9)計算si和oj的梯度;

根據(jù)式(10)更新si和oj;

End

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

本節(jié)將驗(yàn)證WSNE算法在權(quán)重符號社交網(wǎng)絡(luò)中的社交鏈路預(yù)測問題上的性能。特別地，算法的驗(yàn)證主要集中在該種網(wǎng)絡(luò)的邊權(quán)重預(yù)測問題。

4.1 數(shù)據(jù)集

本文在3個數(shù)據(jù)集上運(yùn)行WSNE算法并驗(yàn)證其性能。

1) 比特幣Alpha[21]和比特幣OTC[22]：它們是來自于兩個比特幣交易平臺Alpha和OTC的信任網(wǎng)絡(luò)。每一個用戶能夠使用-10(完全不信任)到10(完全信任)間隔為1的數(shù)字，來表達(dá)他們對于其他用戶的態(tài)度。

2) 維基百科管理員申請網(wǎng)絡(luò)(RfA)：使用文獻(xiàn)[1]中提供的RfA數(shù)據(jù)集，其權(quán)重范圍是[-1,1]。為了便于比較，離散化數(shù)據(jù)集的取值范圍到[-10, 10]，間隔為1，并且僅考慮正邊和負(fù)邊。

三個數(shù)據(jù)集的具體統(tǒng)計描述如表1所示。

表1 數(shù)據(jù)集的統(tǒng)計信息

4.2 評價指標(biāo)

本文選擇根均方誤差(Root Mean Square Error，RMSE)和相關(guān)系數(shù)(Correlation Coefficient，CC)作為權(quán)重預(yù)測性能的評價指標(biāo)。RMSE度量預(yù)測值和真實(shí)值之間的差異程度，其值越小越好。CC度量兩個序列之間的相關(guān)性(真實(shí)值序列和預(yù)測值序列)，該值越高則表明預(yù)測序列的改變趨勢和真實(shí)值序列之間越具有相關(guān)性。

在一個權(quán)重符號社交網(wǎng)絡(luò)中，邊的符號預(yù)測同樣重要。因此，還需探討取得優(yōu)異權(quán)重預(yù)測數(shù)值時的符號預(yù)測性能，即有多少情感傾向被準(zhǔn)確地預(yù)測。本文使用符號準(zhǔn)確率(SignAccuracy, SA)作為符號預(yù)測的評價指標(biāo)(SA=預(yù)測正確的符號數(shù)/總的預(yù)測邊數(shù))。

4.3 參數(shù)分析

WSNE方法包含3個重要的參數(shù)：潛在特征的維度K、控制正則項(xiàng)貢獻(xiàn)的參數(shù)β和控制符號約束貢獻(xiàn)的參數(shù)γ。本文選擇比特幣Alpha數(shù)據(jù)集、RMSE和CC度量指標(biāo)作為例子來闡述參數(shù)的敏感性問題。根據(jù)預(yù)實(shí)驗(yàn)，參數(shù)的分析范圍可以大致確定為：K∈[5,30]，間隔為5；β∈[0.5,2.5]，間隔為0.5；γ∈{1,5,10,15,20}。對三個參數(shù)使用網(wǎng)格搜索，找尋一組性能相對優(yōu)異的參數(shù)取值。為了便于對單個參數(shù)的研究，分析一個參數(shù)時，固定另外兩個參數(shù)。將數(shù)據(jù)集隨機(jī)劃分為兩部分，其中訓(xùn)練集的比例為80%，測試集的比例為20%(本文不考慮冷啟動問題，即未被訓(xùn)練過的節(jié)點(diǎn)不會參與預(yù)測)。對訓(xùn)練集使用五折交叉驗(yàn)證來評估參數(shù)的選擇。使用范圍內(nèi)的隨機(jī)值初始化潛在特征矩陣S和O。重復(fù)實(shí)驗(yàn)5次，取平均值作為最終的結(jié)果。

1) 參數(shù)K。分析參數(shù)K時，固定β=1.5、γ=10，具體的實(shí)驗(yàn)結(jié)果如圖1和圖2所示。

圖2 參數(shù)K的CC值分析結(jié)果

可以看出，隨著K值的增加，RMSE先減小后增大，CC先增大后減小。當(dāng)K取[20, 30]范圍內(nèi)時，RMSE和CC都取得最優(yōu)的結(jié)果。權(quán)重預(yù)測是一種細(xì)粒度的問題，過大的K值會損害權(quán)重預(yù)測的性能。同時K取值越大，需要的存儲空間越多。在實(shí)際操作中，K的取值不宜過大，對于不同的數(shù)據(jù)集而言，K的最優(yōu)取值不同。

2) 參數(shù)β。分析參數(shù)β時，固定K=25、γ=10，具體的實(shí)驗(yàn)結(jié)果如圖3和圖4所示。

圖3 參數(shù)β的RMSE值分析結(jié)果

圖4 參數(shù)β的CC值分析結(jié)果

可以看出，隨著β值的增加，RMSE先減小后增大，CC先增大后減小。當(dāng)β取[1,2]范圍內(nèi)的值時，RMSE取得最優(yōu)值。當(dāng)β取[1.5,2.5]范圍內(nèi)的值時，CC取得最優(yōu)值。β控制著正則項(xiàng)的貢獻(xiàn)，用來避免過擬合問題。過大的β值，將會損害權(quán)重的擬合，從而導(dǎo)致權(quán)重預(yù)測性能下降。

3) 參數(shù)γ。分析參數(shù)γ時，固定K=25、β=1.5，具體的實(shí)驗(yàn)結(jié)果如圖5和圖6所示。

圖5 參數(shù)γ的RMSE值分析結(jié)果

圖6 參數(shù)γ的CC值分析結(jié)果

可以看出，隨著γ值的增加，RMSE先減小后增大，CC先增大后減小。當(dāng)γ的取值在范圍[5, 15]內(nèi)時，RMSE和CC都獲得了最優(yōu)的結(jié)果。γ控制著符號約束的貢獻(xiàn)，適當(dāng)?shù)靥砑臃柤s束能夠提高權(quán)重預(yù)測的性能。但是，過大的符號約束將會引入噪聲，導(dǎo)致權(quán)重預(yù)測性能的降低。

基于上述參數(shù)的分析，為了后續(xù)實(shí)驗(yàn)的便利和各個數(shù)據(jù)集上的統(tǒng)一，本文實(shí)驗(yàn)中設(shè)定K=25、β=1.5、γ=10。

4.4 對比算法

本文選取了如下4個算法進(jìn)行對比：

1) Fairness 和Goodness(FG)[1]。這一算法也用來預(yù)測權(quán)重符號社交網(wǎng)絡(luò)中的邊權(quán)重。該算法提出了兩個度量指標(biāo)：Goodness衡量節(jié)點(diǎn)被其他節(jié)點(diǎn)喜歡的程度，而Fairness用來衡量節(jié)點(diǎn)評價其他節(jié)點(diǎn)的公平性。通過迭代計算來獲得節(jié)點(diǎn)的Fairness和Goodness的值，進(jìn)而用Fairness和Goodness的積預(yù)測邊權(quán)重。這與WSNE的研究背景最相似。

2) node2vec[10]。這是一個無符號社交網(wǎng)絡(luò)嵌入的方法。node2vec擴(kuò)展了節(jié)點(diǎn)鄰居的概念，并且設(shè)計了一個偏好隨機(jī)游走程序來獲取多樣性的鄰居。通過將其與WSNE進(jìn)行比較，驗(yàn)證是否可以直接用傳統(tǒng)無符號網(wǎng)絡(luò)嵌入的方法預(yù)測WSSN中的權(quán)重。

3) SIGNet[14]。這是一個符號網(wǎng)絡(luò)嵌入的方法。SIGNet擴(kuò)展了word2vec嵌入方法，并用于符號社交網(wǎng)絡(luò)。它為每一個節(jié)點(diǎn)構(gòu)造一個緩存，通過從緩存中抽樣來改進(jìn)負(fù)抽樣技術(shù)。與該算法的比較，將驗(yàn)證在WSSN中進(jìn)行權(quán)重預(yù)測時，權(quán)重的符號和數(shù)值這兩個因素之間的關(guān)系。實(shí)驗(yàn)結(jié)果表明，只考慮符號的嵌入，不直接擬合邊的權(quán)重信息并不能獲得滿意的預(yù)測性能。

4) MF[7]。這是一個矩陣分解的方法，使用潛在特征向量之間的點(diǎn)積來擬合邊的權(quán)重。通過比較，能夠進(jìn)一步驗(yàn)證添加符號約束是否能夠改進(jìn)權(quán)重預(yù)測的性能。

本文提出的WSNE算法采用潛在特征向量的點(diǎn)積來擬合邊的權(quán)重信息，并且將符號約束添加到目標(biāo)函數(shù)中以提高權(quán)重預(yù)測的性能。

4.5 結(jié)果與分析

在一個權(quán)重符號社交網(wǎng)絡(luò)中，主要關(guān)注權(quán)重預(yù)測任務(wù)。將數(shù)據(jù)集劃分為兩部分：訓(xùn)練集為80%，測試集為20%。由于無符號網(wǎng)絡(luò)嵌入的方法不能夠處理負(fù)邊，因此，在它嵌入學(xué)習(xí)的過程中刪除負(fù)邊。在實(shí)現(xiàn)對比方法時，本文使用相應(yīng)文獻(xiàn)中提供的默認(rèn)參數(shù)設(shè)定。將對比算法[10, 14]中學(xué)得的節(jié)點(diǎn)潛在特征進(jìn)行級聯(lián)為邊的特征，作為預(yù)測模型的輸入(在權(quán)重預(yù)測中使用線性回歸方法，在符號預(yù)測中使用邏輯回歸方法)。WSNE方法直接使用節(jié)點(diǎn)潛在特征向量的點(diǎn)積來進(jìn)行權(quán)重預(yù)測和符號預(yù)測任務(wù)。

1) 權(quán)重預(yù)測。使用RMSE和CC來評價權(quán)重預(yù)測的性能。實(shí)驗(yàn)結(jié)果如表2所示。

表2 權(quán)重預(yù)測的實(shí)驗(yàn)結(jié)果

可以看出，在所有的情況下，WSNE算法都取得了最優(yōu)的表現(xiàn)。其對于node2vec和SIGNet方法的優(yōu)勢表明直接將無符號網(wǎng)絡(luò)和符號網(wǎng)絡(luò)嵌入的方法用于權(quán)重預(yù)測問題，并不能獲得優(yōu)異的預(yù)測性能。同時，WSNE算法也優(yōu)于MF算法，表明添加符號約束到目標(biāo)函數(shù)中能夠提高權(quán)重預(yù)測的性能。

2) 符號預(yù)測。符號在權(quán)重符號社交網(wǎng)絡(luò)也是非常重要的，因此在已獲得較好的權(quán)重預(yù)測性能的基礎(chǔ)上，本文將進(jìn)一步驗(yàn)證符號預(yù)測的性能。使用SA作為符號預(yù)測的評價指標(biāo)，實(shí)驗(yàn)結(jié)果如表3所示。

表3 符號預(yù)測的實(shí)驗(yàn)結(jié)果

可以看出，在取得優(yōu)異的權(quán)重數(shù)值預(yù)測性能的情況下，WSNE算法也取得了優(yōu)秀的符號預(yù)測性能，即WSNE算法準(zhǔn)確地擬合了邊的符號信息。此外，在RfA數(shù)據(jù)集上，多個方法的性能都是不佳的。這可能是因?yàn)椋琑fA是一個人工生成的權(quán)重符號社交網(wǎng)絡(luò)，在使用語義分析工具將文本內(nèi)容轉(zhuǎn)化為邊權(quán)值時引入了噪音。同時，文獻(xiàn)[1]提供的RfA數(shù)據(jù)集的邊權(quán)范圍為[-1,1]，本文離散化該范圍為[-10,10]，間隔為1。即，對于在(0.1,0.2]范圍內(nèi)的值，離散化為2。再者，也可能是由于RfA數(shù)據(jù)集負(fù)邊比例相對較大，上述算法不能很好地處理負(fù)邊。

3) 稀疏性問題。為了探索數(shù)據(jù)稀疏性問題，本文按照不同的比例來劃分比特幣Alpha數(shù)據(jù)集。增加測試集的比例同時減小訓(xùn)練集的比例，實(shí)驗(yàn)結(jié)果如圖7和圖8所示。

圖7 RMSE值的稀疏性結(jié)果

可以看出，隨著測試集比例的增加，各個算法的性能都有了不同程度的降低。但WSNE算法依舊取得了最優(yōu)的權(quán)重預(yù)測性能，這表明WSNE算法能夠更好地適應(yīng)數(shù)據(jù)稀疏性問題。

5 結(jié) 語

本文提出了一個權(quán)重符號社交網(wǎng)絡(luò)嵌入算法WSNE，來解決權(quán)重符號社交網(wǎng)絡(luò)中的權(quán)重預(yù)測問題。WSNE算法使用每條邊兩個端點(diǎn)的潛在特征向量的點(diǎn)積來擬合邊的權(quán)重。同時該算法考慮到在權(quán)重符號社交網(wǎng)絡(luò)中符號的重要性，提出符號約束并結(jié)合到目標(biāo)函數(shù)中。本文在三個真實(shí)數(shù)據(jù)集上實(shí)現(xiàn)權(quán)重預(yù)測，并與其他相關(guān)且性能優(yōu)秀的算法進(jìn)行了比較，數(shù)值和符號預(yù)測的實(shí)驗(yàn)結(jié)果表明WSNE算法取得了更優(yōu)的社交鏈路預(yù)測性能。

盡管本文算法利用了邊的符號信息來提升權(quán)重預(yù)測的性能，但只考慮了局部的符號約束，在未來的工作中將探索并結(jié)合更多的全局符號約束，以進(jìn)一步提高權(quán)重預(yù)測性能。同時，盡管在數(shù)據(jù)稀疏性問題上WSNE算法的表現(xiàn)都最優(yōu)，但是隨著訓(xùn)練集比例的減少，WSNE算法的性能還是受到了明顯的影響。在未來的工作中，希望利用更多額外的信息，例如節(jié)點(diǎn)的屬性信息，來緩解數(shù)據(jù)稀疏性問題。