融合社交信任的多屬性元路徑好友推薦方法

朱文強(qiáng)，徐 軍

1(江西財(cái)經(jīng)大學(xué) 軟件與物聯(lián)網(wǎng)工程學(xué)院，南昌 330013) 2(江西財(cái)經(jīng)大學(xué) 統(tǒng)計(jì)學(xué)院，南昌 330013)

1 引 言

隨著社交網(wǎng)絡(luò)的蓬勃發(fā)展，好友推薦成了社交網(wǎng)絡(luò)的重要服務(wù)之一[1].如Facebook會(huì)基于用戶手機(jī)號(hào)、郵箱地址、MSN號(hào)等屬性信息為用戶進(jìn)行好友推薦，微信提供了“搖一搖”來進(jìn)行基于地域距離的好友推薦，QQ則可根據(jù)共同好友數(shù)量或手機(jī)通訊錄進(jìn)行好友推薦，新浪微博也提供了為用戶推薦微博好友的功能.通過好友推薦，用戶可快速擴(kuò)展朋友圈，使信息來源變得豐富多樣，進(jìn)行更好的信息共享、過濾和篩選，從而使目前Internet上的信息過載問題得以緩解.

好友推薦的主要任務(wù)是為用戶推薦好友候選人，以便他更加有效的選擇朋友，因此最大的挑戰(zhàn)是如何精確的計(jì)算目標(biāo)用戶的需求，為其發(fā)現(xiàn)他真正需要的朋友[2,3].現(xiàn)有的好友推薦方法大致可以分為三類：基于友情關(guān)聯(lián)的好友推薦，基于用戶屬性特征的好友推薦和基于位置的好友推薦.

其中，基于友情關(guān)聯(lián)的好友推薦是根據(jù)用戶的交互、情感表達(dá)或社交相似度等進(jìn)行好友推薦.因?yàn)橛脩艨梢钥闯墒枪?jié)點(diǎn)，而友情關(guān)聯(lián)可以看成為邊，因此這類推薦方法通常也可被解釋為鏈路預(yù)測推薦方法[4].

基于用戶屬性特征的好友推薦，是根據(jù)用戶的屬性特征內(nèi)容，進(jìn)行興趣點(diǎn)分析，進(jìn)而計(jì)算用戶之間的興趣相似度，為目標(biāo)用戶進(jìn)行候選好友推薦.該類推薦方法基于以下假設(shè)，具有共同興趣的人，往往在情感上更加容易有共鳴，因此可以基于用戶屬性特征進(jìn)行好友推薦[5].

基于位置的好友推薦，則是根據(jù)用戶之間的地域距離和日常訪問地點(diǎn)來進(jìn)行好友推薦.人們的活動(dòng)范圍通常都只局限于某一地理區(qū)域，在該范圍的用戶如果有一些經(jīng)常訪問的共同地點(diǎn)，則他們之間可能有共同的行為習(xí)慣，因此也具備成為好友的可能性[6].

基于友情關(guān)聯(lián)、用戶屬性和位置的好友推薦，本質(zhì)上都可解釋為基于異構(gòu)網(wǎng)絡(luò)的好友推薦.然而，上述的好友推薦方法大多基于用戶的興趣偏好、行為軌跡或社交信息來為目標(biāo)用戶推薦候選好友，未考慮好友推薦所基于的社交網(wǎng)絡(luò)的異構(gòu)網(wǎng)絡(luò)特征，同時(shí)也容易受到惡意用戶的托攻擊，從而使目標(biāo)用戶的利益受到損害[7,8].

基于上述分析，本文提出了一種融合社交信任的多屬性元路徑好友推薦方法，該方法分析了在線社交的異構(gòu)網(wǎng)絡(luò)特征，使用元路徑理論對好友推薦的異構(gòu)網(wǎng)絡(luò)進(jìn)行抽象和形式化，提出了ULTNM(User Local Trust Network Model)信任模型.該信任模型考慮了元路徑上的用戶社交圈子相似度和統(tǒng)計(jì)興趣偏好相似度等多種屬性特征，構(gòu)建了目標(biāo)用戶的本地信任網(wǎng)絡(luò)，并通過Ford Fulkerson算法對信任網(wǎng)絡(luò)進(jìn)行搜索和排序，進(jìn)行目標(biāo)用戶的候選好友推薦.基于真實(shí)數(shù)據(jù)集的對比實(shí)驗(yàn)表明，該推薦方法有更好的推薦準(zhǔn)確率和召回率，能更好的對抗惡意用戶的托攻擊行為，且運(yùn)行效率具有一定的優(yōu)勢.

2 相關(guān)工作

有效的好友推薦，能迅速擴(kuò)大用戶的社交范圍，增加用戶的社會(huì)影響力，為用戶提供有效的感情聯(lián)絡(luò)、信息咨詢及資源共享等功能，成為了當(dāng)下推薦系統(tǒng)的研究熱點(diǎn).現(xiàn)有的好友推薦方法大致可分為以下三類.

1)基于用戶之間的友情關(guān)聯(lián)，進(jìn)行好友推薦.Zheng等人[9]從最大化用戶社交影響力的角度進(jìn)行研究，考慮多路徑友情傳導(dǎo)，計(jì)算用戶的社會(huì)影響力擴(kuò)散效果，提出了一個(gè)概率近似為1-1/ε的貪婪好友推薦算法.基于好友關(guān)聯(lián)、用戶的歷史評(píng)價(jià)和項(xiàng)目的評(píng)論標(biāo)簽，文獻(xiàn)[10]提出了一個(gè)混合好友推薦算法GBLP(Group-Based Link Prediction Model)，該模型先通過不同的社交屬性特征來區(qū)分社交圈子，然后計(jì)算用戶的社交圈子歸屬度，并將歸屬度融合進(jìn)用戶的社交目的模型，進(jìn)而為目標(biāo)用戶進(jìn)行好友推薦.Yang等人[11]基于交互頻率對用戶進(jìn)行區(qū)分，并根據(jù)用戶的屬性特征進(jìn)行社交網(wǎng)絡(luò)相似度計(jì)算，最后預(yù)測用戶的交友興趣和目的.文獻(xiàn)[12]將好友推薦分為兩個(gè)階段，首先，它根據(jù)用戶發(fā)布的信息和友情關(guān)聯(lián)來進(jìn)行候選好友篩選；在此基礎(chǔ)上，利用用戶的興趣屬性特征來進(jìn)行結(jié)果修正，取得了較好的實(shí)驗(yàn)效果.

