,

(江西財(cái)經(jīng)大學(xué) 軟件與物聯(lián)網(wǎng)工程學(xué)院,南昌 330013)

0 概述

隨著計(jì)算機(jī)網(wǎng)絡(luò)的快速發(fā)展,網(wǎng)絡(luò)社交已經(jīng)成為人們進(jìn)行交流的主要方式之一[1]。近年來,社交網(wǎng)絡(luò)中的用戶量越來越龐大,網(wǎng)絡(luò)結(jié)構(gòu)也越來越復(fù)雜。如何快速準(zhǔn)確地預(yù)測大規(guī)模社交網(wǎng)絡(luò)中的用戶信任度顯得尤為重要。

通常情況下,信任是人們進(jìn)行一切社交活動的基礎(chǔ)[2]。同時,在實(shí)際中,信任被認(rèn)為是社交網(wǎng)絡(luò)中的一種特殊信息,其具有可傳播性、弱傳遞性和不確定性等性質(zhì)[3]。這些性質(zhì)為研究預(yù)測社交網(wǎng)絡(luò)中2個用戶間的信任度提供了思路。例如:社交網(wǎng)絡(luò)中的用戶A與用戶B素不相識,而在某個特定的環(huán)境下,A想要知道B是否可以信任。雖然A與B之前沒有任何聯(lián)系,但此時A可以通過咨詢他的朋友來搜集關(guān)于B的信任信息,并結(jié)合相關(guān)的信任推理方法最后對B做出信任度預(yù)測。

目前,社交網(wǎng)絡(luò)信任預(yù)測和個性化評估已被廣泛研究[4],且被應(yīng)用于多種領(lǐng)域,如網(wǎng)絡(luò)安全、社交服務(wù)推薦[5]、P2P網(wǎng)絡(luò)[6]、電子商務(wù)[7-8]、云計(jì)算[9]等。這些研究的主要思路為:首先,從社交網(wǎng)絡(luò)中提取出相應(yīng)的信任路徑(信任圖);然后,在該信任路徑上采用一些典型的信任整合策略計(jì)算出用戶的預(yù)測信任值,其中,基于圖簡化的信任度預(yù)測模型是研究較多的方式之一,較為典型的有Tidal Trust[10]、Mole Trust[11]和GFTrust[12]等算法。但是,這些算法通常只適用于小規(guī)模網(wǎng)絡(luò)或在大規(guī)模網(wǎng)絡(luò)中效率低下,且要求該網(wǎng)絡(luò)中每條邊都具有完整的信任關(guān)系。為解決這一問題,文獻(xiàn)[13]建立一種基于“小世界”網(wǎng)絡(luò)理論的信任圖生成框架SWTrust。該框架主要根據(jù)用戶活動域信息來計(jì)算用戶的信任相關(guān)度,并結(jié)合弱連接理論和社會距離來從大規(guī)模社交網(wǎng)絡(luò)中提取出一個信任圖,然后在該信任圖的基礎(chǔ)上利用8種基于可靠性模型的信任整合策略計(jì)算出用戶的預(yù)測信任值。但是,該方法所計(jì)算的用戶信任度依賴信任的發(fā)起者和被評價的信任者(如source和target),導(dǎo)致其計(jì)算效率存在局限性。

針對以上方法的不足,本文提出一種針對大規(guī)模社交網(wǎng)絡(luò)的用戶信任度預(yù)測算法TTDTrust。綜合考慮網(wǎng)絡(luò)中節(jié)點(diǎn)的拓?fù)涮卣骱陀脩粜湃温市畔?并設(shè)計(jì)一種用戶拓?fù)湫湃味戎笜?biāo)來衡量用戶信任信息。此外,該算法所計(jì)算的用戶拓?fù)湫湃味泉?dú)立于被評價的用戶對,即計(jì)算網(wǎng)絡(luò)中用戶拓?fù)湫湃味鹊倪^程可在線下進(jìn)行。最后,本文在真實(shí)的社交網(wǎng)絡(luò)分析數(shù)據(jù)集上進(jìn)行多次實(shí)驗(yàn)來驗(yàn)證該算法的有效性。

