一種改進(jìn)的鏈路預(yù)測(cè)好友推薦方法

付　霞，杜亞軍*，吳　越，孟慶瑞

(1.西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，四川 成都　610039；2.西藏飛躍智能科技有限公司，西藏 拉薩　850000)

?

一種改進(jìn)的鏈路預(yù)測(cè)好友推薦方法

付霞1，杜亞軍1*，吳越1，孟慶瑞2

(1.西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，四川 成都610039；2.西藏飛躍智能科技有限公司，西藏 拉薩850000)

摘要：為從海量用戶中篩選出與目標(biāo)用戶相似度最高的用戶作為好友進(jìn)行精確推薦，提出一種鏈路預(yù)測(cè)好友推薦算法。通過用戶之間的鏈路關(guān)系推薦出與目標(biāo)用戶相似性最高的Top-N個(gè)用戶；分別計(jì)算目標(biāo)用戶與這Top-N個(gè)用戶之間的標(biāo)簽相似性以及共同好友相似性，并對(duì)其分別賦予相應(yīng)的權(quán)值；根據(jù)權(quán)值計(jì)算目標(biāo)用戶與其他用戶之間的綜合相似度；對(duì)綜合相似度進(jìn)行排序，為目標(biāo)用戶推薦出與其相似度最高的用戶。以騰訊微博用戶推薦為例進(jìn)行實(shí)驗(yàn)，結(jié)果表明，該推薦算法的精確率比單一鏈路預(yù)測(cè)算法高8%。該算法能在一定程度上提高好友推薦的準(zhǔn)確率。

關(guān)鍵詞：在線社交網(wǎng)絡(luò); 鏈路預(yù)測(cè)；朋友推薦; 相似度; 標(biāo)簽

1研究現(xiàn)狀

隨著Internet技術(shù)的快速發(fā)展，以微博為代表的在線社交網(wǎng)站日益成為人們?nèi)粘＝涣鳌蕵贰⑼ㄐ诺闹匾脚_(tái)，其用戶規(guī)模也與日俱增。例如國外的Facebook、Twitter，以及國內(nèi)的豆瓣、新浪微博、人人網(wǎng)等都擁有數(shù)億用戶，并將持續(xù)增加。在這些在線社交網(wǎng)站上，用戶不僅把現(xiàn)實(shí)生活中的人際關(guān)系搬到網(wǎng)絡(luò)上，而且根據(jù)個(gè)人的興趣愛好建立了與線下無關(guān)的單純的線上朋友關(guān)系。在線社交網(wǎng)站和現(xiàn)實(shí)生活類似，在沒有好的推薦方法下是很難找到好朋友的[1]；因此，在龐大的社交網(wǎng)站中，用戶選擇添加哪些用戶作為自己的好友成為了一個(gè)難題。社交網(wǎng)站中的好友推薦系統(tǒng)就是針對(duì)這一問題而提出的。

針對(duì)好友推薦問題，國內(nèi)外研究者提出了許多相關(guān)算法[1-17]，主要有基于鏈路預(yù)測(cè)算法和協(xié)同過濾算法等。

鏈路預(yù)測(cè)[2]方法的基本思想是針對(duì)2個(gè)未建立鏈接的節(jié)點(diǎn)，若它們的鄰節(jié)點(diǎn)的集合有大量重合部分，這2個(gè)節(jié)點(diǎn)在未來某時(shí)刻建立鏈接的可能性就很大。D.Liben-Nowell等[3]提出了一種最早的社交網(wǎng)絡(luò)鏈路預(yù)測(cè)模型，其實(shí)驗(yàn)證明了節(jié)點(diǎn)間的未來交互是可以通過監(jiān)視鄰居節(jié)點(diǎn)來提取的。傅穎斌等[2]提出了基于鏈路預(yù)測(cè)的微博用戶關(guān)系分析方法。P.Alexis等[4]通過一種快速的鏈路預(yù)測(cè)方法來推薦好友，該算法能很好地為目標(biāo)用戶推薦出線下認(rèn)識(shí)的好友以及關(guān)系較強(qiáng)的好友，提高了推薦算法的精確度。Michael等[1]提出一種“你可能認(rèn)識(shí)的人”的算法，該算法可以克服社交網(wǎng)絡(luò)圖過于龐大的困難，保持圖的實(shí)時(shí)更新，同時(shí)可以利用該圖產(chǎn)生好友推薦，對(duì)大數(shù)據(jù)量的圖結(jié)構(gòu)有了高效率的遍歷和搜索。FoF(friend-of-friend)算法[5-8]的思路是利用朋友關(guān)系的傳遞性為目標(biāo)用戶推薦好友。FoF方法認(rèn)為在一個(gè)龐大的社交網(wǎng)絡(luò)上，若2個(gè)獨(dú)立的節(jié)點(diǎn)之間存在越多的共同節(jié)點(diǎn)，則這2個(gè)節(jié)點(diǎn)在將來就有更高可能性建立鏈接。