2)基于用戶的興趣屬性特征，進(jìn)行好友推薦.Khalid等人[13]通過融合蟻群算法、社交過濾、授權(quán)得分等內(nèi)容，提出了一個(gè)基于云框架的優(yōu)化好友推薦算法，在好友篩選的過程中，使用了好友興趣相似度來進(jìn)一步提高推薦算法的精度.通過研究推薦方法的屬性選擇過程，Ding等人[14]提出了一個(gè)有效的屬性過濾方法，以過濾掉不相關(guān)和冗余的用戶屬性特征，從而提高好友推薦方法的效果.文獻(xiàn)[15]研究了用戶的活動(dòng)頻率數(shù)據(jù)，設(shè)計(jì)了一個(gè)FP-Growth增長模型來預(yù)測用戶的活動(dòng)趨勢，并使用多層閾值過濾來過濾用戶的行為數(shù)據(jù)噪音，提出了一個(gè)FRF好友推薦框架為進(jìn)行好友推薦.用戶之間的友情常常是主觀的，因此模糊數(shù)學(xué)在表示好友關(guān)系方面有較好的優(yōu)勢，文獻(xiàn)[16]在用戶標(biāo)簽和項(xiàng)目描述的基礎(chǔ)上，構(gòu)建了兩個(gè)模糊數(shù)據(jù)集，提出了使用模糊關(guān)聯(lián)來表達(dá)用戶簽名的概念，通過為每個(gè)用戶構(gòu)建用戶簽名，可以更精確的找到用戶興趣點(diǎn)，從而產(chǎn)生相似性好友推薦.

3)基于用戶的地理位置信息，進(jìn)行好友推薦.Lin等人[17]通過對現(xiàn)有的好友推薦算法進(jìn)行分析研究，提出了三個(gè)改進(jìn)后的好友推薦方法，即基于社交相似度的好友推薦方法、基于經(jīng)典協(xié)同過濾的好友推薦方法和基于用戶地理軌跡簽到信息的好友推薦方法，并使用線性框架對它們進(jìn)行融合，取得了較好的實(shí)驗(yàn)效果.通過對用戶的居住點(diǎn)和活動(dòng)區(qū)域進(jìn)行區(qū)分，文獻(xiàn)[18]提出了一個(gè)基于區(qū)域挖掘的好友推薦方法，該方法使用θ-ADBSCAN區(qū)域算法來挖掘用戶所在區(qū)域的日?；顒?dòng)軌跡和居住點(diǎn)，并使用分段活動(dòng)地點(diǎn)和用戶活動(dòng)軌跡來代替用戶區(qū)域，然后將這些內(nèi)容轉(zhuǎn)化為多層次的地理位置編碼，最后基于這些內(nèi)容對用戶的行為相似性進(jìn)行分析，進(jìn)行好友推薦.用戶的線上好友信息和線下活動(dòng)行為是用戶交友傾向和位置偏好的重要參考內(nèi)容，基于此，文獻(xiàn)[19]提出了一個(gè)基于用戶位置偏好的好友推薦方法，取得較好的實(shí)驗(yàn)對比效果.

另外，從信息安全的角度考慮，也有不少研究人員對好友推薦的隱私保護(hù)進(jìn)行了分析研究.為避免好友推薦的隨機(jī)性和不可靠性，文獻(xiàn)[20]基于隱私保護(hù)協(xié)議提出了一個(gè)安全有效的好友推薦框架，當(dāng)目標(biāo)用戶發(fā)送好友請求到授權(quán)中心時(shí)，授權(quán)中心通過基于隱私保護(hù)的標(biāo)簽匹配從所有用戶中選出好友候選人，并根據(jù)他們與目標(biāo)用戶的相似性閾值來為目標(biāo)用戶進(jìn)行好友推薦.Zhang等人[21]針對目前好友推薦方法中存在的身份竊取和隱私泄露等問題，提出了一個(gè)K度匿名好友推薦框架，該框架首先建立了在線社交網(wǎng)絡(luò)超圖，然后提出邊分割算法來隱藏用戶的身份信息和社交關(guān)系，再根據(jù)用戶的興趣特征，來計(jì)算用戶之間的相似性，最后融合用戶相似性和邊分割算法進(jìn)行好友推薦.

綜合分析，現(xiàn)有的好友推薦算法存在以下問題：

1)未深入考慮好友推薦所基于的社交網(wǎng)絡(luò)的異構(gòu)網(wǎng)絡(luò)特征，導(dǎo)致好友推薦準(zhǔn)確度不高.

2)大多基于用戶的興趣偏好或行為軌跡來進(jìn)行好友推薦，不能有效抵御惡意用戶的托攻擊，導(dǎo)致目標(biāo)用戶的利益受損.

3)基于整個(gè)用戶-用戶社交矩陣和用戶-項(xiàng)目評(píng)價(jià)矩陣計(jì)算用戶之間的隱含友情關(guān)聯(lián)，計(jì)算工作量較大.

3 ULTNM信任模型

3.1 理論基礎(chǔ)

3.1.1 異構(gòu)網(wǎng)絡(luò)

異構(gòu)網(wǎng)絡(luò)是指存在不同性質(zhì)節(jié)點(diǎn)的信息網(wǎng)絡(luò)，可采用三元組G表示.其中，V表示異構(gòu)網(wǎng)絡(luò)中節(jié)點(diǎn)的集合,E表示異構(gòu)網(wǎng)絡(luò)中邊的集合，T表示節(jié)點(diǎn)類型的集合[22].好友推薦基于在線社交網(wǎng)絡(luò)產(chǎn)生，是典型的異構(gòu)網(wǎng)絡(luò)，包括兩種類型節(jié)點(diǎn)：用戶節(jié)點(diǎn)和項(xiàng)目節(jié)點(diǎn).還包括三類關(guān)系邊：用戶-用戶邊，表示用戶的社交關(guān)系；用戶-項(xiàng)目邊，表示用戶對項(xiàng)目的使用或評(píng)分關(guān)系；項(xiàng)目-項(xiàng)目邊，表示項(xiàng)目之間的關(guān)聯(lián).好友推薦所基于的異構(gòu)網(wǎng)絡(luò)如圖1所示.

圖1 好友推薦所基于的異構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)Fig.1 Example of heterogeneous network for friend recommendation

在本文中，我們將好友推薦所基于的社交網(wǎng)絡(luò)構(gòu)建為帶權(quán)值的異構(gòu)網(wǎng)絡(luò)，用四元組G表示.其中：

1)U={u1,u2,…,un}為用戶節(jié)點(diǎn)集合，n為用戶集的大??；

2)I={i1,i2,…,im}為項(xiàng)目集合，m為項(xiàng)目集的大小；

3)E=EUU∪EUI∪EII為異構(gòu)網(wǎng)絡(luò)中所有邊的集合.EUU={uk,uj|uk∈U,uj∈U}表示用戶之間的邊集合，即他們之間的社交關(guān)系；EUI={uk,ij|uk∈U,ij∈I}表示用戶與項(xiàng)目之間的邊集合，即用戶與項(xiàng)目的使用關(guān)系；EII={ik,ij|ik∈I,ij∈I}表示項(xiàng)目與項(xiàng)目之間的邊集合，即項(xiàng)目與項(xiàng)目之間的關(guān)聯(lián)關(guān)系.在本文中，我們認(rèn)為是EUU有向邊,因?yàn)橛脩糁g的友情往往不是對等的，比如用戶A認(rèn)為用戶B是他最好的朋友，但反過來不一定成立.EUI同樣也是有向邊，因?yàn)橹淮嬖谟脩羰褂庙?xiàng)目的情況.而EII是無向邊，即兩個(gè)項(xiàng)目相關(guān)的話，他們是對等的.為了方便處理，我們統(tǒng)統(tǒng)將這三類關(guān)系作為有向邊進(jìn)行計(jì)算；