1 算法設(shè)計(jì)

1.1 相關(guān)定義

定義1(信任) 信任在不同領(lǐng)域有不同定義。本文主要采用文獻(xiàn)[10]對信任的定義,即信任為“一個用戶的行為將帶來好的結(jié)果”。此外,信任分為推薦信任和功能信任[4]。推薦信任是指一個用戶為某個用戶推薦另一個用戶的信任值,功能信任是一個用戶對另一個用戶的直接信任值。

通常情況下,2個用戶間的信任有2種表示方式:1)二進(jìn)制表示,即“1”表示信任,“0”表示不信任;2)將信任表示為[0,1]內(nèi)的某一個數(shù)值[14],數(shù)值越大表示越信任。本文采用后者作為信任表示方法。

定義2(信任網(wǎng)絡(luò)) 對于一個給定的社交網(wǎng)絡(luò),將其建模表示為對應(yīng)的信任網(wǎng)絡(luò)G=(N,E,W)。其中,N代表社交網(wǎng)絡(luò)中的所有用戶,E代表信任網(wǎng)絡(luò)中的有向邊集合,每一條有向邊e(ni,nj)表示用戶ni(ni∈N,0

定義3(信任路徑) 對于給定的信任網(wǎng)絡(luò)G=(N,E,W),如果該網(wǎng)絡(luò)中的一個源節(jié)點(diǎn)source到另一個目標(biāo)節(jié)點(diǎn)target之間存在一條可達(dá)的路徑p=(source,…,ni,nj,…,target),且p中任意邊e(ni,nj)上的權(quán)值tij大于信任閾值θ,則定義該路徑p為信任路徑。

定義4(信任圖) 對于給定的信任網(wǎng)絡(luò)G=(N,E,W),信任圖由source到target間的所有信任路徑構(gòu)成。

1.2 算法框架

基于第1.1節(jié)的定義,本節(jié)進(jìn)一步描述如何預(yù)測網(wǎng)絡(luò)中源節(jié)點(diǎn)source對目標(biāo)節(jié)點(diǎn)target的信任度。本文TTDTrust算法整體框架如圖1所示。該算法旨在預(yù)測大規(guī)模社交網(wǎng)絡(luò)中沒有直接社交的2個用戶之間的信任度,算法輸入為原始大規(guī)模社交網(wǎng)絡(luò)與2個待預(yù)測的用戶source和target。

圖1 TTDTrust算法整體框架

TTDTrust算法步驟為:1)將大規(guī)模社交網(wǎng)絡(luò)建模表示為信任網(wǎng)絡(luò);2)計(jì)算信任網(wǎng)絡(luò)中節(jié)點(diǎn)的拓?fù)湫湃味?在線下進(jìn)行計(jì)算);3)根據(jù)節(jié)點(diǎn)的拓?fù)湫湃味群Y選該節(jié)點(diǎn)可信任的top-k個鄰居;4)執(zhí)行深度為L的廣度優(yōu)先搜索算法,生成source到target的信任圖;5)在該信任圖上采用信任整合策略計(jì)算source對target的信任度。

1.3 拓?fù)湫湃味?/h3>

