高燕+薛苑+張永恒

摘 要： 針對(duì)如何對(duì)交友網(wǎng)站中的用戶進(jìn)行朋友推薦的問題，提出一種依據(jù)信任度進(jìn)行朋友推薦的模型。通過用戶之間的信任關(guān)系，建立信任模型，計(jì)算出該用戶和其信任距離在3個(gè)跳轉(zhuǎn)之內(nèi)的所有其他用戶的信任度。在計(jì)算用戶之間的間接信任度時(shí)引入了衰減因子，改進(jìn)了常見的間接信任度算法，從而達(dá)到依據(jù)信任度的高低依次對(duì)用戶進(jìn)行朋友推薦的目的。通過應(yīng)用該模型對(duì)一個(gè)實(shí)例模型關(guān)系進(jìn)行分析的結(jié)果表明，該朋友推薦模型能夠有效地對(duì)用戶進(jìn)行朋友推薦，體現(xiàn)了用戶對(duì)于有直接指向關(guān)系用戶的信賴程度。

關(guān)鍵詞： 信任模型； 信任度； 衰減因子； 朋友推薦模型

中圖分類號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）16?0020?03

A friend recommendation model based on user trust degree

GAO Yan1， XUE Yuan2， ZHANG Yongheng1

（1 School of Information Engineering， Yulin University， Yulin 719000， China； 2. Yulin Branch， China Telecom Corporation Limited， Yulin 719000， China ）

Abstract： A friend recommendation model based on user trust degree is proposed to solve the problem that how to recommend a friend to dating site users. The trust model is constructed according to the trust relationship between users. With model， the trust degree of users whose trust distance is within 3 jumps can be calculated for the user under recommendation. Especially the common algorithm for indirect trust degree was improved by introducing attenuation factor in the calculation of the indirect trust degree among users， so as to recommend friends to users according to trust degree. The result of using the model to analyze the model relationship of a case shows that this model can recommend friends to the user effectively and can also reflects direct trust degree of the users.

Keywords： trust model； trust degree； attenuation factor； friend recommendation model

0 引 言

隨著Internet的普及，越來越多的人生活在網(wǎng)上。網(wǎng)民們不僅在網(wǎng)上購物，娛樂，而且還在網(wǎng)上交友相親，希望通過更多的渠道認(rèn)識(shí)新的朋友，從而擴(kuò)展自己的社交圈。然而交友網(wǎng)站在給人帶來方便與快捷的同時(shí)也產(chǎn)生了信息冗雜、難以辨別的問題[1]。尤其對(duì)于新注冊(cè)的用戶，如何有效快速地對(duì)其進(jìn)行朋友推薦成為了亟待解決的問題。

從交友網(wǎng)站出現(xiàn)一直到今天，無數(shù)的學(xué)者對(duì)其進(jìn)行了研究，并推出了大量的朋友推薦模型。如文獻(xiàn)[2]提出了一種綜合信任評(píng)價(jià)度和興趣評(píng)分相似度進(jìn)行好友推薦方法；文獻(xiàn)[3]對(duì)博客進(jìn)行了分析，提出了依據(jù)博主聚類后結(jié)果進(jìn)行好友推薦的方法；文獻(xiàn)[4]提出了一個(gè)新的社會(huì)圖上基于局部隨機(jī)游走的朋友推薦方法，為用戶提供個(gè)性化朋友推薦；文獻(xiàn)[5]提出了一種根據(jù)用戶簽到位置的相似度及好友關(guān)系的綜合相似度進(jìn)行潛在用戶推薦的模型；文獻(xiàn)[6]提出了一種基于用戶間社交圈的相似程度為用戶進(jìn)行朋友推薦的在線社交網(wǎng)絡(luò)朋友推薦算法。本文針對(duì)交友網(wǎng)站的特點(diǎn)，結(jié)合以上論文的研究成果，提出了一種基于用戶信任度的朋友推薦模型。該模型能夠?qū)崿F(xiàn)對(duì)交友網(wǎng)站的用戶進(jìn)行更為方便準(zhǔn)確的朋友推薦。

1 信任關(guān)系模型

在信任網(wǎng)中，若用戶A信任用戶B，則通常在圖中用節(jié)點(diǎn)A到節(jié)點(diǎn)B的一條有向線段來表示[7]，如圖1所示。用戶A指向用戶B的有向線段上的數(shù)值表示用戶A對(duì)用戶B的信任程度，簡稱為信任度，記作T（A，B）。任意2個(gè)用戶之間存在的某一條鏈路上的跳數(shù)在本文中被稱為信任距離。本文中只考慮用戶A指其他用戶的有向信任關(guān)系，不考慮其他用戶指向A的有向信任關(guān)系。而且所取最長信任距離為3，信任距離太遠(yuǎn)難免會(huì)失去參考意義。

