結(jié)合重要節(jié)點信任傳播的社會化推薦算法

顧軍華，陳 博，王 銳，張素琪

1.河北工業(yè)大學 人工智能與數(shù)據(jù)科學學院，天津300401

2.河北省大數(shù)據(jù)計算重點實驗室，天津300401

3.天津商業(yè)大學 信息工程學院，天津300134

生活在信息交互頻繁的社會，人們在做各種決定時不僅根據(jù)自身的觀察和判斷，還會考慮信任朋友的觀點。因此，在推薦系統(tǒng)中，用戶的偏好很可能受用戶朋友的影響[1]。基于這一假設，很多研究學者將社交信息融入到推薦算法[2-4]中，以緩解傳統(tǒng)的協(xié)同過濾推薦算法的數(shù)據(jù)稀疏性問題[5-6]和冷啟動問題[7]。

對于社會化推薦算法，眾多學者進行了深入的研究。Ma等人[8]使用概率矩陣分解方法對社交信息和評分信息建模，解決了評分數(shù)據(jù)稀疏性問題和預測精度差的問題，且可以應用于大規(guī)模數(shù)據(jù)集。Yang等人[9]采用矩陣分解技術，將用戶作為信任者和被信任者兩種身份，根據(jù)用戶之間的信任關系將用戶映射到低維的特征空間，以更好地挖掘被信任者對信任者的影響，進而得到更為準確的推薦結(jié)果。Rafailidis等人[10]提出了一種利用用戶信任和不信任關系的學習排序模型，將用戶及其信任用戶喜愛的項目放到推薦列表的最前面，而將其不信任用戶喜愛的項目排在后面。王衛(wèi)紅等人[11]從社交網(wǎng)絡獲得用戶之間的相似度，再利用聚類算法填充評分矩陣的缺失值，最后通過協(xié)同過濾算法進行推薦。這些方法均利用了社交網(wǎng)絡中的二值數(shù)據(jù)，在一定程度上提高了推薦算法的有效性，但僅僅利用用戶的直接信任關系，忽略了用戶之間的間接聯(lián)系。

總體而言，當前的社會化推薦算法未能充分利用社交信息，忽視了用戶之間的間接聯(lián)系，且僅僅利用社交信息中的二值數(shù)據(jù)，未考慮用戶之間信任的權重問題，降低了推薦算法的精度。因此，本文針對社交信息的稀疏性問題和用戶間信任權重問題進行研究，提出一種結(jié)合重要節(jié)點信任傳播的社會化推薦算法（INTP-Rec）。首先利用重啟隨機游走算法得到社交網(wǎng)絡中的重要節(jié)點，然后提出重要節(jié)點信任傳播算法（INTP），來捕獲用戶之間的間接信任關系，進而豐富社交信息。同時量化用戶之間的信任關系，以提高推薦算法的準確度。經(jīng)過實驗證明，本文提出的方法能有效地緩解社交信息的稀疏性問題，并提高推薦算法的精度。

1 問題描述

本章首先對社會化推薦算法進行簡要描述，然后提出信任傳播和信任量化問題。

1.1 社會化推薦算法

社交信息可以通過社交網(wǎng)絡圖表示出來，如圖1（a）所示。其中，圓形表示用戶節(jié)點，節(jié)點之間的連接表示用戶之間的信任關系。社會化推薦算法，是利用用戶之間的信任關系，認為在社交網(wǎng)絡中相互信任的用戶具有相似的偏好，進而向用戶做出推薦[12]。觀察圖1（a）中的用戶節(jié)點1、用戶節(jié)點2和兩個節(jié)點對項目的喜愛關系，說明社交推薦的過程，如圖1（b）所示。其中，方形表示項目節(jié)點，用戶節(jié)點與項目節(jié)點之間相連的實線邊表示喜愛關系，虛線邊表示推薦關系。為用戶節(jié)點2推薦項目，并將社交推薦過程中所需的邊關系加粗。通過社交網(wǎng)絡圖可知，用戶2信任用戶1，因此假設用戶2與用戶1具有相似的偏好，并將用戶1喜愛的項目b推薦給用戶2。