4)W=WUU∪WUI∪WII是異構(gòu)網(wǎng)絡(luò)中邊的權(quán)重.WUU={w(uk,uj)|(uk,uj)∈EUU}表示用戶邊的權(quán)重集合，即他們之間的社交親密程度；WUI={w(uk,ij)|(uk,ij)∈EUI}表示用戶與項(xiàng)目之間權(quán)重集合，即用戶對項(xiàng)目的偏好程度；EII={w(ik,ij)|(ik,ij)∈EII}表示項(xiàng)目與項(xiàng)目之間權(quán)重集合，即項(xiàng)目與項(xiàng)目之間的相似程度.

3.1.2 元路徑

元路徑(meta-path)主要用來描述異構(gòu)網(wǎng)絡(luò)中節(jié)點(diǎn)間不同連接類型[22].元路徑的相關(guān)定義如下.

根據(jù)六度空間理論[24]和三度影響力理論[25]，在社交網(wǎng)絡(luò)中，3跳以內(nèi)的連接可信度較好，而3跳以外的連接可信度相對較弱，因此本文主要考慮路徑長度不大于3的元路徑，元路徑集包括以下幾類.

Ⅰ類元路徑：U-U-U與U-U-U-U，目標(biāo)用戶與好友的好友具備成為好友的可能性.U-U-U和U-U-U-U元路徑是本文好友推薦算法所基于的主要元路徑，稱之為I類元路徑.

Ⅱ類元路徑：U-I-U，對于有相同項(xiàng)目興趣的用戶，他們具備成為好友的可能性.

Ⅲ類元路徑：U-I-U-U，目標(biāo)用戶與有相同項(xiàng)目興趣用戶的好友，也可能會(huì)成為好友.

Ⅳ類元路徑：U-U-I-U，如果目標(biāo)用戶的好友與其他用戶具有相同項(xiàng)目興趣，那么目標(biāo)用戶與這些用戶也具有成為好友的可能性.

3.1.3 Advogato信任模型

本文認(rèn)為好友的產(chǎn)生和延續(xù)，其主要基礎(chǔ)為社交信任和興趣偏好，興趣偏好決定兩個(gè)用戶能否成為好友，而社交信任決定友情的持續(xù)性[26].

Advogato是經(jīng)典的信任模型，在檢測入侵、識(shí)別可信用戶方面尤為有效，在構(gòu)建節(jié)點(diǎn)信任網(wǎng)絡(luò)方面也有較好的優(yōu)勢，因此本文基于Advogato信任模型研究這四類元路徑所構(gòu)建的信任網(wǎng)絡(luò)[27，28].

構(gòu)建Advogato信任模型需要用到3個(gè)定義.

信任容量(Trust Capacity)，節(jié)點(diǎn)擴(kuò)展其他節(jié)點(diǎn)信任網(wǎng)絡(luò)或構(gòu)建自身信任網(wǎng)絡(luò)的能力.

信任流量(Trust Flow)，當(dāng)前節(jié)點(diǎn)根據(jù)自身對后續(xù)節(jié)點(diǎn)的信任程度，而分配到信任邊上的權(quán)重內(nèi)容.信任流量越多，分配給后續(xù)節(jié)點(diǎn)的信任容量越大，后續(xù)節(jié)點(diǎn)擴(kuò)展信任網(wǎng)絡(luò)的能力也就越強(qiáng).

源節(jié)點(diǎn)，也稱為Seed節(jié)點(diǎn)，擁有最大的信任容量，用來作為整個(gè)信任網(wǎng)絡(luò)的根節(jié)點(diǎn)，即授權(quán)中心.整個(gè)Advogato信任網(wǎng)絡(luò)構(gòu)建在源節(jié)點(diǎn)之上.

Advogato信任模型的構(gòu)建可分為3個(gè)步驟.

第1步.確定當(dāng)前節(jié)點(diǎn)，然后使用廣度優(yōu)先搜索算法搜索后續(xù)節(jié)點(diǎn)，并根據(jù)公式(1)為其分配信任容量.

(1)

其中，Capsuc代表后續(xù)節(jié)點(diǎn)的信任容量，Capcur代表當(dāng)前節(jié)點(diǎn)的信任容量，(out-degree)cur為當(dāng)前節(jié)點(diǎn)的出度.通過這一步，便得到了整個(gè)信任網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的信任容量.

第2步.對整個(gè)信任網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行處理，轉(zhuǎn)換為Advogato信任網(wǎng)絡(luò)(圖2所示).步驟為：每個(gè)節(jié)點(diǎn)被拆分為正向節(jié)點(diǎn)和負(fù)向節(jié)點(diǎn)；節(jié)點(diǎn)的信任容量減去信任閾值1并使其流向正向節(jié)點(diǎn)；減去的信任閾值注入稱為超級(jí)匯點(diǎn)的節(jié)點(diǎn)上(superlink).

第3步.使用文獻(xiàn)[29]的Fold-Fulkerson算法對新的信任網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)最大流增量路徑查找，以獲得源節(jié)點(diǎn)信任網(wǎng)絡(luò)中的可信節(jié)點(diǎn)集合.

基于Advogato信任模型，本文提出了目標(biāo)用戶本地信任網(wǎng)絡(luò)模型ULTNM(User Local Trust Network Model)，其與Advogato模型存在以下區(qū)別.

1)Advogato信任網(wǎng)絡(luò)只有一個(gè)或幾個(gè)源節(jié)點(diǎn)，而ULTNM模型則將每個(gè)用戶當(dāng)成一個(gè)源節(jié)點(diǎn)來計(jì)算，根據(jù)用戶與其他節(jié)點(diǎn)的信任關(guān)系來計(jì)算其他節(jié)點(diǎn)的信任容量，從而構(gòu)建自己的信任網(wǎng)絡(luò).

2)Advogato中每個(gè)節(jié)點(diǎn)的信任容量是全局信任值，而ULTNM信任模型則是為每個(gè)用戶構(gòu)建本地信任網(wǎng)絡(luò)，不同節(jié)點(diǎn)的信任容量對于每個(gè)目標(biāo)用戶來講，都是不一樣的.

圖2 信任網(wǎng)絡(luò)轉(zhuǎn)化為Advogato信任網(wǎng)絡(luò)的步驟Fig.2 Steps of transforming a trust network into the Advogato structure