1.1 信任模型的建立

當(dāng)一個(gè)新用戶在交友網(wǎng)站進(jìn)行注冊(cè)時(shí)，首先要求該用戶從網(wǎng)站已有的老用戶中選擇若干個(gè)可信的用戶，并對(duì)這些用戶的信任度進(jìn)行打分，分?jǐn)?shù)可取從0～1之間的任意小數(shù)，0表示完全不信任，1表示完全信任；接著將這些可信用戶以及他們的信任度值存入該用戶對(duì)應(yīng)的數(shù)據(jù)表中，作為該用戶擁有直接信任關(guān)系的用戶。隨著該用戶在交友網(wǎng)站中的不斷交流和互動(dòng)，可以添加、更改或者刪除擁有直接信任關(guān)系的用戶，并對(duì)他們的信任度進(jìn)行修改。從而實(shí)現(xiàn)對(duì)該用戶信任關(guān)系的動(dòng)態(tài)更新。

接下來依據(jù)該用戶選擇的直接信任用戶，從數(shù)據(jù)庫中再次讀取與這些直接信任用戶擁有直接信任關(guān)系的用戶以及他們的信任度，建立該新用戶的第二層間接信任關(guān)系；以此類推，建立起最長信任距離為3的最終信任關(guān)系圖。本文以用戶A為例，按照上述過程建立用戶A的信任關(guān)系模型如圖1所示。圖中的有向線段指向體現(xiàn)了用戶之間的信任關(guān)系，有向線段上的數(shù)值體現(xiàn)了用戶之間的信任度。endprint

圖1 信任關(guān)系模型

1.2 信任度計(jì)算

在信任網(wǎng)絡(luò)中，信任度的計(jì)算已經(jīng)成為不可回避的問題。在已有的關(guān)于信任網(wǎng)絡(luò)的文獻(xiàn)中，對(duì)于信任度的取值和計(jì)算各有不同，而主要的計(jì)算難度集中在用戶間的間接信任度計(jì)算上。

1.2.1 直接信任度計(jì)算

直接信任指在信任關(guān)系圖中和用戶A有直接指向關(guān)系的用戶。如在圖1中和用戶A有直接指向關(guān)系的用戶有B，C，D。在圖1中用戶A對(duì)用戶B，C，D的信任度分別是0.7，0.5和0.4，可用T（A，B）=0.7，T（A，C）=0.5，T（A，D）=0.4來表示。

1.2.2 常用間接信任度計(jì)算

對(duì)于間接信任度的計(jì)算有許多文獻(xiàn)都對(duì)其進(jìn)行了描述?，F(xiàn)在假設(shè)用戶X和用戶Y存在間接信任關(guān)系，用IN[X，Y]表示從用戶X到用戶Y的信任鏈上所有有向線段上信任度的乘積。文獻(xiàn)[2]提到了一種通過利用IN[X，Y]除以該條信任鏈的跳數(shù)計(jì)算間接信任度的方法；文獻(xiàn)[8]中提到了一種取該條信任鏈上所有有向線段上信任度的最小值作為間接信任度的方法；文獻(xiàn)[9]提到了一種將從用戶X到用戶Y每條信任鏈的IN[X，Y]除以該條信任鏈上的跳數(shù)，并從中選取最大值作為間接信任度的方法；文獻(xiàn)[10]提到了一種首先將用戶X到用戶Y的所有信任鏈上跳數(shù)最少的信任鏈選出，其次將該最短信任鏈的IN[X，Y]除以該條信任鏈跳數(shù)的所得值作為間接信任度的方法。

但是上述文獻(xiàn)中提到的這些計(jì)算方法均沒有考慮信任傳遞時(shí)的信任衰減問題。例如在圖1中，用戶A和用戶F之間的信任鏈有3條，分別是A→B→F，A→C→F和A→C→B→F。若按照文獻(xiàn)[10]中的計(jì)算方法，首先從中挑選出跳數(shù)最短的信任鏈A→B→F和A→C→F，因?yàn)橛?條相同跳數(shù)的信任鏈，接著計(jì)算這2條信任鏈上間接信任度的平均值，將其作為A，F(xiàn)之間信任程度。由此可得：

[TA，F(xiàn)=TA，B×TB，F(xiàn)+TA，C×TC，F(xiàn)4=0.072 5] （1）