協(xié)同過濾算法在推薦系統(tǒng)中得到了廣泛的應(yīng)用。Typestry是最早提出來的一個(gè)基于協(xié)同過濾算法的推薦系統(tǒng),它要求目標(biāo)用戶需要明確指出與自己興趣愛好相似的其他用戶[9]。針對(duì)用戶規(guī)模的增加，文獻(xiàn)[10-11]加入用戶曾經(jīng)使用過的項(xiàng)目屬性，提出基于用戶聚類的協(xié)同過濾推薦算法，該算法在一定程度上縮小了近鄰用戶搜索范圍；但由于缺少對(duì)目標(biāo)用戶的興趣分析，聚類會(huì)丟失部分用戶數(shù)據(jù)。文獻(xiàn)[12]充分利用標(biāo)簽信息，采用標(biāo)簽共生分布來計(jì)算標(biāo)簽相似度。張楊[13]在經(jīng)典的推薦系統(tǒng)的基礎(chǔ)之上，給出一個(gè)基于標(biāo)簽的雙向協(xié)同過濾模型DCMu,通過社會(huì)化標(biāo)簽，將用戶的已評(píng)分項(xiàng)目分為正向(喜歡)和負(fù)向(厭惡)2大類,并在用戶初始模型的基礎(chǔ)上計(jì)算正反用戶之間的相似關(guān)聯(lián)性。胡文江等[14]采用好友之間的關(guān)系推薦和喜好標(biāo)簽的相似度推薦相結(jié)合的方法,提出了一種改進(jìn)的推薦算法。張怡文等[15]提出一種基于共同用戶和相似標(biāo)簽的協(xié)同過濾算法，抽取共同關(guān)注用戶作為共同項(xiàng)目，加入體現(xiàn)用戶興趣的自定義標(biāo)簽數(shù)據(jù)。這類基于標(biāo)簽或共同好友數(shù)的方法雖然能有效地得到用戶的興趣等信息；但由于目前的語義相似度計(jì)算存在較大誤差，如果僅僅依據(jù)標(biāo)簽等屬性指標(biāo)計(jì)算用戶之間的相似度，會(huì)導(dǎo)致推薦結(jié)果誤差較大。

雖然基于協(xié)同過濾的推薦系統(tǒng)在現(xiàn)實(shí)中得到了廣泛的應(yīng)用，但協(xié)同過濾推薦技術(shù)仍存在精確度低、數(shù)據(jù)稀疏[16]、冷啟動(dòng)[17]和可擴(kuò)展[18]等問題。

為解決鏈路預(yù)測(cè)不能很好地描述用戶本身的興趣和特征的缺點(diǎn)以及協(xié)同過濾算法的數(shù)據(jù)稀疏問題，提高好友推薦準(zhǔn)確率，本文提出了一種結(jié)合鏈路預(yù)測(cè)和標(biāo)簽等屬性的改進(jìn)的鏈路預(yù)測(cè)好友推薦算法。

2相關(guān)工作

2.1社交網(wǎng)絡(luò)關(guān)系圖