3)在計(jì)算后續(xù)節(jié)點(diǎn)信任容量時(shí)，Advogato信任模型是根據(jù)當(dāng)前節(jié)點(diǎn)的出度計(jì)算，而ULTNM信任模型則是根據(jù)節(jié)點(diǎn)間的社交相似度和統(tǒng)計(jì)興趣相似度計(jì)算.

4)Advogato信任模型在構(gòu)建superlink節(jié)點(diǎn)時(shí)，為每個(gè)節(jié)點(diǎn)減去1個(gè)固定信任容量，而ULTNM信任模型在構(gòu)建superlink節(jié)點(diǎn)時(shí)，則是通過用戶的信任閾值來構(gòu)建，從而可確保信任網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的可信程度.具體區(qū)別見表1所示.

表1 ULTNM信任模型與Advogato信任模型的區(qū)別Table 1 Differences between ULTNM and Advogato trust model

3.2 ULTNM信任模型的形式化

定義 1.信任網(wǎng)絡(luò)G=(U,I,E,W)代表一個(gè)以信任為基礎(chǔ)的面向好友推薦的社交網(wǎng)絡(luò).其中，U代表用戶節(jié)點(diǎn)集，每個(gè)節(jié)點(diǎn)代表網(wǎng)絡(luò)中的一個(gè)用戶.I代表節(jié)點(diǎn)集，每個(gè)節(jié)點(diǎn)代表網(wǎng)絡(luò)中的一個(gè)項(xiàng)目.E為信任網(wǎng)絡(luò)中的邊集，E∈(U×U∪U×I∪I×I)，每條邊代表所連接兩個(gè)節(jié)點(diǎn)間的關(guān)系.W為信任網(wǎng)絡(luò)中連接邊的權(quán)重集合.

定義 2.節(jié)點(diǎn)k的本地信任網(wǎng)絡(luò)Gk=(Uk,Ik,Ek,Wk).對于一個(gè)節(jié)點(diǎn)k，以k為源節(jié)點(diǎn)派生出來的信任網(wǎng)絡(luò)Gk=(Uk,Ik,Ek,Wk)為信任網(wǎng)絡(luò)G的一個(gè)子圖，稱為節(jié)點(diǎn)k的本地信任網(wǎng)絡(luò)Gk=(Uk,Ik,Ek,Wk).其中Uk∈U,為節(jié)點(diǎn)k根據(jù)Ⅰ類元路徑可到達(dá)的有限路徑內(nèi)的可信用戶節(jié)點(diǎn)集.Ik∈I,為節(jié)點(diǎn)k通過Ⅱ類元路徑、Ⅲ類元路徑和Ⅳ類元路徑可達(dá)的項(xiàng)目.Eu?E，為節(jié)點(diǎn)k本地信任網(wǎng)絡(luò)內(nèi)的邊集合.Wu?W，為節(jié)點(diǎn)k本地信任網(wǎng)絡(luò)所有邊上的權(quán)重集合.

定義 3.m跳朋友.在節(jié)點(diǎn)k的本地信任網(wǎng)絡(luò)Gk=(Uk,Ik,Ek,Wk)中，如果存在一條路徑P=(,vi∈(Uk∪Ik),vm∈Uk)使得k可以通過m-1個(gè)節(jié)點(diǎn)到達(dá)vm，那么我們vm稱為k的m跳朋友.當(dāng)m=1時(shí)，稱vm為k的1跳朋友,也稱為直接鄰居.

定義 4.信任容量Capk.節(jié)點(diǎn)k構(gòu)建本地信任網(wǎng)絡(luò)的能力，稱為信任容量Capk.

定義 5.信任強(qiáng)度F.對于給定的節(jié)點(diǎn)k和它的1跳朋友vp，稱k對vp的信任流量為k到vp的信任強(qiáng)度，用Fk,p表示.

3.3 目標(biāo)節(jié)點(diǎn)的本地信任網(wǎng)絡(luò)構(gòu)建

對于不同的用戶來講，不同的社交關(guān)系可信程度不同，比如有些用戶認(rèn)為“遠(yuǎn)親不如近鄰”，而有些用戶則認(rèn)為“打虎親兄弟，上陣父子兵”.在社交網(wǎng)絡(luò)中，我們常常難以對這些關(guān)系進(jìn)行提取.因此，我們需要對用戶的社交網(wǎng)絡(luò)進(jìn)行重構(gòu)，對其中的用戶進(jìn)行信任度區(qū)分.本小節(jié)將根據(jù)前述的4類元路徑來構(gòu)建用戶的本地信任網(wǎng)絡(luò).

3.3.1 基于Ⅰ類元路徑的本地信任網(wǎng)絡(luò)構(gòu)建

為了方便處理，在構(gòu)建信任網(wǎng)絡(luò)時(shí)，為每個(gè)源節(jié)點(diǎn)統(tǒng)一分配信任容量為1.節(jié)點(diǎn)間的信任強(qiáng)度按照公式(2)進(jìn)行計(jì)算.

(2)

其中，Wi,j代表用戶i和用戶j的信任強(qiáng)度，SocSimi,j為用戶i和用戶j的社交相似度，StaSimi,j為用用戶i和用戶j的統(tǒng)計(jì)興趣相似度.當(dāng)StaSimi,j為0時(shí)，我們則使用社交相似度SocSimi,j來表達(dá)用戶i和用戶j之間的信任強(qiáng)度，以應(yīng)對冷啟動(dòng)用戶的數(shù)據(jù)稀疏問題.而如果SocSimi,j為0時(shí)，我們則使用統(tǒng)計(jì)興趣相似度StaSimi,j來表達(dá)用戶i和用戶j之間的信任強(qiáng)度.社交相似度SocSimi,j的計(jì)算采用公式(3)計(jì)算，其中的社交圈子重合度JaSimi,j采用公式(4)計(jì)算，社交親密度Intimi,j采用公式(5)計(jì)算.

SocSimi,j=log2(JaSimi,j+Intimi,j)

(3)

(4)

(5)

JaSimi,j為用戶i和用戶j的社交圈子重合度，采用Jaccard相關(guān)性公式，即公式(4)進(jìn)行計(jì)算，Soci、Socj別代表用戶i和用戶j的社交關(guān)系圈子節(jié)點(diǎn)集，也包括節(jié)點(diǎn)自身.Intimi,j表示用戶i和用戶j的親密度，采用公式(5)計(jì)算.在公式(5)中，Interi,j表示用戶i和用戶j的互動(dòng)次數(shù)，avg(Interall)表示整個(gè)社交網(wǎng)絡(luò)所有節(jié)點(diǎn)的平均互動(dòng)次數(shù).通過使用avg(Interall)可以對公式(3)進(jìn)行平衡，以防止某一對節(jié)點(diǎn)互動(dòng)次數(shù)過多，而成為奇異點(diǎn)的情況，從而克服惡意用戶通過提高交互次數(shù)來增加自身影響的情況.