然而該方法存在如下2個(gè)缺陷：

（1） 對(duì)于用戶A來說，其對(duì)于B的直接信任度要高于該用戶對(duì)于C的直接信任度，因此用戶A會(huì)更傾向于相信B的意見。該方法并沒有體現(xiàn)這一點(diǎn)。

（2） 有些情況下，這種方法會(huì)計(jì)算出一個(gè)并不理想的信任度值。例如，用戶A和用戶G之間的信任鏈有4條，分別是A→D→G，A→B→F→G，A→C→F→G和A→C→B→F→G。若按照文獻(xiàn)[10]中的計(jì)算方法，首先從中挑選出跳數(shù)最短的信任鏈A→D→G，通過計(jì)算會(huì)發(fā)現(xiàn)這條信任鏈計(jì)算出的間接信任度是最低的。這不太符合現(xiàn)實(shí)生活中的情況。

1.2.3 改進(jìn)后的間接信任度計(jì)算

本文中在計(jì)算間接信任度時(shí)考慮到了信任傳遞時(shí)的信任衰減的問題，將2個(gè)用戶之間某信任鏈上前一級(jí)的信任度作為衰減因子引入到了該條信任鏈信任度的計(jì)算中。例如，假設(shè)用戶A和用戶Z之間存在一條信任鏈，A→B→C→…X→Y→Z，則改進(jìn)后的信任鏈上用戶A和用戶Z之間的間接信任度的計(jì)算公式為：

[TA，Z=TA，B×TB，C×TA，B×…× TY，Z×TX，Y] （2）

若2個(gè)用戶之間存在多條信任鏈，則取所有信任鏈的間接信任度的最大值作為兩用戶之間的最終間接信任度。改進(jìn)后的公式顯著體現(xiàn)了信任鏈上的用戶對(duì)于有直接指向關(guān)系用戶的信賴程度，同時(shí)避免了按照常用間接信任度方法時(shí)沒有考慮信任衰減的問題，以及有可能選出兩用戶之間最低信任度的情況，而且也保留了信任鏈上的跳數(shù)越多，則信任度有可能會(huì)越低的結(jié)果。

1.3 朋友推薦過程

第1步：依據(jù)1.1小節(jié)提到的信任關(guān)系模型的建立方法，建立用戶的信任關(guān)系模型；

第2步：依據(jù)已有的信任關(guān)系圖，利用1.2小節(jié)提到的計(jì)算公式算出用戶和信任關(guān)系圖中的所有用戶之間的信任度；

第3步：按照計(jì)算出的信任度高低依次對(duì)用戶進(jìn)行朋友推薦。

第4步：若用戶對(duì)擁有直接信任關(guān)系的用戶及其信任度進(jìn)行更新，則從第一步開始重新建立用戶的信任關(guān)系模型，重新計(jì)算和信任關(guān)系圖中的所有用戶之間的信任度，按照新的信任度取值重新對(duì)用戶進(jìn)行朋友推薦。

2 實(shí)例及結(jié)果分析

在實(shí)例分析中，以圖1中用戶之間的信任關(guān)系為例對(duì)用戶A進(jìn)行朋友推薦。

首先按照直接信任度的計(jì)算方法計(jì)算出和用戶A有直接信任關(guān)系的3個(gè)用戶B，C，D的信任度分別為：T（A，B）=0.7，T（A，C）=0.5，T（A，D）=0.4。

其次，按照間接信任度的計(jì)算方法計(jì)算出用戶A和用戶E，F(xiàn)，G之間的信任度。

用戶A和用戶E之間的信任鏈有2條，分別是A→B→E和A→C→B→E。接下來依次計(jì)算每條信任鏈上的間接信任度，并從中選取最大值。

[T′A，E=TA，B×TB，E×TA，B =0.441] （3）

[T″A，E=TA，C×TC，B×TA，C× TB，E×TC，B=0.144] （4）

取其最大值可得T（A，E）=0.441。計(jì)算結(jié)果明確顯示出用戶A對(duì)于用戶B，用戶B對(duì)于用戶C意見的重視程度，數(shù)據(jù)更符合實(shí)際情況。

用戶A和用戶F之間的信任鏈有3條，分別是A→B→F，A→C→F和A→C→B→F。接下來依次計(jì)算每條信任鏈上的間接信任度，并從中選取最大值。

[T′A，F(xiàn)=TA，B×TB，F(xiàn)×TA，B =0.196] （5）

[T″A，F(xiàn)=TA，C×TC，F(xiàn)×TA，C =0.15] （6）