本文要實(shí)現(xiàn)的朋友推薦算法采用騰訊微博的數(shù)據(jù)作為數(shù)據(jù)集。通過調(diào)用騰訊微博開放平臺(tái)所提供的API[19]獲取數(shù)據(jù)，通過朋友之間的鏈接關(guān)系構(gòu)建與種子賬號(hào)相關(guān)的社交網(wǎng)絡(luò)關(guān)系。在騰訊微博中，每個(gè)賬號(hào)都有“偶像”與“聽眾”2種關(guān)注與被關(guān)注的形式，假設(shè)有賬戶A、B，他們有如下幾種關(guān)系：1)A是B的偶像，即B是A的聽眾；2)A是B的聽眾，即B是A的偶像；3)A與B相互收聽；4)A與B沒有直接的收聽關(guān)系。用戶與用戶之間在社交網(wǎng)絡(luò)圖中用有向圖來表示用戶間的收聽關(guān)系。

社交網(wǎng)絡(luò)關(guān)系圖定義為G=(V,E)表示所構(gòu)建的社交網(wǎng)絡(luò)關(guān)系圖，其中V表示社交網(wǎng)絡(luò)關(guān)系圖中的所有朋友節(jié)點(diǎn)的集合，E表示所有邊的集合。e=(vi,vj)表示從vi指向vj的有向邊，vi的偶像是vj，其中e∈E，表示節(jié)點(diǎn)間的收聽關(guān)系，vi,vj∈V，表示節(jié)點(diǎn)集中的2個(gè)朋友節(jié)點(diǎn)。

2.2基于鏈路預(yù)測(cè)的朋友推薦算法

用sim1(vx,vy)來表示社交網(wǎng)絡(luò)圖中的vx、vy2個(gè)節(jié)點(diǎn)之間的相似度，其計(jì)算公式[4]為

(1)

2.3基于標(biāo)簽和共同好友數(shù)的推薦算法

在本文中，對(duì)標(biāo)簽和共同好友數(shù)相似性均采用杰卡德相似系數(shù)計(jì)算。杰卡德相似系數(shù)是用于比較有限樣本集合的相似性和差異性的統(tǒng)計(jì)量[20]。2個(gè)集合A和B交集元素的個(gè)數(shù)在A、B并集中所占的比例，稱為這2個(gè)集合的杰卡德系數(shù)，用符號(hào)J(A,B)表示。其公式為

(2)

如果集合A、B均為空集，定義J(A,B)=1。顯然0≤J(A,B)≤ 1。J值越大,2個(gè)樣本的相似度越大。

3改進(jìn)的鏈路預(yù)測(cè)好友推薦算法

本文首先根據(jù)用戶之間的鏈路關(guān)系，通過單一的鏈路預(yù)測(cè)算法推薦出與目標(biāo)用戶相似性最高的Top-N個(gè)用戶；接著通過標(biāo)簽相似算法和共同好友算法分別計(jì)算目標(biāo)用戶與這Top-N個(gè)用戶之間的標(biāo)簽相似性和共同好友相似性，并為它們賦予相應(yīng)的權(quán)值，從而計(jì)算目標(biāo)用戶與其他用戶之間的綜合相似度；最后對(duì)綜合相似度進(jìn)行排序，為目標(biāo)用戶推薦出與其相似度最高的用戶。

3.1基于鏈路預(yù)測(cè)算法的偽代碼

根據(jù)式(1)，將基于鏈路預(yù)測(cè)的朋友推薦算法的偽代碼表示如下。

input:局部社交網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，其中隱含了鏈接關(guān)系，vij∈V表示第i層的j節(jié)點(diǎn)；局部社交網(wǎng)絡(luò)中朋友鏈接的最大長(zhǎng)度l；局部社交網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)n。

output：局部社交網(wǎng)絡(luò)中各節(jié)點(diǎn)與種子節(jié)點(diǎn)之間的相似度集合。

Begin

Step1：在種子用戶及其直接朋友的基礎(chǔ)上構(gòu)建朋友鏈長(zhǎng)最多為2的局部社交網(wǎng)絡(luò)SN2

fork=1ton//計(jì)算鏈路長(zhǎng)度為2的節(jié)點(diǎn)與種子節(jié)點(diǎn)的相似度

end for

Step2：在SN2的基礎(chǔ)上構(gòu)建朋友鏈長(zhǎng)最多為3的局部社交網(wǎng)絡(luò)SN3

fork=1ton//計(jì)算鏈路長(zhǎng)度為3的節(jié)點(diǎn)與種子節(jié)點(diǎn)的相似度sim1