在計(jì)算統(tǒng)計(jì)興趣相似度StaSim時(shí)，我們考慮兩個(gè)因素，一個(gè)是用戶間共同項(xiàng)目選擇的數(shù)量，一個(gè)是對于項(xiàng)目的評(píng)價(jià)情況.已有的研究文獻(xiàn)在計(jì)算用戶的興趣相似度時(shí)，通常采用Pearson公式(見公式(6))進(jìn)行計(jì)算，但忽略了用戶的共同項(xiàng)目數(shù)量信息.比如用戶A和B恰好只評(píng)價(jià)了一個(gè)共同項(xiàng)目，但評(píng)分一致，則根據(jù)Pearson公式計(jì)算，他們的興趣相似度為1，這樣不能客觀反映用戶之間的興趣相似度.因此，我們對Pearson公式進(jìn)行修正，將用戶的興趣分為統(tǒng)計(jì)興趣相似度StaSim和基礎(chǔ)興趣相似度BasSim.采用公式(6)計(jì)算基礎(chǔ)興趣相似度BasSim，而采用公式(8)進(jìn)行計(jì)算StaSim.

(6)

(7)

(8)

通過使用公式(2)，我們計(jì)算得到了節(jié)點(diǎn)i,j之間的信任強(qiáng)度Wi,j.而后，我們就可以對本地信任網(wǎng)絡(luò)中后續(xù)節(jié)點(diǎn)的信任容量進(jìn)行計(jì)算，采用公式(9)進(jìn)行.

Capj=Capi×Wi,j

(9)

其中，Capi為當(dāng)前節(jié)點(diǎn)i的信任容量，j代表它的后續(xù)節(jié)點(diǎn).如果i為目標(biāo)節(jié)點(diǎn)，則它的信任容量為1.如果從目標(biāo)節(jié)點(diǎn)i到達(dá)后續(xù)節(jié)點(diǎn)j的存在多條路徑，那么我們則使用文獻(xiàn)[29]Ford Fulkerson算法的思想，來計(jì)算節(jié)點(diǎn)j的信任容量.

假定目標(biāo)節(jié)點(diǎn)U基于Ⅰ類元路徑的本地信任網(wǎng)絡(luò)如圖3所示，根據(jù)本文的算法，節(jié)點(diǎn)U的信任容量為1，通過公式(2)計(jì)算得到節(jié)點(diǎn)U與節(jié)點(diǎn)A之間的信任強(qiáng)度為0.72，那么節(jié)點(diǎn)A的信任容量即為CapA=1×0.72=0.72.通過同樣的方式，我們可以計(jì)算得到節(jié)點(diǎn)B, C, D的信任容量.對于與目標(biāo)節(jié)點(diǎn)A距離為2跳的朋友節(jié)點(diǎn)也采用同樣的方式進(jìn)行計(jì)算，從而得到節(jié)點(diǎn)E和F的信任容量.對于節(jié)點(diǎn)G的信任容量計(jì)算，存在兩條傳播路徑PathUBG和PathUCG，因此前述方法，我們選擇一條信任流量最大的傳播路徑.根據(jù)PathUBG路徑的計(jì)算結(jié)果，節(jié)點(diǎn)G的信任容量為0.577，而根據(jù)PathUCG路徑的計(jì)算結(jié)果，節(jié)點(diǎn)G的信任容量為0.774，因此，G的最終信任容量為0.774.同理可得到節(jié)點(diǎn)D和節(jié)點(diǎn)H的信任容量.根據(jù)前面提到的三度影響力理論[25]，我們將節(jié)點(diǎn)基于Ⅰ類元路徑的的本地信任網(wǎng)絡(luò)構(gòu)建深度設(shè)為3,即目標(biāo)節(jié)點(diǎn)的朋友不能超過3跳關(guān)系.

圖3 信任流量傳遞中的路徑選擇Fig.3 Path choosing while transiting trust flow

3.3.2 目標(biāo)節(jié)點(diǎn)的本地信任網(wǎng)絡(luò)擴(kuò)展

上節(jié)計(jì)算了用戶節(jié)點(diǎn)間的信任強(qiáng)度，即Ⅰ類元路徑的情況，接下來我們對其他3類元路徑進(jìn)行分析.

1)Ⅱ類元路徑(U-I-U)的信任強(qiáng)度計(jì)算

對于Ⅱ類元路徑(U-I-U)實(shí)例的兩個(gè)用戶節(jié)點(diǎn)，我們使用公式(10)來計(jì)算他們之間的信任強(qiáng)度.

Wi,j=StaSimi,j

(10)

我們假定節(jié)點(diǎn)i和節(jié)點(diǎn)j之間沒有社交相似度SocSimi,j(同時(shí)存在有社交相似度的話，則該兩個(gè)節(jié)點(diǎn)也屬于Ⅰ類元路徑，這涉及到多路徑實(shí)例的情況，后面會(huì)進(jìn)一步分析)，因此我們使用統(tǒng)計(jì)興趣相似度StaSimi,j來表達(dá)節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的信任強(qiáng)度，統(tǒng)計(jì)興趣相似度StaSimi,j仍然使用公式8進(jìn)行計(jì)算.

2)Ⅲ類元路徑(U-I-U-U)的信任強(qiáng)度計(jì)算

對于Ⅲ類元路徑，實(shí)際上可將它轉(zhuǎn)換為Ⅱ類元路徑信任強(qiáng)度計(jì)算及其后續(xù)用戶節(jié)點(diǎn)的信任強(qiáng)度計(jì)算.因此，對于一條實(shí)例路徑Path(uk-il-up-uq)，節(jié)點(diǎn)k對節(jié)點(diǎn)q的信任強(qiáng)度Wk,q可由公式(11)計(jì)算.

(11)

3)Ⅳ類元路徑(U-U-I-U)的信任強(qiáng)度計(jì)算

Ⅳ類元路徑的信任計(jì)強(qiáng)度算與Ⅲ類元路徑的類似，可以將它轉(zhuǎn)換為當(dāng)前節(jié)點(diǎn)和后續(xù)Ⅱ類元路徑(U-I-U)的信任強(qiáng)度計(jì)算.對于一條實(shí)例路徑Path(uk-up-il-uq)，節(jié)點(diǎn)k對節(jié)點(diǎn)q的信任強(qiáng)度Wk,q可由公式(12)計(jì)算.

(12)

公式(12)與公式(11)的不同在于，它先計(jì)算節(jié)點(diǎn)k對節(jié)點(diǎn)p的信任強(qiáng)度Wk,p，然后再計(jì)算節(jié)點(diǎn)p對節(jié)點(diǎn)q的信任強(qiáng)度Wp,q，最后產(chǎn)生元路徑實(shí)例節(jié)點(diǎn)k對節(jié)點(diǎn)q的信任強(qiáng)度Wk,q.對于歸屬于多條實(shí)例路徑的節(jié)點(diǎn)，本文仍使用前述方法進(jìn)行信任流量傳播.如圖4所示.