在社交網(wǎng)絡(luò)分析中,通常利用節(jié)點(diǎn)度[15]、緊密度[16]和介數(shù)中心性[17]等度量來評估節(jié)點(diǎn)的信息傳播能力。其中,節(jié)點(diǎn)度因設(shè)計(jì)簡單而被廣泛運(yùn)用,但其難以充分度量節(jié)點(diǎn)的信息傳播能力。相比之下,緊密度和介數(shù)中心性因考慮到節(jié)點(diǎn)與節(jié)點(diǎn)之間的信息,可以較好地體現(xiàn)節(jié)點(diǎn)的信息傳播能力,但是其計(jì)算復(fù)雜度較高。因此,這3種度量方法均難以直接應(yīng)用于社交網(wǎng)絡(luò)信任度預(yù)測中。文獻(xiàn)[18]通過考慮節(jié)點(diǎn)鄰居度信息,提出用一種局部中心性指標(biāo)來評估節(jié)點(diǎn)的信息傳播能力。通常,在該指標(biāo)考慮節(jié)點(diǎn)三步內(nèi)鄰居的入出度情況時,就可以達(dá)到較好的效果,且其計(jì)算過程只需在一步節(jié)點(diǎn)度的基礎(chǔ)上進(jìn)行即可。因此,該指標(biāo)不僅具有較好的信息傳播能力,而且具備節(jié)點(diǎn)度計(jì)算簡單的特點(diǎn)。基于此,本文提出一種新的度量節(jié)點(diǎn)信任能力的指標(biāo):拓?fù)湫湃味?該指標(biāo)綜合考慮網(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)涮卣骱陀脩舻男湃温市畔?。?jié)點(diǎn)拓?fù)湫湃味热鐖D2所示。

圖2 節(jié)點(diǎn)拓?fù)湫湃味仁疽鈭D

定義5(節(jié)點(diǎn)拓?fù)湫湃味? 圖2中的一個信任網(wǎng)絡(luò)G=(N,E,W)共有11個節(jié)點(diǎn),邊上權(quán)值為2個用戶的信任率,則定義節(jié)點(diǎn)n1的拓?fù)湫湃味萒degree(n1)的計(jì)算公式如下:

綜上,對于一個給定的信任網(wǎng)絡(luò)G=(N,E,W)和2個用戶source、target,通過式(1)可以事先(脫機(jī)處理)計(jì)算出所有節(jié)點(diǎn)的拓?fù)湫湃味取?/p>

1.4 信任整合策略

通常情況下,信任整合包括2個步驟:

步驟1針對信任圖中的每條路徑整合出一個信任值。

步驟2聚合多條路徑的信任值,即將步驟1中的所有信任值聚合成一個整體的信任度。

本文在實(shí)驗(yàn)過程中實(shí)現(xiàn)了基于可靠性模型[19]的4種信任整合策略,具體信息如表1所示。

表1 信任整合策略信息

1.5 TTDTrust算法描述

TTDTrust算法主要針對一個給定的大規(guī)模社交網(wǎng)絡(luò)和用戶source、target,預(yù)測source對target的信任度。其偽代碼如算法1所示。

算法1TTDTrust

輸入信任網(wǎng)絡(luò)G,源節(jié)點(diǎn)source,目標(biāo)節(jié)點(diǎn)target,搜索廣度上界k,搜索深度上界L,信任閾值θ

輸出source對target的信任度t(source,target)

1.Queue={source},tempQ={}//初始化隊(duì)列Queue為

//source,tempQ為空

2.depth=0//初始化搜索深度為0

3.Spath={}//初始化信任路徑集為空

4.while (Queue非空,且depth小于等于L)do

5.從Queue中取出最前面的元素,并賦給v節(jié)點(diǎn)

6.從v所有鄰居中篩選出拓?fù)湫湃味茸罡叩那皌op-k個鄰居

7.for (v節(jié)點(diǎn)的top-k鄰居中每一個節(jié)點(diǎn)u)do

8.查詢獲取u的拓?fù)湫湃味萒degree(u)//事先通過式(1)

//線下計(jì)算并存儲Tdegree(u)

9.if(u未訪問,且Tdegree(u)大于θ)then

10.if(u是target節(jié)點(diǎn))then

11.從target回溯source得到一條信任路徑p

12.將p加入到Spath中

13.else

14.將u加入到tempQ中

15.標(biāo)記u已經(jīng)被訪問

16.end if

17.end if

18.end for

19.if (Queue為空)then

20.將tempQ中的元素賦給Queue

21.depth增加1

22.清空tempQ

23.end if

24.end while

25.在Spath上分別利用4種信任整合策略計(jì)算出t(source,target)