圖1 社會化推薦Fig.1 Social recommendation

1.2 信任傳播和信任量化

將社交信息融入到推薦算法中，在一定程度上緩解了數(shù)據(jù)稀疏性問題和冷啟動問題，但是由于用戶間的直接聯(lián)系很少，導致可利用的社交信息較少，降低了社會化推薦算法的準確度。因此，本文提出一種重要節(jié)點信任傳播的算法（INTP），以挖掘社交網(wǎng)絡中的重要節(jié)點，并通過信任在重要節(jié)點和其間接相連節(jié)點之間的傳播，得到兩者之間的信任關系。信任傳播過程如圖2所示，其中，節(jié)點1為重要節(jié)點，節(jié)點6通過節(jié)點2與節(jié)點1間接相連，兩者之間以虛線連接，當兩者滿足信任傳播的條件時，建立由節(jié)點6指向節(jié)點1的信任關系，為社交網(wǎng)絡圖增加連接邊。本文將在第2章中詳細說明INTP算法。

圖2 信任傳播過程Fig.2 Trust propagation process

為獲得更精確的推薦結(jié)果，本文將優(yōu)化后的社交網(wǎng)絡上的二值數(shù)據(jù)進行加權量化，來進一步反映社交網(wǎng)絡的整體結(jié)構(gòu)信息，具體方法在下面內(nèi)容中詳細說明。

2 INTP算法

本章提出基于重啟隨機游走的重要節(jié)點信任傳播算法（INTP），以增補社交信息中用戶之間關系的缺失值，進而解決社交信息的稀疏性問題。在該算法中，首先通過重啟隨機游走算法RWR（Random Walk with Restart）得到社交網(wǎng)絡圖的重要節(jié)點，其次確定在社交網(wǎng)絡圖中信任通過重要節(jié)點向外傳播的條件，以判斷用戶節(jié)點是否受到重要節(jié)點的影響，然后建立受到影響的用戶節(jié)點與重要節(jié)點之間的連接，從而豐富社交信息，最后為增加連接邊后的社交網(wǎng)絡圖增加邊權重，以提高推薦效果。

2.1 確定社交網(wǎng)絡圖的重要節(jié)點

在社會生活中存在小部分人，他們的個人行為會對很多人造成影響，比如，網(wǎng)紅效應，當知名網(wǎng)紅博主使用并推薦一款產(chǎn)品時，眾多信任這位博主的人會去購買這款產(chǎn)品。因此，在社交網(wǎng)絡圖中，如果一個用戶節(jié)點對很多節(jié)點都具有很大的影響力，那么就把這個用戶節(jié)點定義為重要節(jié)點。在圖1（a）中可以看出節(jié)點1受到大量其他用戶節(jié)點的信任，由此可以認為，節(jié)點1是圖1（a）中的重要節(jié)點，可以影響社交網(wǎng)絡中的其他節(jié)點。因此，根據(jù)重要節(jié)點被大量其他節(jié)點信任的特點，本文使用重啟隨機游走算法對用戶節(jié)點的重要程度進行排序，以篩選出在整個網(wǎng)絡中有影響力，值得信任的重要節(jié)點。

重啟隨機游走算法最早用以解決互聯(lián)網(wǎng)頁面的重要性排序問題[13]。本文將用戶節(jié)點比作網(wǎng)頁，用戶間的信任關系比作網(wǎng)頁間的跳轉(zhuǎn)關系。RWR確定重要節(jié)點的步驟如下：給定一個加權有向圖G，用V表示圖G的節(jié)點集合，N表示圖G的節(jié)點個數(shù)，A表示圖G的鄰接矩陣，Aij表示節(jié)點i和節(jié)點j之間有無連接，當從節(jié)點i出發(fā)有邊連向節(jié)點j時，Aij=1，否則Aij=0。用P表示圖G的轉(zhuǎn)移概率矩陣，P里面的每一個元素Pij表示節(jié)點i跳轉(zhuǎn)到節(jié)點j的概率值，具體如公式（1）所示：

