基于混合好友路徑信任度的社交好友推薦算法

陳思憬，駱冰清，孫知信

(1.南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210000;2.南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210000)

0 引 言

近年來(lái)，中國(guó)互聯(lián)網(wǎng)發(fā)展迅猛，騰訊、新浪等社交網(wǎng)絡(luò)應(yīng)用的成功案例層見疊出。面對(duì)龐大的數(shù)據(jù)，如何為用戶推薦好友成為社交網(wǎng)絡(luò)應(yīng)用市場(chǎng)角力的重點(diǎn)，衍生出了許多實(shí)用技術(shù)[1]。目前好友推薦算法的主要依據(jù)有兩類：基于用戶之間的相似性和基于用戶之間的信任度。對(duì)于如何依據(jù)用戶之間的信任度進(jìn)行好友推薦，學(xué)界進(jìn)行了大量研究[2-11]。

唐曉波等[2]提出了一種基于復(fù)雜信任網(wǎng)絡(luò)的社會(huì)化媒體好友推薦模型，通過(guò)構(gòu)建用戶的信任網(wǎng)絡(luò)體系，推薦信任度高的用戶潛在好友。朱強(qiáng)等[5]提出了一種基于信任度的協(xié)同過(guò)濾推薦算法，在算法中融入信任度的影響力。Yao等[7]將用戶好友信任度分成了主動(dòng)信任與被動(dòng)信任，并對(duì)兩種情況進(jìn)行了加權(quán)計(jì)算。Wang等[8]提出應(yīng)該依據(jù)用戶評(píng)分和好友信任度來(lái)估計(jì)用戶間的好友強(qiáng)度，結(jié)合用戶好友強(qiáng)度以及偏好相似性來(lái)進(jìn)行好友推薦。文獻(xiàn)[2,7]的算法的關(guān)注重點(diǎn)是如何更加精確地計(jì)算好友信任度，其他算法的重點(diǎn)則在于如何合理地平衡好友信任度與用戶相似度之間的關(guān)系。然而，以上算法均忽略了三度好友路徑對(duì)于用戶信任度計(jì)算的影響。

1967年，Stanley Milgram提出了六度分割理論[9]，認(rèn)為一個(gè)人跟任何一個(gè)陌生人的距離都不會(huì)超過(guò)6個(gè)人。在此基礎(chǔ)上，Nicholasa A Christakis提出了3度影響力規(guī)則(three degrees of influence rule)，認(rèn)為每一個(gè)人的行為與情感會(huì)對(duì)三度以內(nèi)的好友產(chǎn)生影響[10]。2015年，王名揚(yáng)等[11]將三度影響力理論引入好友推薦算法，提出了基于三度影響力理論的好友推薦算法，以用戶之間三度以內(nèi)的好友路徑數(shù)量為依據(jù)進(jìn)行好友推薦，拓展了好友推薦算法的關(guān)系連接范圍。然而該算法沒(méi)有考慮到用戶對(duì)其好友路徑的信任度的影響。

基于三度影響力理論(three-degree influenced)，提出一種采用三度以內(nèi)好友路徑計(jì)算好友信任度的社交網(wǎng)絡(luò)好友推薦法，并通過(guò)實(shí)驗(yàn)證明該算法的準(zhǔn)確性。

1 混合好友路徑信任度算法

1.1 好友信任的度量

信任是通過(guò)搜聚、分析用戶之間的交互行為獲得的用于衡量二人好友關(guān)系密切程度的度量。用戶之間的信任包括：

(1)認(rèn)識(shí)信任：用戶不會(huì)添加自己不了解的陌生人為好友，因此用戶之間建立好友關(guān)系時(shí)，可以認(rèn)為兩個(gè)用戶之間已經(jīng)產(chǎn)生了一定的信任關(guān)系；

(2)交互信任：用戶之間的交互行為越多，可以認(rèn)為兩個(gè)用戶之間的信任關(guān)系越強(qiáng)。

文中采用交互信任進(jìn)行信任度計(jì)算，當(dāng)用戶ai參與評(píng)論、轉(zhuǎn)發(fā)好友用戶aj的發(fā)布內(nèi)容時(shí)，其對(duì)于好友用戶aj的交互信任度會(huì)隨之增加。在此定義交互信任度算法如下：