end for

End

3.2基于標(biāo)簽的好友推薦算法

3.2.1標(biāo)簽推薦算法的思想

標(biāo)簽所表示的是用戶的興趣愛好。將這些標(biāo)簽作為關(guān)鍵字，并以此來組成用戶標(biāo)簽的偏好向量。在做推薦的時(shí)候，將目標(biāo)用戶的標(biāo)簽和其他用戶的標(biāo)簽進(jìn)行相似度的比較，將相似度高的用戶推薦給目標(biāo)用戶。

在騰訊微博中，每個(gè)用戶都可以為自己添加不同的標(biāo)簽來表示自己的興趣和愛好。將用戶的標(biāo)簽用一個(gè)列表表示，每個(gè)列表對(duì)應(yīng)一個(gè)用戶及其標(biāo)簽。用戶A的標(biāo)簽列表可以表示為UAT={〈A,tag1〉,〈A,tag2〉,〈A,tag3〉,…，〈A,tagn〉},用戶B的標(biāo)簽列表可以表示為UBT={〈B,tag1〉,〈B,tag2〉,〈B,tag3〉,…，〈B,tagn〉}。如果要計(jì)算用戶A、B之間的相似度，只需要通過計(jì)算他們標(biāo)簽之間的相似度來間接計(jì)算他們之間的相似度。如果用戶間的標(biāo)簽相似度越高，那么在社交網(wǎng)絡(luò)中他們就越有可能成為好友，這里稱為興趣最相似的好友。其公式為：

(3)

其中t1，t2分別為2個(gè)用戶的標(biāo)簽，如果2個(gè)標(biāo)簽相同，值為1，否則為0。根據(jù)式(2)，用戶間的標(biāo)簽相似性計(jì)算公式為

(4)

3.2.2標(biāo)簽推薦算法偽代碼

Input:所有的朋友節(jié)點(diǎn)n的標(biāo)簽列表,種子節(jié)點(diǎn)A的標(biāo)簽列表。

Output:節(jié)點(diǎn)與種子節(jié)點(diǎn)的相似度。

BEGIN:

For 所有朋友節(jié)點(diǎn) do

計(jì)算節(jié)點(diǎn)的標(biāo)簽與種子節(jié)點(diǎn)標(biāo)簽相同的個(gè)數(shù)

End for

計(jì)算節(jié)點(diǎn)與種子節(jié)點(diǎn)的相似度

Return sim2

End

3.3基于共同好友數(shù)的好友推薦算法

3.3.1共同好友推薦算法思想

不管是在社交網(wǎng)絡(luò)還是現(xiàn)實(shí)生活中，人們一般可以通過朋友的朋友來認(rèn)識(shí)新的朋友。本文主要通過計(jì)算用戶與目標(biāo)用戶之間共同關(guān)注的人的數(shù)量來衡量2個(gè)用戶之間的相似度。2個(gè)用戶共同關(guān)注的人所占比例越多，那么他們就越有可能成為朋友。目標(biāo)用戶A關(guān)注的人的集合A={UA1，UA2，UA3，…，UAn}，用戶B關(guān)注的人的集合B={UB1,UB2…，UBn},然后計(jì)算A和B集合中共同的粉絲數(shù)。其計(jì)算公式為：

(5)

其中UAi，UBi分別表示A、B集合中的粉絲，如果2個(gè)用戶UAi，UBi相同，則值為1，否則值為0。根據(jù)式(2)，基于共同好友數(shù)的相似度計(jì)算公式為

(6)

3.3.2共同好友推薦算法偽代碼

Input:所有的朋友節(jié)點(diǎn)n的朋友列表，種子節(jié)點(diǎn)A的朋友列表。

Output:節(jié)點(diǎn)與種子節(jié)點(diǎn)的相似度。

BEGIN:

For 所有朋友節(jié)點(diǎn) do

計(jì)算節(jié)點(diǎn)的朋友與種子節(jié)點(diǎn)朋友相同的個(gè)數(shù)

End for

計(jì)算節(jié)點(diǎn)與種子節(jié)點(diǎn)的相似度

Return sim3

End

