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

高燕+薛苑+張永恒

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

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

中圖分類號： 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的普及，越來越多的人生活在網上。網民們不僅在網上購物，娛樂，而且還在網上交友相親，希望通過更多的渠道認識新的朋友，從而擴展自己的社交圈。然而交友網站在給人帶來方便與快捷的同時也產生了信息冗雜、難以辨別的問題[1]。尤其對于新注冊的用戶，如何有效快速地對其進行朋友推薦成為了亟待解決的問題。

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

1 信任關系模型

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

1.1 信任模型的建立

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

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

圖1 信任關系模型

1.2 信任度計算

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

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 常用間接信任度計算

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

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

[TA，F=TA，B×TB，F+TA，C×TC，F4=0.072 5] （1）

然而該方法存在如下2個缺陷：

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

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

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

1.3 朋友推薦過程

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

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

第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，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意見的重視程度，數據更符合實際情況。

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

[T′A，F=TA，B×TB，F×TA，B =0.196] （5）

[T″A，F=TA，C×TC，F×TA，C =0.15] （6）

[T′′′A，F=TA，C×TC，B×TA，C× TB，F×TC，B=0.058] （7）

取其最大值可得T（A，F）=0.196。計算結果明確顯示出用戶A對于用戶B的意見的重視程度，數據更符合實際情況。同理，用戶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×TA，B× TF，G×TB，F=0.071] （8）

[T″A，G=TA，C×TC，F×TA，C× TF，G×TC，F=0.081] （9）

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

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

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

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

3 結 語

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

參考文獻

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

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

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

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

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

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

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

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

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

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