RWR算法通過一個參數(shù)α來調(diào)節(jié)游走者繼續(xù)跳轉(zhuǎn)或者返回初始節(jié)點的概率，游走者在每次跳轉(zhuǎn)時都有α的概率跳轉(zhuǎn)到當前節(jié)點的鄰接節(jié)點上，或者以1-α的概率返回初始節(jié)點，圖G中的每個節(jié)點都有1/N的概率成為初始節(jié)點，具體如公式（2）所示：

式中，x表示節(jié)點的重要程度向量，t表示迭代次數(shù)，xt和xt+1是經(jīng)過t和t+1次迭代后的向量，x0是一個重啟向量，每個節(jié)點對應位置的元素值為1/N。當向量x收斂后結(jié)束RWR算法[14]，向量x中的N個元素表示每個節(jié)點的重要程度值。最后，取重要程度值較高的節(jié)點放入重要節(jié)點集合S，S中節(jié)點的數(shù)目為節(jié)點總數(shù)的1%。

2.2 重要節(jié)點的信任傳播

在社交網(wǎng)絡圖中，重要節(jié)點對其他用戶節(jié)點有較大的影響。因此，信任可以通過社交網(wǎng)絡中的邊由重要節(jié)點向其他用戶節(jié)點傳播。

將社交網(wǎng)絡圖建模為一個加權有向圖G=(V,E,W)，用V表示圖G的節(jié)點集合，E是邊的集合，W是邊權重的集合。在圖G中，從用戶節(jié)點u指向重要節(jié)點v的一條邊(u→v)表示用戶u信任用戶v。信任傳播算法的目標是識別出信任重要節(jié)點且沒有與重要節(jié)點直接相連的用戶節(jié)點，并為識別出的用戶節(jié)點與重要節(jié)點建立連接邊，進而減小社交網(wǎng)絡的稀疏度。

在社交網(wǎng)絡圖中，邊的權重由構(gòu)成邊的兩個用戶節(jié)點的結(jié)構(gòu)特征確定。因此，使用直接信任權重w(uv)表示用戶節(jié)點u對重要節(jié)點v的信任程度，定義為：

其中，Iv表示為用戶節(jié)點v的入度，Ou表示為用戶節(jié)點u的出度。只有當邊的直接信任權重w(uv)大于等于用戶節(jié)點u的閾值時，該算法認為用戶節(jié)點u信任重要節(jié)點v。

為增加間接信任關系，算法選擇與用戶節(jié)點u相連而與重要節(jié)點v無連接的用戶節(jié)點p(p→u→v)，判斷用戶節(jié)點p是否信任重要節(jié)點v。當直接信任權重w(uv)大于等于用戶節(jié)點u的閾值且間接信任權重w'(pv)大于等于用戶節(jié)點p的閾值時，認為節(jié)點p和v之間存在信任關系，并為用戶節(jié)點p和重要節(jié)點v建立連接。間接信任權重w'(pv)的計算方法如下：

其中，decay為信任傳播中的衰減系數(shù)，用于表示信任間接傳播造成的影響。在該算法中，衰減系數(shù)為常數(shù)，取值0.1。

本文提出兩種判斷用戶之間是否信任的閾值條件，并在第4章中對兩種閾值條件進行重要節(jié)點信任傳播算法影響實驗。

條件1：將整個網(wǎng)絡邊權值的均值作為閾值，在此條件下，每個節(jié)點的閾值為同一個常數(shù)。

條件2：選擇節(jié)點的所有輸出邊的邊權值的均值作為閾值，在此條件下，每個節(jié)點的閾值為不同的常數(shù)。