[T′′′A，F(xiàn)=TA，C×TC，B×TA，C× TB，F(xiàn)×TC，B=0.058] （7）

取其最大值可得T（A，F(xiàn)）=0.196。計(jì)算結(jié)果明確顯示出用戶A對(duì)于用戶B的意見的重視程度，數(shù)據(jù)更符合實(shí)際情況。同理，用戶A和用戶G之間的信任鏈有4條，分別是A→D→G，A→B→F→G，A→C→F→G和A→C→B→F→G。接下來依次計(jì)算每條信任鏈上的間接信任度，并從中選取最大值。

[T′A，G=TA，B×TB，F(xiàn)×TA，B× TF，G×TB，F(xiàn)=0.071] （8）

[T″A，G=TA，C×TC，F(xiàn)×TA，C× TF，G×TC，F(xiàn)=0.081] （9）

[T′′′A，G=TA，C×TC，B×TA，C× TB，F(xiàn)×TC，B×TF，G×TB，F(xiàn) =0.023] （10）

[T′′′′A，G=TA，D×TD，G×TA，D =0.032] （11）

取其最大值可得T（A，G）=0.081。計(jì)算結(jié)果避免了按照常用間接信任度方法有可能選出兩用戶之間最低信任度的情況，而且也保留了信任鏈上的跳數(shù)越多，則信任度有可能會(huì)越低的結(jié)果，數(shù)據(jù)更符合實(shí)際情況。

因此對(duì)于用戶A進(jìn)行朋友推薦時(shí)，按照信任度的高低對(duì)用戶A進(jìn)行朋友推薦的順序依次為：B，C，E，D，F(xiàn)，G。

3 結(jié) 語

當(dāng)今社會(huì)交友網(wǎng)站蓬勃發(fā)展，越來越多的人選擇在網(wǎng)上擴(kuò)展自己的社交圈，因此如何快速有效對(duì)用戶進(jìn)行朋友推薦成為了眾多學(xué)者關(guān)注的問題。針對(duì)這一現(xiàn)象，構(gòu)造出一種基于信任度的朋友推薦模型。通過分析用戶信任關(guān)系，建立可動(dòng)態(tài)更新的信任關(guān)系模型，計(jì)算出某用戶對(duì)于和他有信任關(guān)系的用戶的信任度。尤其是對(duì)常見的間接信任度計(jì)算方法進(jìn)行了改進(jìn)，考慮到對(duì)于有直接指向關(guān)系用戶的信賴程度的問題，引入了衰減因子。通過實(shí)例分析表明，該模型能夠有效地按照信任度值的高低對(duì)用戶進(jìn)行朋友推薦。

參考文獻(xiàn)

[1] 鄭楊，譚玲.個(gè)性化好友推薦系統(tǒng)在社交網(wǎng)站上的應(yīng)用研究[J].今傳媒，2014（6）：117?119.

[2] 黃亮，杜永萍.基于信任關(guān)系的潛在好友推薦方法[J].山東大學(xué)學(xué)報(bào)：理學(xué)版，2013（11）：73?79.

[3] 牛慶鵬.博客朋友推薦技術(shù)的研究[D].沈陽：東北大學(xué)，2009.

[4] 俞琰，邱廣華.基于局部隨機(jī)游走的在線社交網(wǎng)絡(luò)朋友推薦算法[J].系統(tǒng)工程，2013（2）：47?54.

[5] 孫曉晨，徐雅斌.位置社交網(wǎng)絡(luò)的潛在好友推薦模型研究[J].電信科學(xué)，2014，30（10）：71?77.

[6] 王玙，高琳.基于社交圈的在線社交網(wǎng)絡(luò)朋友推薦算法[J].計(jì)算機(jī)學(xué)報(bào)，2014（4）：801?808.

[7] 周超，李博.一種基于用戶信任網(wǎng)絡(luò)的推薦方法[J].北京郵電大學(xué)學(xué)報(bào)，2014（4）：98?102.

[8] 盧竹兵.基于信任關(guān)系的協(xié)同過濾推薦策略研究[D].重慶：西南大學(xué)，2008.

[9] 龔鋼軍，熊琛，許剛.基于層次分析判斷矩陣的配用電通信業(yè)務(wù)模型的研究[J].電力系統(tǒng)保護(hù)與控制，2013（22）：19?24.

[10] 李靜，陳蜀宇，文俊浩.基于信任網(wǎng)絡(luò)的網(wǎng)格資源發(fā)現(xiàn)機(jī)制[J].重慶大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，30（1）：86?88.endprint