26.return t(source,target)

TTDTrust算法具體流程如下:

步驟1初始化數(shù)據(jù)結(jié)構(gòu)與參數(shù)(第1行～第3行)。隊(duì)列Queue和tempQ分別用于存儲當(dāng)前層訪問的節(jié)點(diǎn)和下一層訪問的節(jié)點(diǎn),depth用于記錄每次遍歷的深度,Spath={}用于存儲最強(qiáng)信任路徑集。

步驟2執(zhí)行具有限制條件的廣度優(yōu)先搜索算法(第4行～第24行):1)只要隊(duì)列Queue不為空,且搜索深度depth≤L,就取出Queue中最前面的節(jié)點(diǎn)并賦給節(jié)點(diǎn)v;2)根據(jù)之前線下計(jì)算存儲的節(jié)點(diǎn)拓?fù)湫湃味?從v的所有鄰居中篩選出拓?fù)湫湃味茸罡叩那皌op-k個鄰居;3)遍歷該top-k個鄰居中的每個節(jié)點(diǎn)u,查詢u的拓?fù)湫湃味萒degree(u);4)對u進(jìn)行判斷,如果u沒有被訪問且Tdegree(u)大于給定的信任閾值θ,則繼續(xù)判斷u是否為目標(biāo)節(jié)點(diǎn)target,如果是目標(biāo)節(jié)點(diǎn),即從target回溯到source生成一條信任路徑p,并把p添加到信任路徑集Spath中,否則,標(biāo)記u已經(jīng)被訪問,同時將u放入tempQ隊(duì)列中;5)如果Queue為空,則將tempQ隊(duì)列中的元素全部賦給Queue隊(duì)列,同時將搜索深度depth加1,并清空tempQ隊(duì)列。

步驟3分別采用表1中的4種信任整合策略計(jì)算出source對target的預(yù)測信任度t(source,target)(第25行)。

1.6 算法復(fù)雜度分析

TTDTrust算法的計(jì)算時間主要包括線下計(jì)算時間和線上計(jì)算時間2個部分。

1)線下計(jì)算時間。線下計(jì)算過程主要為計(jì)算網(wǎng)絡(luò)中所有用戶的拓?fù)湫湃味取Ｔ撨^程遍歷每個用戶三步鄰居的邊,即需要掃描3|E|條邊,因此,該過程時間復(fù)雜度為O(|E|)。

2)線上計(jì)算時間。線上計(jì)算包括2個部分:(1)執(zhí)行搜索寬度為k、深度為L的廣度優(yōu)先搜索算法;(2)根據(jù)信任圖(信任路徑集)計(jì)算source對target的預(yù)測信任度。首先,為限制廣度優(yōu)先搜索算法的廣度,采用查找排序算法篩選每個用戶的top-k個鄰居,其時間復(fù)雜度為O(|N|·logak);然后,執(zhí)行廣度優(yōu)先搜索算法,該過程最差情況的時間復(fù)雜度為O(|V|+|E|)。此外,在計(jì)算source對target預(yù)測信任度的過程中,需要掃描信任圖中的每條路徑和路徑上的邊權(quán)(信任率),又因?yàn)樾湃螆D中只有|Spath|條信任路徑,每條路徑的邊數(shù)最多不超過L,且|Spath|和L通常是一個較小的常數(shù),所以該過程的時間復(fù)雜度為O(1)。因此,線上計(jì)算過程的時間復(fù)雜度為O(|N|·logak)。

綜上,TTDTrust算法的總時間復(fù)雜度為O(|E|+|n|·logak),線上計(jì)算的時間復(fù)雜度為O(|N|·logak),遠(yuǎn)小于傳統(tǒng)的全遍歷信任度預(yù)測算法的復(fù)雜度O(|V|·|E|),尤其是在大型網(wǎng)絡(luò)中,TTDTrust算法的時間復(fù)雜度優(yōu)勢更明顯。

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

2.1 數(shù)據(jù)集說明與實(shí)驗(yàn)設(shè)置

