陳思憬，駱冰清，孫知信

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

0 引 言

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

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

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

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

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

1.1 好友信任的度量

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

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

(2)交互信任：用戶之間的交互行為越多，可以認為兩個用戶之間的信任關系越強。

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

(1)

1.2 二度好友路徑信任度

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

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

(2)

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

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

(3)

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

1.3 三度好友路徑信任度

計算三度好友路徑信任度，首先要找出從源用戶到目標用戶的三度以內(nèi)好友路徑。社交網(wǎng)絡常用的表現(xiàn)形式為拓撲圖，通常用節(jié)點表示用戶，用兩個節(jié)點間的邊表示兩個用戶之間存在的好友關系。以用戶a1為核心的虛擬社交網(wǎng)絡拓撲如圖1所示。

圖1 虛擬社交網(wǎng)絡拓撲

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

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

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

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

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

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

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

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

T(ae,ak)

(4)

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

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

(5)

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

1.4 混合好友路徑信任度

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

(6)

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

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

2 實 驗

2.1 實驗數(shù)據(jù)及依據(jù)

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

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

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

(7)

(8)

(9)

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

2.2 實驗結(jié)果與分析

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

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

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

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

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

3 結(jié)束語

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

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

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

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

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

[5] 朱 強，孫玉強.一種基于信任度的協(xié)同過濾推薦方法[J].清華大學學報:自然科學版，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] 王名揚，賈沖沖，楊東輝.基于三度影響力的社交好友推薦機制[J].計算機應用,2015,35(7):1984-1987.

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

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

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