(1)

1.2 二度好友路徑信任度

在現(xiàn)實(shí)生活中，人們通常會(huì)在他人的介紹下結(jié)交新好友，這說(shuō)明好友之間的信任是可以傳遞的，只是好友信任會(huì)在傳遞的過(guò)程中逐漸削弱。只要獲取好友用戶之間的信任度，就能夠依照某種信任傳遞規(guī)則獲知這種信任對(duì)于他人的影響[12]。假設(shè)用戶ai對(duì)于其一度好友用戶aj存在信任關(guān)系T(ai,aj)，而用戶aj對(duì)于用戶ai經(jīng)過(guò)aj的二度好友a(bǔ)k也存在信任關(guān)系T(aj,ak),那么用戶aj對(duì)于用戶ak的信任度可以在一定程度上作為用戶ai對(duì)于用戶ak的參考。基于以上認(rèn)識(shí)，定義信任傳遞規(guī)則：

Γ2(ai,aj,ak)=T(ai,aj)*T(aj,ak)

(2)

其中，ai為該路徑的起始端點(diǎn)，即該算法的源用戶；ak為目的用戶；aj為該路徑經(jīng)過(guò)的好友用戶；Γ2(ai,aj,ak)為從用戶ai出發(fā)，經(jīng)過(guò)用戶aj到達(dá)用戶ak的二度好友路徑信任度。

在實(shí)際應(yīng)用中，一般情況下兩個(gè)用戶之間總是存在多條用戶好友路徑。要實(shí)現(xiàn)信任度計(jì)算，需要聚合多條路徑的好友信任度。文中定義的二度好友路徑信任度聚合方法為：

(3)

其中，Tai為用戶ai的好友集合；ρ2(ai,ak)為從用戶ai到達(dá)用戶ak的所有二度好友路徑的信任值聚合；N為從源用戶ai到達(dá)目標(biāo)用戶ak的二度好友路徑數(shù)量。

1.3 三度好友路徑信任度

計(jì)算三度好友路徑信任度，首先要找出從源用戶到目標(biāo)用戶的三度以內(nèi)好友路徑。社交網(wǎng)絡(luò)常用的表現(xiàn)形式為拓?fù)鋱D，通常用節(jié)點(diǎn)表示用戶，用兩個(gè)節(jié)點(diǎn)間的邊表示兩個(gè)用戶之間存在的好友關(guān)系。以用戶a1為核心的虛擬社交網(wǎng)絡(luò)拓?fù)淙鐖D1所示。

圖1 虛擬社交網(wǎng)絡(luò)拓?fù)?/p>

根據(jù)圖1可以得到各個(gè)用戶的好友列表集合，即Ta1={a2,a3,a4}，Ta2={a1,a5}，Ta3={a1,a6}，Ta4={a1,a7}，Ta5={a2,a6}，Ta6={a3,a5}，Ta7={a4}。每個(gè)用戶的好友列表里任意兩個(gè)元素組成元素對(duì)，均可視為經(jīng)過(guò)該用戶的二度好友路徑。得到二度好友路徑后，只要將其端點(diǎn)用戶好友列表中的一度好友路徑與該二度好友路徑進(jìn)行匹配，即可得到三度好友路徑。在算法實(shí)際進(jìn)行過(guò)程中，需要考慮到產(chǎn)生回路的可能性，將用戶的二度好友同時(shí)也是用戶一度好友的情況篩選除去。

尋找源用戶通往目的用戶三度好友路徑的具體步驟如下：

(1)通過(guò)好友列表尋找源用戶ai的一度好友；

(2)源用戶ai的一度好友的好友列表中將除了源用戶ai之外的好友用戶ae與源用戶ai組成二度好友對(duì)；

(3)篩選二度好友對(duì)，除去路徑目的用戶ae是源用戶ai的一度好友的好友對(duì)；

(4)將好友推薦目的用戶ak的好友列表與源用戶ai的二度好友a(bǔ)e進(jìn)行匹配，得到源用戶通往目的用戶的三度好友路徑。