本文采用真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)集Epinions[20]進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)中舍棄不存在信任關(guān)系的用戶和邊,最后得到7 375個用戶節(jié)點(diǎn)和111 781條邊?？紤]到數(shù)據(jù)集中的信任表示為二進(jìn)制類型,在實(shí)驗(yàn)過程中,本文采用文獻(xiàn)[14]方法,將用戶二值信任關(guān)系轉(zhuǎn)換為[0,1]范圍內(nèi)的信任表示。具體方法為:首先,為每個用戶節(jié)點(diǎn)賦一個質(zhì)量qi∈[0,1],且qi～N(μ,σ2);然后,從[max(qj-δij,0),min(qj+δij,1)]范圍內(nèi)均勻地選取用戶ni對nj的信任值t(ni,nj)。其中,δij=(1-qi)/2表示噪音系數(shù),t(ni,nj)的范圍為[0,1],其值越大表示ni對nj越信任。

本次實(shí)驗(yàn)使用的個人計(jì)算機(jī)配置為64位win7操作系統(tǒng),處理器為Intel(R) Core(TM) i5-2400 CPU@3.10 GHz RAM 8 G。實(shí)驗(yàn)參數(shù)如表2所示。

表2 實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)過程采用留一法進(jìn)行測試。實(shí)驗(yàn)次數(shù)τ=10 000,每次實(shí)驗(yàn)隨機(jī)地抽取一條邊進(jìn)行測試,將第i次實(shí)驗(yàn)中2個用戶之間的實(shí)際信任度值記為treal(i),預(yù)測信任度值記為tpred(i)。相應(yīng)的信任度評估指標(biāo)為平均絕對誤差(MAE)、準(zhǔn)確度(Precision)、召回率(Recall)和F值。各值計(jì)算公式為:

Precision=|SA∩SB|/SB

(3)

Recall=|SA∩SB|/SA

(4)

F=2×Precision×Recall/(Precision+Recall)

(5)

其中,SA、SB分別為實(shí)驗(yàn)隨機(jī)抽取的邊中treal(i)大于θ和tpred(i)大于θ的邊集合。

2.2 算法性能分析

2.2.1 TTDTrust算法精度

為驗(yàn)證TTDTust算法的有效性,分別運(yùn)用4種典型信任整合策略測試TTDTust算法的信任預(yù)測精度,實(shí)驗(yàn)結(jié)果如表3所示。

表3 TTDTrust算法的信任預(yù)測精度

由表3可以看出,在4種信任整合策略中,Min-WAve的MAE、Precision、Recall和F值都優(yōu)于其他3種策略,即Min-WAve預(yù)測效果最好。此外,從表3還可以看出,4種策略的綜合指標(biāo)F最小值為0.883 1,最大值為0.897 0,該結(jié)果驗(yàn)證了TTDTust算法具有較高的信任預(yù)測精度。

2.2.2 TTDTrust算法與典型預(yù)測算法的對比分析

在社交網(wǎng)絡(luò)信任度預(yù)測研究領(lǐng)域中,Tidal Trust算法[10]較典型,且其具有很強(qiáng)的代表性。此外,文獻(xiàn)[13]提出的SWTrust算法也是針對大規(guī)模社交網(wǎng)絡(luò)進(jìn)行用戶信任度預(yù)測研究,且是近幾年社交網(wǎng)絡(luò)信任度預(yù)測模型中效果較好的算法之一。因此,本節(jié)實(shí)驗(yàn)通過Min-WAve策略,進(jìn)行TTDTrust算法與Tidal Trust算法、SWTrust算法的性能對比分析,實(shí)驗(yàn)結(jié)果如表4所示。其中,T表示算法運(yùn)行時間。

表4 3種算法在Min-WAve策略下的性能對比分析