在圖4中，方形節(jié)點(diǎn)K為項(xiàng)目節(jié)點(diǎn)，圓形節(jié)點(diǎn)U、J、L、M、N、O為用戶節(jié)點(diǎn).節(jié)點(diǎn)U到節(jié)點(diǎn)N之間存在3條元路徑實(shí)例，分別為PathUJN、PathUKN、PathUJKN，分別對應(yīng)I類元路徑、Ⅱ類元路徑和Ⅳ類元路徑.其中，StaSimJ,N=0.92、StaSimU,N=0.78、StaSimU,L=0.83，因此，根據(jù)前述的計(jì)算公式可以得到基于PathUJN的WU,N=0.577，基于PathUKN的WU,N=0.78，基于PathUJKN的WU,N=0.8556，因此，節(jié)點(diǎn)E的最終信任容量為0.8556.節(jié)點(diǎn)U到節(jié)點(diǎn)O之間存在2條元路徑實(shí)例，分別為PathULO、PathUKLO，分別對應(yīng)Ⅰ類元路徑和Ⅲ類元路徑.同理可以計(jì)算得到O的最終信任容量為0.764.

圖4 多條元路徑實(shí)例下的信任容量計(jì)算Fig.4 Computation of trust capacity for multi meta-path instances

4 融合社交信任的多屬性元路徑好友推薦算法(ComULTNM)

在本節(jié)中，我們將使用算法1對目標(biāo)節(jié)點(diǎn)的本地信任網(wǎng)絡(luò)進(jìn)行轉(zhuǎn)換，并根據(jù)目標(biāo)節(jié)點(diǎn)的信任閾值對其本地信任網(wǎng)絡(luò)進(jìn)行搜索，然后返回目標(biāo)節(jié)點(diǎn)的候選好友列表.ComULTNM推薦方法的算法如下.

算法1.融合社交信任的多屬性元路徑好友推薦算法(ComULTNM)

輸入：目標(biāo)節(jié)點(diǎn)u，全局鄰接矩陣GUM，節(jié)點(diǎn)u的本地信任網(wǎng)絡(luò)鄰接矩陣LUM，LUM中所有節(jié)點(diǎn)的信任容量表capList,鄰接矩陣LUM的秩N，節(jié)點(diǎn)u的信任閾值Thu

輸出：目標(biāo)節(jié)點(diǎn)的有序候選好友列表Fru

1. i=0,Fru=0,n=N, th=Thu

2. for i in range(n):

3. for j in range(n):

4. ifCapi,j>Thu:

5.Capi,j=Capi,j-Thu

6. setSuperlink(LUM, LUM[i][j],u)

7. capList[i][j]=Capi,j

8. if not isRelated(GUM,u, LUM[i][j]):

9.Fru.append(LUM[i][j])

10. endif

11. endif

12. endfor

13. endfor

14.Fru.sort()

15. returnFru

其中，Capi,j為LUM中下標(biāo)為i,j的節(jié)點(diǎn)信任容量，偽代碼4-7行用來判斷當(dāng)前節(jié)點(diǎn)LUM[i][j]的信任容量Capi,j是否大于u的信任閾值Thu，如果大于，則調(diào)用方法setSuperlink(LUM,nodei,j,u)方法在LUM中為節(jié)點(diǎn)nodei,j,u建立關(guān)聯(lián)，并對Capi,j的信任容量進(jìn)行更新.

偽代碼8-10行用來判斷在全局鄰接矩陣GUM中，目標(biāo)節(jié)點(diǎn)u與LUM[i][J]是否存在連接，即是否為1跳朋友關(guān)系.如果不是1跳朋友關(guān)系，則說明當(dāng)前節(jié)點(diǎn)LUM[i][j]還不是u的朋友，因此將該節(jié)點(diǎn)添加到u的候選好友列表Fru中.否則u與LUM[i][j]已經(jīng)是朋友關(guān)系，則不作處理.

偽代碼14-15行用來對u的候選好友列表Fru進(jìn)行排序，并將列表返回.

圖5 采用算法1對目標(biāo)用戶的本地信任網(wǎng)絡(luò)重建和搜索Fig.5 Research and rebuild on local trust network of target user with algorithm 1

通過算法1，我們結(jié)合圖3和圖4對目標(biāo)節(jié)點(diǎn)u的本地信任網(wǎng)絡(luò)進(jìn)行搜索和重建(如圖5所示)，最終得到目標(biāo)節(jié)點(diǎn)的候選好友列表：N,G,O,H,E,F,M(這里設(shè)置Thu=0.1，限于篇幅，E, F, L, J, K, M, N, O節(jié)點(diǎn)沒有畫出).

5 實(shí)驗(yàn)與分析

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

目前用于好友推薦的公開實(shí)驗(yàn)數(shù)據(jù)集主要有：Gowalla數(shù)據(jù)集、Foursquare數(shù)據(jù)集、Epinions數(shù)據(jù)集等，也有不少研究者使用網(wǎng)絡(luò)爬蟲對新浪微博、Twitter等網(wǎng)站的數(shù)據(jù)進(jìn)行爬取，用于好友推薦實(shí)驗(yàn).其中，Gowalla數(shù)據(jù)集和Foursquare數(shù)據(jù)集主要用于基于地理位置的好友推薦，而使用網(wǎng)絡(luò)爬蟲從新浪微博或Twitter爬取數(shù)據(jù)，很難獲得用戶間的完整社交關(guān)系.因此，本文選取Epinions作為實(shí)驗(yàn)數(shù)據(jù)集.其統(tǒng)計(jì)信息如表2所示.

表2 Epinions數(shù)據(jù)集的統(tǒng)計(jì)信息Table 2 Statistics of the Epinions dataset

該數(shù)據(jù)集包含了139738個(gè)項(xiàng)目，664824條項(xiàng)目評(píng)分，項(xiàng)目評(píng)分區(qū)間為[1-5].還包含了49290個(gè)用戶和487181對朋友關(guān)系，數(shù)據(jù)集的朋友關(guān)系數(shù)據(jù)稀疏度為99.98%，屬于極度稀疏數(shù)據(jù).

在將本文的ULTNM信任模型應(yīng)用于Epinions數(shù)據(jù)集時(shí)，考慮到公式(5)中用戶間的互動(dòng)次數(shù)Interi,j在Epinions數(shù)據(jù)集中沒有直接對應(yīng)的數(shù)據(jù)，因此我們采用用戶共同訪問項(xiàng)目數(shù)量來作為替代，其他的參數(shù)都可在數(shù)據(jù)集中找到對應(yīng)的數(shù)據(jù)內(nèi)容或計(jì)算得出.在進(jìn)行實(shí)驗(yàn)時(shí)，將數(shù)據(jù)集的487181對朋友關(guān)系分成兩份，90%作為訓(xùn)練集，10%作為測試集，以檢測推薦方法的有效性.

5.2 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