文中定義的單條路徑三度好友路徑信任度如下：

Γ3(ai,aj,ae,ak)=T(ai,aj)*T(aj,ae)*

T(ae,ak)

(4)

其中，ai為源用戶；ak為目的用戶；aj,ae為該路徑經(jīng)過(guò)的好友用戶；Γ3(ai,aj,ae,ak)為從用戶ai出發(fā)，經(jīng)過(guò)用戶ai，ae到達(dá)用戶ak的三度好友路徑信任度。

多條路徑好友信任度算法如下：

(5)

其中，Tai表示用戶ai的好友集合；ρ3(ai,ak)表示從用戶ai到達(dá)用戶ak的所有三度好友路徑的信任值聚合；M表示從源用戶ai到達(dá)目標(biāo)用戶ak的三度好友路徑數(shù)量。

1.4 混合好友路徑信任度

在社交網(wǎng)絡(luò)中，兩個(gè)用戶之間通常不止存在一條好友路徑，因此需要將其之間的二、三度好友路徑信任度聚合起來(lái)以得到其混合好友路徑信任度，定義如下：

(6)

文中提出的混合好友路徑信任度好友推薦算法的處理方法如圖2所示。

該算法通過(guò)分析用戶好友信息以及用戶交互信息得到用戶之間的好友路徑及其信任度，對(duì)用戶之間信任度進(jìn)行排序從而得到好友推薦結(jié)果。

2 實(shí) 驗(yàn)

2.1 實(shí)驗(yàn)數(shù)據(jù)及依據(jù)

實(shí)驗(yàn)將文中算法與依據(jù)三度以內(nèi)好友路徑數(shù)量(三度無(wú)信任)的好友推薦算法、基于共同二度以內(nèi)好友路徑信任度(二度信任)的好友推薦算法進(jìn)行比較分析。

圖2 混合好友路徑信任度好友推薦算法

目前新浪微博有很多開放API，為原始實(shí)驗(yàn)數(shù)據(jù)的采集提供了便利[13]。實(shí)驗(yàn)采用新浪微博用戶數(shù)據(jù)作為原始實(shí)驗(yàn)數(shù)據(jù)，收集、挑選了63 641個(gè)用戶信息，1 028 331個(gè)用戶互粉數(shù)據(jù)以及1 055 043條用戶交互行為數(shù)據(jù)。實(shí)驗(yàn)將用戶數(shù)據(jù)分為包含80%用戶的測(cè)試集以及20%的訓(xùn)練集。先隱藏用戶部分好友信息，將依據(jù)其他好友信息得到的推薦好友集Top-K與隱藏的好友信息進(jìn)行比對(duì)以驗(yàn)證算法的有效性。其中K表示推薦好友數(shù)量。采用準(zhǔn)確率(precision)以及召回率(recall)兩個(gè)常用指標(biāo)作為驗(yàn)證好友推薦算法有效性的依據(jù)[14]。F1-measure是綜合了precision和recall的信息檢索評(píng)價(jià)指標(biāo)。分別定義如下：

(7)

(8)

(9)

其中，H(ai)表示對(duì)用戶ai的推薦好友是用戶ai的隱藏好友的數(shù)量；K(ai)表示向用戶ai推薦的好友總數(shù)量；G(ai)表示用戶ai的隱藏好友用戶總數(shù)量。

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

實(shí)驗(yàn)將推薦好友Top-K的數(shù)量K分別設(shè)定為5、10、20，應(yīng)用precision、recall和F1-measure分別將基于二度以內(nèi)好友路徑信任度的好友推薦算法以及基于三度以內(nèi)好友路徑數(shù)量的好友推薦算法[11]與文中基于三度以內(nèi)好友路徑信任度的好友推薦算法進(jìn)行性能比較，結(jié)果如圖3～5所示。

圖3 三種算法在不同K值下的precision值

圖4 三種算法在不同K值下的recall值

圖5 三種算法在不同K值下的F1-measure值