選擇條件2作為閾值判斷條件，通過重要節(jié)點信任傳播算法為圖1（a）的社交網(wǎng)絡圖增加連接邊，具體結(jié)果如圖3所示。其中，邊上的值為節(jié)點間的信任權重w，利用公式（3）得出。通過條件2得知用戶節(jié)點2的閾值為4，等于w(21)?？蛇M一步判斷與重要節(jié)點1間接相連的節(jié)點6是否信任重要節(jié)點。利用公式（4）得出w'(61)為2.2，大于節(jié)點6的閾值2。因此，用戶節(jié)點6信任重要節(jié)點1，并為兩者建立連接邊。

圖3 重要節(jié)點信任傳播算法Fig.3 Important nodes trust propagation algorithm

2.3 二值數(shù)據(jù)加權量化

在前面方法中得到了一些新的用戶之間存在信任關系的邊，將這些新得到的邊加入到社交網(wǎng)絡圖G=(V,E,W)中，由此得到更豐富的社交信息。之后，為獲得更為精確的推薦結(jié)果，利用公式（5）對社交信息中的二值數(shù)據(jù)進行進一步加權量化。

其中，為用戶i對用戶j的最終信任權重，Tij表示用戶i是否信任用戶j，當信任時，值為1，否則值為0。

3 結(jié)合重要節(jié)點信任傳播的社會化推薦算法

SoRec算法是最為經(jīng)典的社會化推薦算法，其假設用戶評分系統(tǒng)和社交網(wǎng)絡共享相同的偏好空間，使用概率矩陣分解的方法進行建模。該模型使用矩陣U、V、Z分別表示用戶特征矩陣、項目特征矩陣和信任因子特征矩陣，使用R、T表示評分矩陣和信任矩陣。該模型的概率圖模型如圖4所示。

圖4 SoRec概率圖模型Fig.4 SoRec probabilistic graphical model

SoRec模型定義評分矩陣和信任矩陣的似然函數(shù)分別為：

該模型根據(jù)貝葉斯推斷，后驗概率∝似然函數(shù)?先驗概率，得到特征矩陣的后驗概率為評分矩陣和信任矩陣的似然函數(shù)與特征矩陣U、V、Z的先驗概率分布相乘，最終的結(jié)果為：

通過利用隨機梯度下降方法（SGD）或交替最小二乘法（ALS），求解矩陣U、V使得公式（8）的后驗概率最大化，最后通過預測用戶Ui對項目Vj的評分[15]。

本文將INTP算法應用于SoRec算法中，以判斷INTP算法在豐富社交信息，提高推薦算法精度上的有效性。在算法1中詳細描述了結(jié)合重要節(jié)點信任傳播的社會化推薦算法，其中T(u)表示信任節(jié)點u的節(jié)點集合，集合中任意節(jié)點與節(jié)點u之間存在直接相連的邊。

算法1INTP-Rec

輸入：社交網(wǎng)絡圖G=(V,E,W)，用戶評分矩陣R。

輸出：預測評分結(jié)果Rij。

步驟1初始化衰減系數(shù)decay=0.1，訪問系數(shù)visit=0。

步驟2根據(jù)公式（2）計算用戶節(jié)點重要程度排名x，獲得重要節(jié)點集合S。

步驟3根據(jù)公式（3）計算社交網(wǎng)絡中每條邊信任權重w，獲得用戶節(jié)點閾值thr。

步驟4for eachv∈Sdo

if?E(u→v)andw(uv)≥thr(u)：

visit=1；

end if

whilevisit=1 do

visit=0；

for eachp∈T(u)

w(pv)=w(pu)×(1+decay)；

ifw(pv)>thr(u)：

E(p→v)//向社交網(wǎng)絡圖G中增加由節(jié)點p指向重要節(jié)點v的邊

步驟5根據(jù)公式（5）對增加邊之后社交信息進行進一步優(yōu)化，得到。

步驟6將代替T放入公式（8），并利用SGD計算出U、V。

步驟7得到用戶對項目的評分，輸出對用戶的推薦結(jié)果。

4 實驗分析

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