本文選取推薦系統(tǒng)中常用的準(zhǔn)確率(precision)、召回率(recall)作為推薦方法實(shí)驗(yàn)效果的評(píng)價(jià)指標(biāo).具體計(jì)算方式如公式(13)、公式(14)所示.

(13)

(14)

其中，R(u)表示推薦給用戶u的候選好友集合，T(u)表示用戶u在測試集中真實(shí)的好友集合.準(zhǔn)確率是指推薦的候選好友列表中，真實(shí)為用戶好友的比例占推薦用戶總數(shù)的比例，反映的是推薦方法的精度.召回率是指推薦的候選好友列表中，真實(shí)為用戶好友的比例，占測試集中用戶真實(shí)好友數(shù)量的比例，反映的是推薦方法的覆蓋率.這兩個(gè)指標(biāo)數(shù)值越大，表明推薦方法的總體效果越好.

5.3 源節(jié)點(diǎn)信任閾值設(shè)置

本文提出的ComULTNM推薦方法所使用的實(shí)驗(yàn)參數(shù)大多可根據(jù)數(shù)據(jù)集內(nèi)容計(jì)算得到，只有源節(jié)點(diǎn)的信任閾值Thu需要設(shè)置.因此我們通過實(shí)驗(yàn)來驗(yàn)證源節(jié)點(diǎn)信任閾值Thu取值對推薦方法召回率的影響，來考察推薦方法的覆蓋率.本實(shí)驗(yàn)中，我們將Thu值設(shè)為[0, 1]，步長0.1.實(shí)驗(yàn)結(jié)果如表3所示.

表3 不同信任閾值下的召回率對比Table 3 Comparison of recall under different trust threshold

通過表3可以看出，隨著信任閾值Thu的不斷上升，在Thu為0.1時(shí)，ComULTNM推薦方法的召回率最高，而后則不斷下降，在Thu為1時(shí)達(dá)到最低，只有0.009.這是因?yàn)槟軌蜻M(jìn)入源節(jié)點(diǎn)可信社交網(wǎng)絡(luò)的用戶越來越少，當(dāng)信任閾值達(dá)到1時(shí)，意味著源節(jié)點(diǎn)基本只信任自己，因此很難為他推薦好友.因此我們在后續(xù)的實(shí)驗(yàn)中，都將信任閾值Thu設(shè)為0.1.

5.4 實(shí)驗(yàn)對比方法

為了驗(yàn)證本文提出的推薦方法，我們將使用以下方法進(jìn)行對比.

1)User-based CF，經(jīng)典的基于用戶興趣相似度的協(xié)同過濾推薦方法，根據(jù)用戶的興趣相似度來進(jìn)行候選好友推薦[30].

2)Praveen Model，文獻(xiàn)[31]提出的好友推薦方法，該文章將社交網(wǎng)絡(luò)按照拓?fù)浣Y(jié)構(gòu)進(jìn)行重建，并將好友推薦方法分為兩個(gè)階段，首先基于用戶之間的興趣偏好和共同好友進(jìn)行好友候選人篩選，然后再根據(jù)候選好友的影響力進(jìn)行排序，從而完成目標(biāo)用戶的好友推薦.

3)PAFR，文獻(xiàn)[32]提出的好友推薦方法，該文章基于協(xié)同分析和隱私保護(hù)云技術(shù)設(shè)計(jì)了一個(gè)好友推薦框架，該框架利用用戶之間共同鄰居的行為、興趣，來推測目標(biāo)用戶的交友興趣，并使用同態(tài)加密技術(shù)來保護(hù)用戶的隱私信息.

在和這三個(gè)推薦方法進(jìn)行實(shí)驗(yàn)對比時(shí)，我們將好友候選人的Top-N值，分別設(shè)為n=5，10，15，20，實(shí)驗(yàn)結(jié)果取100次執(zhí)行結(jié)果的平均值.

5.5 推薦效果對比

圖6(a)、圖6(b)分別展示了4個(gè)推薦方法在Epinions數(shù)據(jù)集上的準(zhǔn)確率和召回率.

圖6 4種推薦方法的推薦效果對比Fig.6 Comparison of the four recommendation methods

通過對圖6所示的實(shí)驗(yàn)結(jié)果進(jìn)行分析，可以得到以下結(jié)論.

1)隨著推薦候選好友Top-N數(shù)量的增加，這4個(gè)推薦方法的準(zhǔn)確率都有所下降，而召回率卻都逐漸上升.準(zhǔn)確率從高到低順序依次為：ComULTNM、Praveen Model、PAFR和User-based CF，召回率方面，推薦效果最好的方法依次為：ComULTNM、Praveen Model、PAFR和User-based CF.因此，本文提出的推薦方法總體效果最好，這說明我們提出的推薦方法是有效的.

2)在這4個(gè)推薦方法中，User-based CF的推薦效果最不理想，其原因可能是該推薦方法只考慮了用戶的興趣相似度，而忽略了重要的社交因素和信任因素在推薦方法中的作用.

3)對比Praveen Model和PAFR方法，Praveen Model的推薦效果比PAFR方法好.雖然這兩個(gè)推薦方法都考慮了目標(biāo)用戶的共同好友因素，但Praveen Model還將好友候選人的影響力因素引入，因此有更好的效果，這與現(xiàn)實(shí)生活中的情況一致，人們總是更愿意接受有影響力的朋友推薦的好友.

4)對比Praveen Model和PAFR方法，ComULTNM的推薦效果最優(yōu).雖然這兩個(gè)推薦方法也都考慮了目標(biāo)用戶的共同好友即社交圈子因素，但在計(jì)算興趣相似度時(shí)，ComULTNM不僅考慮了項(xiàng)目的興趣相似度，還進(jìn)一步考慮了基于共同選擇項(xiàng)目數(shù)量的統(tǒng)計(jì)興趣相似度.在此基礎(chǔ)上，ComULTNM方法還進(jìn)一步考慮了基于互動(dòng)次數(shù)和社交圈子相似度的親密度因素，因此取得了最佳的推薦效果.

5.6 抗托攻擊效果對比

托攻擊是惡意用戶通過模擬目標(biāo)用戶的項(xiàng)目評(píng)分，提高自身與目標(biāo)用戶興趣相似度，從而將具有欺騙性的項(xiàng)目推薦給目標(biāo)用戶，導(dǎo)致目標(biāo)用戶利益受損的常用攻擊手段.本節(jié)的實(shí)驗(yàn)通過模擬惡意用戶的托攻擊行為，來檢測這4種推薦方法在托攻擊下的表現(xiàn).本實(shí)驗(yàn)中，我們將Top-N的n值設(shè)為20，然后增加惡意用戶的比例.實(shí)驗(yàn)結(jié)果如圖7(a)、圖7(b)所示.

通過對圖7所示的實(shí)驗(yàn)結(jié)果進(jìn)行分析，可以得到以下結(jié)論.