由表4可以看出,與Tidal Trust、SWTrust算法相比,TTDTrust算法MAE值分別降低了29.62%和23.33%,Precision值分別提高了1.55%和0.33%,Recall值分別提高了9.65%和8.27%,F值分別提高了5.74%和4.43%。此外,在計(jì)算效率上,因?yàn)門TDTrust算法的線上計(jì)算時間較少,所以其總體計(jì)算時間大幅減少,Tidal Trust算法的計(jì)算時間是TTDTrust算法的6.65倍,SWTrust算法的計(jì)算時間是TTDTrust算法的6.05倍。這些結(jié)果均能說明TTDTrust算法針對大規(guī)模社交網(wǎng)絡(luò)用戶信任度預(yù)測時具有較好的效率。

2.2.3 參數(shù)k、L、θ對TTDTrust算法的影響

TTDTrust算法涉及3個關(guān)鍵參數(shù):k,L,θ。因此,本節(jié)實(shí)驗(yàn)分別測試參數(shù)k、L、θ對TTDTrust算法的影響,算法MAE值、F值、T值3個指標(biāo)的實(shí)驗(yàn)結(jié)果如圖3所示。其中,圖3(a)～圖3(c)的實(shí)驗(yàn)參數(shù)為k∈[3,27]、L=6、θ=0.5;圖3(d)～圖3(f)的實(shí)驗(yàn)參數(shù)為k=9、L∈[2,10]、θ=0.5;圖3(g)～圖3(i)的實(shí)驗(yàn)參數(shù)為k=9、L=6、θ∈[0.1,0.9]。

圖3 參數(shù)k、L、θ對TTDTrust算法的影響

由圖3(a)～圖3(f)可以看出,在k∈[3,9]、L∈[2,6]范圍內(nèi),隨著k、L的增大,TTDTrust算法的MAE值逐漸減小,F值、T值均逐漸增加。隨后,MAE值和F值開始收斂,T值增長放緩。此外,在圖3(c)中,T值增長曲線的趨勢與log函數(shù)基本相同。該結(jié)果與前文分析的TTDTrust算法時間復(fù)雜度為O(|N|·logak)相吻合。

由圖3(g)～圖3(i)可以看出,在θ∈[0.1,0.5]范圍內(nèi),隨著θ的增大,TTDTrust算法的MAE值、F值變化較小,而在θ=0.5后,MAE值顯著增大、F值顯著減小。這說明信任閾值θ不能設(shè)置過大,原因是信任閾值太大會導(dǎo)致太多的路徑被剔除,即信任閾值過大將導(dǎo)致source獲得過少關(guān)于target的信息,以至于降低了TTDTrust算法的精度。此外,從圖3(i)可以看出,隨著θ的增大,TTDTrust算法的運(yùn)行時間變化甚微。

綜上可知,k、L和θ對TTDTrust算法均有較大影響,尤其在k∈[3,9]、L∈[2,6]、θ∈[0.5,0.9]范圍內(nèi)影響較顯著。從實(shí)驗(yàn)結(jié)果可以看出,在實(shí)際應(yīng)用中取k=9、L=6和θ=0.5時,算法效果較好。

3 結(jié)束語

本文綜合考慮網(wǎng)絡(luò)中的節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)信息和用戶信任率信息,提出一種針對大規(guī)模社交網(wǎng)絡(luò)的用戶信任度預(yù)測算法TTDTrust,并設(shè)計(jì)一種用戶拓?fù)湫湃味戎笜?biāo)來衡量用戶信任信息。在真實(shí)的社交網(wǎng)絡(luò)分析數(shù)據(jù)集上進(jìn)行多方面的實(shí)驗(yàn)測試,結(jié)果表明,與典型算法Tidal Trust、SWTrust相比,TTDTrust算法具有較高的信任預(yù)測精度和計(jì)算效率。由于實(shí)際社交網(wǎng)絡(luò)往往具有較復(fù)雜的網(wǎng)絡(luò)環(huán)境,且用戶信任的影響因素較多,因此下一步將考慮多因素的信任建模并構(gòu)建可應(yīng)用于復(fù)雜網(wǎng)絡(luò)環(huán)境的信任模型。