為保證實驗的準確性，本文選擇了三個獨立公開的數(shù)據(jù)集（Epinions數(shù)據(jù)集[16]、FilmTrust數(shù)據(jù)集[17]、Douban數(shù)據(jù)集[18]）進行實驗。三個數(shù)據(jù)集均同時包含評分數(shù)據(jù)和社交信任數(shù)據(jù)，其中Epinions數(shù)據(jù)集和FilmTrust數(shù)據(jù)集中的社交網(wǎng)絡是有向圖，而Douban數(shù)據(jù)集中的社交網(wǎng)絡是無向圖，因此，將Douban數(shù)據(jù)集中的每條邊按照雙向信任的規(guī)則進行實驗，各個數(shù)據(jù)集的詳細信息如表1所示。

表1 數(shù)據(jù)集詳細信息Table 1 Dataset details

4.2 實驗指標及對比方法

在社交網(wǎng)絡圖中，如果一個用戶節(jié)點對很多節(jié)點都具有很大的影響力，實驗使用準確率（Precision）、召回率（Recall）、F1值和均方根誤差（RMSE）作為模型推薦性能的評估標準。每個評估標準的計算方法如下：

其中，F(xiàn)av(u)表示用戶u真實喜愛項目集合，Rec(u)表示推薦算法為用戶u推薦的項目集合。

為了全面地評價本文提出的INTP-Rec模型的推薦效果，本文將對比以下三種算法：

（1）概率矩陣分解算法（PMF）[19]，使用貝葉斯概率矩陣分解的方法對用戶-項目評分矩陣進行分解，得到用戶項目特征矩陣。

（2）基于概率矩陣分解的社會化推薦算法（SoRec）[8]，使用貝葉斯概率矩陣分解的方法建立用戶偏好與信任關系之間的關聯(lián)。

（3）基于信任的協(xié)同過濾社會化推薦算法（TrustPMF）[9]，考慮到信任用戶與被信任用戶之間的聯(lián)系。

其中，PMF算法僅利用評分數(shù)據(jù)進行推薦，而SoRec和TrustPMF方法同時使用信任信息和評分數(shù)據(jù)進行推薦。

4.3 實驗結(jié)果

本節(jié)首先通過實驗確定判斷節(jié)點之間是否信任的閾值條件，然后衡量重要節(jié)點信任傳播算法在緩解社交信息稀疏性問題上的有效性，最后通過與其他四種推薦算法的對比，證明本文提出的INTP-Rec方法能有效地提高推薦算法的精度。

4.3.1 用戶節(jié)點閾值選擇實驗

本組實驗的目的是，驗證2.2節(jié)中兩種不同的閾值條件對推薦算法的影響，并根據(jù)實驗結(jié)果選擇最優(yōu)的閾值條件加入到本文的推薦算法INTP-Rec的設置中。其中閾值是INTP算法中判斷信任能否在節(jié)點之間傳播的重要條件。

本部分實驗將SoRec[8]算法作為基本方法，使用兩種閾值條件與原始的算法進行對比實驗，實驗指標使用RMSE。具體實驗結(jié)果如表2所示。

表2 不同閾值實驗效果對比Table 2 Comparison of different threshold experimental results

表2中的粗體為三種方法得到的實驗結(jié)果在該數(shù)據(jù)集上的最大值。從優(yōu)化前后的對比結(jié)果來看，優(yōu)化后的提升效果較為明顯，說明使用信任傳播算法對社交信息進行優(yōu)化，提高了推薦算法的精度。從條件1與條件2的實驗結(jié)果對比來看，條件2的結(jié)果更為理想，說明選擇節(jié)點的所有輸出邊的邊權值的均值作為閾值更能夠取得較好的推薦效果。條件2相較于條件1為每一個節(jié)點按照節(jié)點自身結(jié)構(gòu)特征做出判斷，所以更可能取得好的推薦效果。在之后的實驗中，本文均選擇條件2作為閾值確定的條件。

4.3.2 社交信息稀疏度緩解實驗

