一種基于信任度的朋友推薦模型

高燕+薛苑+張永恒

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

關鍵詞： 信任模型； 信任度； 衰減因子； 朋友推薦模型

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 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)上交友相親，希望通過更多的渠道認識新的朋友，從而擴展自己的社交圈。然而交友網(wǎng)站在給人帶來方便與快捷的同時也產(chǎn)生了信息冗雜、難以辨別的問題[1]。尤其對于新注冊的用戶，如何有效快速地對其進行朋友推薦成為了亟待解決的問題。

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

1 信任關系模型

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

1.1 信任模型的建立

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

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

圖1 信任關系模型

1.2 信任度計算

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

1.2.1 直接信任度計算

直接信任指在信任關系圖中和用戶A有直接指向關系的用戶。如在圖1中和用戶A有直接指向關系的用戶有B，C，D。在圖1中用戶A對用戶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 常用間接信任度計算

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

但是上述文獻中提到的這些計算方法均沒有考慮信任傳遞時的信任衰減問題。例如在圖1中，用戶A和用戶F之間的信任鏈有3條，分別是A→B→F，A→C→F和A→C→B→F。若按照文獻[10]中的計算方法，首先從中挑選出跳數(shù)最短的信任鏈A→B→F和A→C→F，因為有2條相同跳數(shù)的信任鏈，接著計算這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個缺陷：

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

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

1.2.3 改進后的間接信任度計算

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

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

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

1.3 朋友推薦過程

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

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

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

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

2 實例及結果分析

在實例分析中，以圖1中用戶之間的信任關系為例對用戶A進行朋友推薦。

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

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

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

[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。計算結果明確顯示出用戶A對于用戶B，用戶B對于用戶C意見的重視程度，數(shù)據(jù)更符合實際情況。

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

[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。計算結果明確顯示出用戶A對于用戶B的意見的重視程度，數(shù)據(jù)更符合實際情況。同理，用戶A和用戶G之間的信任鏈有4條，分別是A→D→G，A→B→F→G，A→C→F→G和A→C→B→F→G。接下來依次計算每條信任鏈上的間接信任度，并從中選取最大值。

[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。計算結果避免了按照常用間接信任度方法有可能選出兩用戶之間最低信任度的情況，而且也保留了信任鏈上的跳數(shù)越多，則信任度有可能會越低的結果，數(shù)據(jù)更符合實際情況。

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

3 結 語

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

參考文獻

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

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

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

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

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

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

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

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

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

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