1)隨著惡意用戶比例的增加，這4個(gè)推薦方法的準(zhǔn)確率和召回率都有所下降.在沒有惡意用戶出現(xiàn)的時(shí)候，推薦準(zhǔn)確率和召回率的實(shí)驗(yàn)效果從高到底排序?yàn)椋篊omULTNM、Praveen Model、PAFR和User-based CF.當(dāng)惡意用戶比例超過10%時(shí)，Praveen Model推薦方法受到了較大的影響，這時(shí)準(zhǔn)確率和召回率的實(shí)驗(yàn)效果從高到底排序?yàn)椋篊omULTNM、PAFR、Praveen Model和User-based CF.

圖7 4種推薦方法的抗托攻擊效果對比Fig.7 Comparison of the four recommendation methods under Shilling attacks

2)隨著惡意用戶比例的增加，User-based CF受影響最大，其推薦精度下降最快.其原因是托攻擊本身就是針對該方法設(shè)計(jì)，因此該方法受影響最大.

3)Praveen Model受惡意用戶增加的影響僅次于User-based CF推薦方法，在惡意用戶比例為0時(shí)，它的推薦效果要優(yōu)于PAFR方法，但當(dāng)惡意用戶比例增加到10%時(shí)，它的推薦精度下降較迅速，以至于被PAFR推薦方法超越.這可能是該方法也是基于User-based CF的思想設(shè)計(jì)，所以當(dāng)惡意用戶增加過多時(shí)，推薦精度也受到了較大的影響.

4)相比較而言，當(dāng)惡意用戶逐漸增加時(shí)，本文的ComULTNM推薦方法一直保持效果最好，但PAFR推薦方法卻最穩(wěn)定.雖然ComULTNM方法也考慮了用戶的興趣偏好，也受到惡意用戶比例增加的影響，但由于使用了統(tǒng)計(jì)興趣偏好、社交相似度這些因素進(jìn)行糾偏，所以仍然保持了最好的推薦效果.而PAFR推薦方法由于使用了同態(tài)加密技術(shù)和隱私保護(hù)云技術(shù)，可以隱藏用戶的身份信息，從而導(dǎo)致惡意節(jié)點(diǎn)模仿目標(biāo)節(jié)點(diǎn)的興趣相似度存在一定的困難，因此穩(wěn)定性最好.

5.7 運(yùn)行效率對比

本實(shí)驗(yàn)對4個(gè)推薦方法的運(yùn)行效率進(jìn)行對比.在本實(shí)驗(yàn)中，我們將Top-N的n值設(shè)為20，隨機(jī)選10個(gè)目標(biāo)用戶進(jìn)行好友推薦，將每個(gè)推薦方法運(yùn)行100次，然后取平均運(yùn)行時(shí)間.為了方便對比，我們將User-based CF方法的運(yùn)行時(shí)間作為基礎(chǔ)，用無量綱值1來表示，對比其他推薦方法的運(yùn)行時(shí)間.實(shí)驗(yàn)結(jié)果如圖8所示.

通過對圖8所示的實(shí)驗(yàn)結(jié)果分析，可以得到以下結(jié)論.

1)這4種推薦方法的運(yùn)行效率排序?yàn)椋篊omULTNM、Praveen Model、User-based CF和PAFR.即本文提出的ComULTNM運(yùn)行效果推薦方法運(yùn)行所需時(shí)間最少，而PAFR推薦方法耗時(shí)最多.

2)ComULTNM、Praveen Model及User-based CF三個(gè)方法相比，由于User-based CF在為目標(biāo)用戶進(jìn)行候選好友推薦時(shí)，需要計(jì)算全局鄰接矩陣中每個(gè)用戶與目標(biāo)用戶的興趣相似度，而Praveen Model方法在計(jì)算用戶興趣相似度的基礎(chǔ)上，還需要計(jì)算全局鄰接矩陣中每個(gè)用戶與目標(biāo)用戶的共同好友數(shù)量，然后根據(jù)候選好友的影響力排序，因此它的時(shí)間消耗比User-based CF略高.對于ComULTNM方法，由于不需要進(jìn)行全局鄰接矩陣運(yùn)算，但在計(jì)算過程中，需要構(gòu)建目標(biāo)用戶的本地信任網(wǎng)絡(luò)，且需要計(jì)算社交親密度、統(tǒng)計(jì)興趣相似度等內(nèi)容，但因?yàn)樗捎玫脑窂介L度不大于3，因此減少了許多的計(jì)算量，其計(jì)算耗時(shí)相對比User-based CF略少些.

圖8 4種推薦方法的運(yùn)行效率對比Fig.8 Time cost of the four recommendation methods

3)對于PAFR方法，因?yàn)槠洳粌H需要計(jì)算用戶之間的共同鄰居行為相似度，還需要計(jì)算他們之間的興趣相似度，在計(jì)算這些數(shù)據(jù)時(shí)，還需要使用同態(tài)加密技術(shù)和隱私保護(hù)云技術(shù)，因此耗時(shí)量最大，要遠(yuǎn)高于其他3個(gè)對比方法.

6 總 結(jié)

社交網(wǎng)絡(luò)的日益普及，促進(jìn)了在線社交的發(fā)展，好友推薦成為了目前大多數(shù)社交應(yīng)用的主流服務(wù)，也成了推薦系統(tǒng)的研究熱點(diǎn).有效的好友推薦，能幫用戶快速擴(kuò)大自己的社交范圍，得到更多的社會(huì)資源和信息.然而，現(xiàn)有的好友推薦方法，大多基于用戶偏好或行為軌跡進(jìn)行好友推薦，未考慮在線社交的異構(gòu)網(wǎng)絡(luò)特征，且容易受到托攻擊的影響，導(dǎo)致推薦精度降低.從這一研究角度出發(fā)，本文分析了在線社交的異構(gòu)網(wǎng)絡(luò)特征，使用元路徑理論對好友推薦的異構(gòu)網(wǎng)絡(luò)進(jìn)行抽象和形式化，提出了ULTNM(User Local Trust Network Model)信任模型.該信任模型綜合考慮元路徑上節(jié)點(diǎn)的社交相似度和統(tǒng)計(jì)興趣偏好相似度等多種屬性特征，構(gòu)建了目標(biāo)用戶的本地信任網(wǎng)絡(luò)，并通過Ford Fulkerson算法對信任網(wǎng)絡(luò)進(jìn)行搜索和排序，進(jìn)行目標(biāo)用戶的候選好友推薦.基于真實(shí)數(shù)據(jù)集的對比實(shí)驗(yàn)表明，該推薦方法有更好的推薦準(zhǔn)確率和召回率，能更好的抵御惡意用戶的托攻擊行為，且運(yùn)行效率具有一定的優(yōu)勢.

下一步工作將考慮基于時(shí)間序列的用戶興趣偏好對好友推薦的影響，并進(jìn)一步考慮小世界理論在好友推薦中的應(yīng)用.