3.4改進(jìn)的鏈路預(yù)測(cè)好友推薦方法

3.4.1算法思想

結(jié)合基于鏈路預(yù)測(cè)、標(biāo)簽相似和共同好友相似的算法，構(gòu)造本文的推薦方法。其相似度公式為

Sim=psim1+qsim2+(1-p-q)sim3。

(7)

式中：p、q是權(quán)值參數(shù)，p表示基于鏈路預(yù)測(cè)推薦算法的權(quán)重，q表示基于標(biāo)簽相似算法的權(quán)重；sim1表示用戶在基于鏈路預(yù)測(cè)推薦算法下與目標(biāo)用戶的相似度；sim2表示用戶在基于標(biāo)簽相似算法下與目標(biāo)用戶的相似度；sim3表示用戶在基于共同好友數(shù)相似算法下與目標(biāo)用戶的相似度。在實(shí)驗(yàn)過程中通過分析p、q采用不同值對(duì)推薦結(jié)果的影響，不斷修改參數(shù)值使得推薦效果最佳且收斂。Sim即為用戶與目標(biāo)用戶之間的綜合相似度。取出Top-N個(gè)Sim作為推薦對(duì)象。

3.4.2算法偽代碼

改進(jìn)的推薦算法偽代碼實(shí)現(xiàn)如下。

input：數(shù)據(jù)集。

output：推薦好友列表。

Begin

Step1:循環(huán)利用式(1)，計(jì)算用戶x,y之間的鏈路預(yù)測(cè)相似度sim1。

Step2:根據(jù)sim1的值輸出好友列表Top-N進(jìn)入下一階段。

Step3:循環(huán)利用式(4)計(jì)算Top-N好友和目標(biāo)用戶的標(biāo)簽相似度sim2。

Step4:循環(huán)利用式(6)計(jì)算Top-N好友和目標(biāo)用戶的共同好友相似度sim3。

Step5:輸入p、q的值。

Step6:循環(huán)利用式(7)得到最終的相似度Sim。

Step7:輸出推薦的好友列表。

End

4實(shí)驗(yàn)結(jié)果與分析

4.1實(shí)驗(yàn)環(huán)境

硬件配置為內(nèi)存2 GB、硬盤230 GB、網(wǎng)卡10/100 M。軟件配置為操作系統(tǒng)Windows 7、數(shù)據(jù)庫SQL SERVER 2008 R2、開發(fā)工具VS 2010。

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

實(shí)驗(yàn)中的數(shù)據(jù)是通過調(diào)用騰訊微博開放平臺(tái)所提供的API[20]來獲取的，在實(shí)驗(yàn)過程中采用以授權(quán)用戶為種子用戶爬取與該用戶直接、間接相關(guān)的其他朋友賬戶的信息并存入數(shù)據(jù)庫，實(shí)驗(yàn)中共爬取了3層朋友信息，并將這些信息存放到數(shù)據(jù)庫中。其中部分信息如表1—3所示。AllTheName表記錄所用的相關(guān)用戶的基本信息。Sim表記錄相關(guān)用戶與目標(biāo)用戶之間的相似度。RecommendFriendsDetialInfo表記錄推薦好友的相關(guān)信息。

表1　AllTheName表

表2　Sim表

表3　RecommendFriendsDetialInfo表

4.3實(shí)驗(yàn)過程

在本文的推薦系統(tǒng)中，當(dāng)用戶點(diǎn)擊推薦朋友按鈕之后，會(huì)將與目標(biāo)用戶相似度最高的前50名用戶按相似度降序排列顯示在頁面中，如圖1所示。

圖1　好友推薦

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

本文主要采用精確率、召回率來評(píng)價(jià)實(shí)驗(yàn)結(jié)果。精確率(P)為相關(guān)用戶在Top-N個(gè)被推薦用戶中的比例。召回率(R)為Top-N個(gè)推薦用戶中相關(guān)用戶的數(shù)量在總用戶中的比例。文中的相關(guān)用戶是指目標(biāo)用戶可能添加為好友的用戶。

4.5實(shí)驗(yàn)結(jié)果