本組實驗的目的是，通過對比原始社交網(wǎng)絡的邊數(shù)和經(jīng)過信任傳播算法優(yōu)化后的社交網(wǎng)絡的邊數(shù)，來驗證INTP算法是否能夠緩解社交信息的稀疏性問題。實驗將重要節(jié)點信任傳播算法分別應用于Epinions、FilmTrust和Douban三個真實數(shù)據(jù)集，對數(shù)據(jù)集中的社交信息進行優(yōu)化。具體實驗結(jié)果如表3所示，其中N-TP表示社交網(wǎng)絡圖原始的邊數(shù)，TP表示經(jīng)過信任傳播算法優(yōu)化后的新的社交網(wǎng)絡圖的邊數(shù)。

表3 INTP優(yōu)化前后信任邊數(shù)對比Table 3 Comparison of trust sides before and after INTP optimization

由表3中三個數(shù)據(jù)集上的對比實驗可以看出，經(jīng)過INTP算法優(yōu)化的社交網(wǎng)絡的邊數(shù)得到增加。實驗結(jié)果表明INTP算法可以有效地緩解社交數(shù)據(jù)的稀疏性問題。

4.3.3 INTP算法應用效果實驗

本組實驗的目的是，將INTP算法應用到其他推薦算法上，以驗證其在全局數(shù)據(jù)上的推薦效果。實驗分為兩部分：（1）將INTP算法融入到SoRec算法和TrustPMF算法中進行實驗，使用RMSE作為評價指標與原始實驗算法效果對比，來驗證信任傳播算法在提高推薦算法精度上的有效性；（2）使用準確率、召回率和F1值作為衡量推薦質(zhì)量的指標，將INTP算法融入到SoRec算法中與其他方法推薦效果對比，來驗證信任傳播算法在提高推薦算法準確度上的有效性。對比結(jié)果如表4、5所示。

表4 INTP評分預測精度實驗Table 4 Score prediction accuracy experiment of INTP

通過表4中的實驗數(shù)據(jù)可以看出，將INTP算法融入SoRec算法和TrustPMF算法，能使推薦算法的精度提高，說明將INTP算法融入到推薦系統(tǒng)中可以有效地提高推薦效果。

表5中的粗體為五種方法得到的實驗結(jié)果在該數(shù)據(jù)集上的最大值。從表5中可以看出，與CF、PMF這些傳統(tǒng)的協(xié)同過濾推薦算法相比，融入社交信息的社會化推薦算法INTP-Rec表現(xiàn)更好，說明向推薦算法中融入社交信息能提高推薦算法的有效性。與使用原始社交信息的SoRec算法相比，緩解了社交信息稀疏性問題的INTP-Rec算法表現(xiàn)更好，說明了INTP-Rec算法能有效地提高推薦算法的精度，得到更好的推薦結(jié)果。對于整體實驗結(jié)果而言，本文方法在準確率、召回率和F1值上，均比其他方法在一定程度上得到提高，表明本文方法可以有效地提高推薦算法的質(zhì)量。

表5 項目推薦質(zhì)量實驗Table 5 Recommended quality experiment

5 結(jié)束語

為解決社交網(wǎng)絡中信任數(shù)據(jù)稀疏問題和二值數(shù)據(jù)難以反映社交網(wǎng)絡整體結(jié)構(gòu)問題，本文提出結(jié)合重要節(jié)點信任傳播的社會化推薦算法（INTP-Rec）。首先利用重要節(jié)點信任傳播算法（INTP），增加重要節(jié)點與其他節(jié)點之間的連接，并通過實驗驗證了該方法在豐富社交信息上的有效性。之后將優(yōu)化后的社交網(wǎng)絡上的二值數(shù)據(jù)進行加權量化，以進一步反映社交網(wǎng)絡的整體結(jié)構(gòu)信息。最后，在三個公開數(shù)據(jù)集上的實驗表明，本文提出的結(jié)合重要節(jié)點信任傳播的社會化推薦算法可以提高社會化推薦算法的準確率、召回率和F1值，達到了更好的推薦效果。