由圖3～5可以看出，三度好友信任推薦要比三度好友無(wú)信任推薦具有更高的precision與recall，其F1-mearsure性能指標(biāo)比三度好友無(wú)信任推薦得到的要高。這證明了當(dāng)好友推薦考慮三度以內(nèi)的好友路徑影響時(shí)，考慮好友路徑的信任度影響的推薦效果要比僅僅依靠好友路徑數(shù)量進(jìn)行好友推薦的效果好。而在考慮好友路徑信任度對(duì)好友推薦效果的影響時(shí)，引入三度好友路徑的影響，其三項(xiàng)好友推薦性能指標(biāo)比僅僅考慮二度好友路徑信任度的影響均有所提升。這證明了進(jìn)行好友推薦時(shí)引入三度好友路徑的影響能有效提高好友推薦效果，同時(shí)也證明了三度影響力的正確性。

3 結(jié)束語(yǔ)

文中在三度影響力理論下對(duì)以往的好友推薦算法進(jìn)行了改進(jìn)，拓寬了好友推薦的參考因素范圍，引入三度好友路徑對(duì)好友推薦的影響。經(jīng)實(shí)驗(yàn)證明，引進(jìn)三度好友的影響力之后，好友推薦算法的準(zhǔn)確性要比僅僅考慮二度好友影響的算法高，而在三度好友影響力的基礎(chǔ)上加上好友路徑的信任度影響因素，其算法的準(zhǔn)確性更高。該算法對(duì)于好友推薦系統(tǒng)的性能有一定提高。三度影響力理論也為以后的好友推薦算法提供了新的發(fā)展思路，從而能更有效地向用戶推薦好友。

[1] 劉建國(guó),周 濤,汪秉宏.個(gè)性化推薦系統(tǒng)的研究進(jìn)展[J].自然科學(xué)進(jìn)展,2009,19(1):1-15.

[2] 唐曉波，孫 飛.基于復(fù)雜信任網(wǎng)絡(luò)的社會(huì)化媒體好友推薦研究[J].情報(bào)理論與實(shí)踐，2015，38(11)：96-102.

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

[4] 王 濤，覃錫忠，賈振紅，等.基于相似度和信任度的關(guān)聯(lián)規(guī)則微博好友推薦[J].計(jì)算機(jī)應(yīng)用，2016,36(8)：2262-2267.

[5] 朱 強(qiáng)，孫玉強(qiáng).一種基于信任度的協(xié)同過(guò)濾推薦方法[J].清華大學(xué)學(xué)報(bào):自然科學(xué)版，2014,54(3)：360-365.

[6] PAN W,XIA S,LIU Z,et al.Mixed factorization for collaborative recommendation with heterogeneous explicit feedbacks[J].Information Sciences,2016,332:84-93.

[7] YAO W,HE J,HUANG G,et al.Modeling dual role preferences for trust-aware recommendation[C]//Proceedings of the 37th international ACM SIGIR conference on research & development in information retrieval.Gold Coast,Australia:ACM,2014:975-978.

[8] WANG M,MA J.A novel recommendation approach based on users’ weighted trust relations and the rating similarities[J].Soft Computing,2015,20(10):3981-3990.

[9] KE X.A social networking services system based on the “six degrees of separation” theory and damping factor[C]//Proceedings of the 2010 2nd international conference on future networks.Washingten,DC:IEEE Computer Society,2010:438-441.

[10] WALKER S K.Connected:the surprising power of our social networks and how they shape our lives[J].Journal of Family Theory & Review,2011,3(3):220-224.

[11] 王名揚(yáng)，賈沖沖，楊東輝.基于三度影響力的社交好友推薦機(jī)制[J].計(jì)算機(jī)應(yīng)用,2015,35(7):1984-1987.

[12] 蔣黎明，張 琨，徐 建，等.證據(jù)信任模型中的信任傳遞與聚合研究[J]．通信學(xué)報(bào)，2011，32(8):91-100.

[13] 黃延煒，劉嘉勇.新浪微博數(shù)據(jù)獲取技術(shù)研究[J].信息安全與通信保密，2013(6):71-73.

[14] 朱郁筱，呂琳媛.推薦系統(tǒng)評(píng)價(jià)指標(biāo)綜述[J]．電子科技大學(xué)學(xué)報(bào)，2012，41(2):163-175.