分別選擇相似度高的前10、20、30、40、50名用戶作為推薦對(duì)象，并在2種推薦算法下對(duì)推薦結(jié)果進(jìn)行統(tǒng)計(jì)，其結(jié)果如表4所示。

表4　推薦結(jié)果統(tǒng)計(jì)

根據(jù)表4的相關(guān)數(shù)據(jù)，分別計(jì)算了2種算法的精確率和召回率。圖2—3示出2種算法在各種情況下的精確率和召回率。

P(單一鏈路預(yù)測(cè))=58%；

P(改進(jìn)的鏈路預(yù)測(cè))=62%；

R(單一鏈路預(yù)測(cè))=7.47%；

R(單一鏈路預(yù)測(cè))=7.99%。

圖2　精確率對(duì)比

圖3　召回率對(duì)比

可以看出，改進(jìn)的鏈路預(yù)測(cè)算法能準(zhǔn)確地向用戶推薦新的好友，隨著推薦用戶數(shù)的增加，改進(jìn)的鏈路預(yù)測(cè)算法的精確率和召回率都比單一的鏈路預(yù)測(cè)算法好，其中精確率比單一的鏈路預(yù)測(cè)算法高8%。

在實(shí)驗(yàn)的過程中筆者為權(quán)值參數(shù)p、q賦予不同的值會(huì)出現(xiàn)不同的推薦結(jié)果。例如當(dāng)p=0.2，q=0.4時(shí)算法的精確率只能達(dá)到34.56%，遠(yuǎn)遠(yuǎn)達(dá)不到預(yù)期目標(biāo)。通過多次實(shí)驗(yàn)比較與分析，得出p=0.8，q=0.1時(shí)實(shí)驗(yàn)結(jié)果最佳。

5總結(jié)與展望

本文在鏈路預(yù)測(cè)算法的基礎(chǔ)上加入標(biāo)簽相似度和共同好友相似度，提出一種新的好友推薦算法。實(shí)驗(yàn)結(jié)果表明，本文的推薦算法解決了鏈路預(yù)測(cè)不能很好地描述用戶本身的興趣和特征的缺點(diǎn)以及協(xié)同過濾算法的數(shù)據(jù)稀疏問題，與單一的鏈路預(yù)測(cè)推薦算法相比，改進(jìn)的鏈路預(yù)測(cè)算法能更好的為用戶推薦出好友，提高了推薦的精確率。

實(shí)驗(yàn)中仍然存在著一些問題，由于騰訊微博中微博用戶的興趣標(biāo)簽比較少，造成了一定的數(shù)據(jù)缺失，這對(duì)權(quán)重的賦值有一定的影響。在接下來的工作中，希望能考慮更多的因素，使推薦效果更好。

參考文獻(xiàn)

[1]Michael M, Dosbayev Y, Berlyant M. PYMK: Friend Recommendation at Myspace [C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. New York, NY, USA: ACM, 2010: 999-1002.

[2]傅穎斌，陳羽中.基于鏈路預(yù)測(cè)的微博用戶關(guān)系分析[J].計(jì)算機(jī)科學(xué)，2014，41(2)：201.

[3]Liben-Nowell D,Kleinbe J. The Link-prediction Problem for Social Networks[J]．Twelfth International Conference on Information and knowledge Management, 2003, 58(7):556.

[4]Alexis P, Panagiotis S ,Yannis M.Fast and Accurate Link Prediction in Social Network Systems[J].The Journal of Systems and Software,2012,85:2113.

[5]Chen Jilin, Werner Geyer, Casey Dugan, et al. Make New Friends, but Keep the Old: Recommending People on Social Networking Sites[C]//Proceedings of the SIGCHI Conference on Human Factors in Computing Systems.[s.l.]：ACM,2009:201-210.

[6]鄭佳佳. 社交網(wǎng)絡(luò)中基于圖排序的好友推薦機(jī)制研究與實(shí)現(xiàn) [D]. 杭州：浙江大學(xué)，2011 .

[7]Official Facebook Blog[EB/OL].[2015-09-09].http://blog.facebook.com/blog.php?Post=136103112130,2014.

[8]Joonhee K, Sungrim K. Friend Recommendation Method using Physical and Social Context [J]. International Journal of Computer Science and Network Security, 2010, 10(11): 116.

[9]Goldberg D, Nichols D, Oki BM, et al. Using Collaborative Filtering to Weave an Information Tapestry[J].Communications of the ACM, 1992, 35(12):61.

[10]王輝,高利軍,王聽忠.個(gè)性化服務(wù)中基于用戶聚類的協(xié)同過濾推薦[J].計(jì)算機(jī)應(yīng)用，2007,27(5):1225.

[11]黃國言,李有超,高建培.基于項(xiàng)目屬性的用戶聚類協(xié)同過濾推薦算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010，31(5)：1038.

[12]陳毅波,揭志忠,吳產(chǎn)樂.基于同義標(biāo)簽分組的協(xié)同推薦[J].湖南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2011，38(5)：83.

[13]張楊.一種基于標(biāo)簽的雙向協(xié)同過濾模型[D]. 長(zhǎng)春：吉林大學(xué), 2013.

[14]胡文江, 胡大偉, 高永兵,等. 基于關(guān)聯(lián)規(guī)則與標(biāo)簽的好友推薦算法[J]. 計(jì)算機(jī)工程與科學(xué), 2013, 35(2):109.

[15]張怡文, 岳麗華, 張義飛,等. 基于共同用戶和相似標(biāo)簽的好友推薦方法[J]. 計(jì)算機(jī)應(yīng)用, 2013, 33(8):2273.

[16]Sarwar B M，Karypis G ，Konstan J A，et al．Application of Dimensionality Reduction in Recommender System-A case study[C]// KDD Workshop on Web Mining for E-Commerce Challenges and Opportunities.Boston,MA:ACM,2000：82-90.

[17]Massa P，Avesani P．Trust-aware Collaborative Filtering for Recommender Systems [J]．Lecture Notes in Computer Science，2004，3290：492-508.

[18]Vincent S-z，Boi Fahings．Using Hierarchical Clustering for Learning the Ontologies used in Recommendation Systems[C]//Proceedings of the 13th ACMSIGKDD International Confer-ence on Knowledge Discovery and Data Mining．San Jose，California，United States：ACM，2007：599-608.

[19]騰訊開放平臺(tái)[EB/OL].[2015-08-10].http://wiki.open.qq.com/wiki/API文檔.

[20]Wikipedia.Jaccard index [EB/OL].[2015-08-10].https://en.wikipedia.org/wiki/Jaccard_index.

(編校：饒莉)

A Modified Friend Recommending Method Based on Link Prediction

FU Xia1, DU Yajun1*, WU Yue1, MENG QingRui2

(1.SchoolofComputerandSoftwareEngineering,XihuaUniversity,Chengdu610039China；2.TibetFeiyueIntelligentTechnologyCo.,Ltd.,Lasa850000China)

Abstract:In order to select user who has the highest similarity with target user as a friend from the mass of the users, a modified friend recommending method based on link prediction is proposed in this paper. Firstly, through the links relationship, the Top-N users who have the highest similarity with the target user are recommended. Secondly, calculating the tag similarity and the common friends similarity between the target user and recommended Top-N users. Thirdly, giving appropriate weight to them,and calculate comprehensive similarity between target users and the recommend Top-N users. Finally, sorting users based on comprehensive similarity, and recommending the users who have the highest similarity to the target users. The experimental results show that the algorithm in this paper is higher than the single link prediction by 8% on accuracy.

Keywords:OSN; link prediction;friends recommendation; similarity; target

收稿日期：2015-08-14

基金項(xiàng)目：國家科技支撐計(jì)劃項(xiàng)目西藏自然科學(xué)博物館數(shù)字館關(guān)鍵技術(shù)研究及集成示范 (2011BAH26B01);國家自然科學(xué)基金(61472329)。

*通信作者：杜亞軍(1967—)，男，教授，博士，主要研究方向?yàn)榫W(wǎng)絡(luò)信息獲取與處理。E-mail：duyajun@mail.xhu.edu.cn

中圖分類號(hào)：TP181;TP391.3

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-159X(2016)03-0045-6

doi:10.3969/j.issn.1673-159X.2016.03.010

·計(jì)算機(jī)軟件理論、技術(shù)與應(yīng)用·