Web服務(wù)中的推薦機(jī)制的研究

毛莉娜 唐林燕 王曉軍

摘要：借助社會的人際關(guān)系網(wǎng)，提出web服務(wù)中基于信任網(wǎng)的推薦機(jī)制用于實(shí)現(xiàn)信任關(guān)系的傳遞，給出信任網(wǎng)的數(shù)學(xué)表達(dá)、生成算法和聚集算法，并歸納信任網(wǎng)推薦鏈之間的各種依賴關(guān)系及相應(yīng)的處理策略，最后的實(shí)驗(yàn)結(jié)果證明了其有效性。

關(guān)鍵詞：信任評估；WEB服務(wù)；信任網(wǎng)；推薦機(jī)制

中圖分類號：TP3文獻(xiàn)標(biāo)識碼：A

1引言

由于WEB服務(wù)網(wǎng)絡(luò)中存在海量的WEB服務(wù)。服務(wù)請求者與通過UDDI搜索得到的WEB服務(wù)之間往往不存在或只有少數(shù)的直接交互經(jīng)驗(yàn)。直接經(jīng)驗(yàn)的不足或缺乏使得服務(wù)請求者經(jīng)常無法評估對對方的信任關(guān)系，特別是當(dāng)服務(wù)請求者碰到一個陌生的服務(wù)或服務(wù)提供者時(shí)，如何對其進(jìn)行信任度或聲譽(yù)的評估成了一個關(guān)鍵問題。

常見的解決方法是利用其它實(shí)體的推薦信息作為評估參考。信任和聲譽(yù)可以通過”口碑”或其他實(shí)體的推薦進(jìn)行，這也就為WEB服務(wù)網(wǎng)絡(luò)中對陌生實(shí)體的評估提供了一個有效的解決途徑。本文研究重點(diǎn)是分析如何構(gòu)造實(shí)體間的信任網(wǎng)來實(shí)現(xiàn)信任關(guān)系的傳播，以獲取對陌生實(shí)體的間接信任，提出在WEB服務(wù)中基于信任網(wǎng)的推薦機(jī)制，給出相應(yīng)的數(shù)學(xué)表述以及生成算法，給出推薦鏈之間的各種依賴關(guān)系以及相應(yīng)的處理策略。

2Web服務(wù)中基于信任網(wǎng)的推薦機(jī)制

在一般的社會網(wǎng)絡(luò)中，信任關(guān)系是通過個體間的相互關(guān)系推薦而形成。然而其中某一個體的聲譽(yù)一般又取決于其他個體的推薦，同時(shí)推薦本身的聲譽(yù)也決定所推薦的信息的可信度。此種相互依賴的信任度的關(guān)系也就構(gòu)成了整個實(shí)體間的信任網(wǎng)絡(luò)，如實(shí)體A向?qū)嶓wB進(jìn)行信任評估（圖1所示）。信任網(wǎng)中任何個體的聲譽(yù)可以作為對陌生實(shí)體的評估參考。

推薦機(jī)制是信任和聲譽(yù)模型的重要組成部分，許多學(xué)者也將其作為研究的重點(diǎn)。本文提出兩個問題：

利用Jacobi迭代對信任關(guān)系矩陣進(jìn)行迭代收斂來獲取任意節(jié)點(diǎn)的全部可信度，但沒有分析迭代過程中信任關(guān)系之中的相互依賴情況；

節(jié)點(diǎn)之間的每一次交易都會在與這些節(jié)點(diǎn)有過交易的所有實(shí)體中引起迭代，因而無法適應(yīng)大規(guī)模的Web服務(wù)網(wǎng)絡(luò)。

現(xiàn)有的研究大多對信任網(wǎng)中推薦鏈的依賴關(guān)系缺乏缺乏深入的分析。

2.1基本定義和概念

本文提出的關(guān)于信任網(wǎng)中的基本定義和概念。

定義1認(rèn)識關(guān)系（acquaintancerelationship）：如果實(shí)體a認(rèn)識b，那么稱a和b間存在認(rèn)識關(guān)系，則記為Know（a，b）。

定義2熟人關(guān)系（familiartiesfamiliarties）：如果Acq（a，b）=Know（a，b）∧Know（b，a），那么就稱實(shí)體a和b是具有熟人關(guān)系。

定義3熟人關(guān)系集（acquaintanceset）：如果實(shí)體a的熟人關(guān)系集Acq（a）是所有熟人組成的集合，則可記為：Acq（a）={b∈A∧Acq（a，b）}。

定義4推薦關(guān)系（recommendrelationship）：r為一有序偶，表示實(shí)體ci對cj的推薦。

定義5推薦鏈（recommendchain）：如果對i∈[1，2，…，n-1]都有Acq（ci，ci+1），同時(shí)滿足Acq（a，c1和Acq（cn，b），那么就稱e=是從a到b的推薦鏈。其中，定義推薦鏈的長度L（e）為：L（e）=|e|=n+2。

定義6信任網(wǎng)（WebofTrust）：假設(shè)Wot（C，R，W，a，b）為一加權(quán)有向圖，其中C為有限Agent集{c1，c2，…，cn}，R={r1，r2，…，rn}是C中節(jié)點(diǎn)組成的有序推薦集，是由直接經(jīng)驗(yàn)帶來的信任關(guān)系，W為b的所有見證者集合，可用W（b），表示a為評估主體，b為評估客體。

定義7信任強(qiáng)度（trustIntensity）：這里是指在推薦信任傳遞過程中所能直接信任的可靠程度，信任強(qiáng)度可以通過實(shí)體間的直接信任關(guān)系推導(dǎo)得出，用Ti表示。

定義8推薦信任（RecommendationTrust）：這里是指包括了對目標(biāo)客體的直接信任以及對直接信任的可靠程度，可以用向量（Td，Ti）來表示，稱其為推薦信任Tr。

本文是以主觀邏輯的合意規(guī)則作為對于Td和Ti的聚集函數(shù)。其中，對Tr的計(jì)算本質(zhì)實(shí)際上就是對Td和Ti進(jìn)行合成，而信任強(qiáng)度Ti稱為權(quán)重值。

2.2推薦信息可信度分析

推薦信息是推薦實(shí)體在收到推薦請求之后，可能如實(shí)地提供推薦信息，也可能出于本身的利益考慮或其他目的而故意給出錯誤的推薦信息。對推薦信息的可信度評估就反映為對信任強(qiáng)度的計(jì)算。

對信任強(qiáng)度的計(jì)算方法主要有以下三種：①歷史推薦信息，即Ci根據(jù)Cj以往給出的推薦情況來衡量推薦信息的可靠度，確定對推薦信息的采納程度。②Cj的全局聲譽(yù)，即通過其他實(shí)體的綜合評價(jià)來考慮推薦信息的可信度，其前提是假定聲譽(yù)越高的實(shí)體所提供的推薦信息越可信。③Cj的本地聲譽(yù)，即根據(jù)Ci與Cj以往的直接交互經(jīng)驗(yàn)計(jì)算的Cj本地聲譽(yù)，并以此來衡量推薦信息的可信度。

本文結(jié)合第一種和第二種方法，也就是綜合考慮Cj的歷史推薦情況及Cj在Ci中的本地聲譽(yù)來計(jì)算Cj所提供的推薦信息的可靠度。

2.3信任網(wǎng)生成算法

信任策略1：若兩個實(shí)體之間即存在直接的推薦信任關(guān)系的話，則也會存在通過其他實(shí)體的推薦信任連接起來的間接推薦信任關(guān)系，也就是說直接經(jīng)驗(yàn)比間接經(jīng)驗(yàn)的信任度更高。如果只是采納直接推薦信任關(guān)系的話，就可忽略間接的推薦信任關(guān)系。

信任策略2：如果推薦實(shí)體不能對獲取的間接信任進(jìn)行推薦的話，那么就只允許推薦直接信任。

以上兩個策略用于約束信任網(wǎng)的拓?fù)浣Y(jié)構(gòu)，減少復(fù)雜性。其生成算法CreateWebTrust是一個深度優(yōu)先的有向圖遍歷過程，其偽代碼表示如下：

功能描述：

輸入：評估主體a，目標(biāo)客體b，a的熟人關(guān)系集Acq（a）。輸出：信任網(wǎng)Wot（C，R，W，a，b），推薦鏈集E。變量：E（推薦鏈集變量），e（推薦鏈變量，以隊(duì)列形式表示），Nt（節(jié)點(diǎn)變量），Ld（推薦鏈長度）。

算法描述：

E=，a=，a→e

Nt=FirstAcq（a）//獲取a的第一熟人

Ld=1//推薦鏈深度置1

Dfs（Nt）//開始進(jìn)行深度優(yōu)先搜索，得到推薦鏈E

RestrictWebofTrust（Wot）//對信任網(wǎng)增加信任策略1的限制

根據(jù)推薦鏈集E產(chǎn)生Wot（C，R，W，a，b）

Dfs（Nt）的過程：

功能描述：尋求滿足條件的結(jié)點(diǎn)Nt的推薦對象，輸入：節(jié)點(diǎn)Nt，輸出：滿足條件的下一節(jié)點(diǎn)

算法描述：

Ife=andNt=0then//結(jié)束搜索

Exit

Endif

IfLd

IfAcq（Nt，b）then//找到一條合法的推薦鏈

Nt→e，b→e，e→E//將e添加到推薦鏈集E中

Delete{Nt，b}frome//將{Nt，b}從e中刪除

Nt=NextAcq（1astnode（e））//獲取e最后一個節(jié)點(diǎn)的下一個熟人

Endif

IfnotAcq（Nt，b）andNt≠0then//Nt不是的b見證者，且不為空

Nt→eLd=Ld+1//將Nt添加到e的尾部，并將推薦鏈長度加1

Nt=FirstAcq（Nt）//獲取Nt的第一個熟人

Dfs（Nt）//繼續(xù)搜索

Endif

IfNt=0then//節(jié)點(diǎn)不存在

deletelastnode（e）frome//刪除e中的最后一個節(jié)點(diǎn)

Ld=Ld-1//推薦鏈長度減1

Nt=NextAcq（node（e））

（Nt）

Endif

Else//已經(jīng)達(dá)到推薦鏈的最大深度限制，需要回避

Delete1astnode（e）frome//刪除e中的最后一個節(jié)點(diǎn)

Ld=Ld-1

Nt=NextAcq（node（e））

（Nt）

Endif

2.4推薦鏈的依賴關(guān)系分析

因?yàn)閷τ赽的信任評估主要通過合理地綜合推薦鏈上的信任關(guān)系，所以要求同一推薦關(guān)系就不能在其計(jì)算過程中不斷地進(jìn)行重復(fù)的使用。依據(jù)信任網(wǎng)中的推薦鏈之間不同的依賴程度，將推薦鏈之間的依賴關(guān)系區(qū)可以分為以下兩種：

無依賴關(guān)系（NoDependentRelationship）

若推薦鏈ei和ej滿足條件：如果x∈ei/{a，b}，y∈ej/{a，b}，ei≠ejx∩y=φ，那么就稱ei和ej之間是相互獨(dú)立的，并無依賴關(guān)系（說明：ei/{a，b}為ei中去除a和b后剩下的節(jié)點(diǎn)集合）。

聚集算法（AggregateWitnessRep）描述了對無依賴關(guān)系推薦鏈上的信任觀念的綜合過程。假設(shè)信任網(wǎng)Wot（C，R，W，a，b）中集合C的節(jié)點(diǎn)個數(shù)n，設(shè)（n+1）×（n+1）階矩陣M=（mij）為Wot中的推薦路徑表示，矩陣中行節(jié)點(diǎn)排列順序?yàn)閏1，c2，…，cn，b，列的排列順序?yàn)閍，c1，c2，...，cn，且mij滿足：1（若ci為起點(diǎn)，cj為終點(diǎn)）；-1（cj為起點(diǎn)，ci為終點(diǎn)）；0（無連接關(guān)系）。

聚集算法（AggregateWitnessRep）偽代碼描述：

輸入：信任網(wǎng)Wot（C，R，W，a，b）；輸出：a對wi的信任觀念awi（信任強(qiáng)度Ti），b對wi的信任觀念wib（信任強(qiáng)度Td）；變量：CH和Cr為節(jié)點(diǎn)，t為信任觀念變量。算法描述：

Foreachiin[1..n+1]do

Ifm[i，n+1]=1then//說明節(jié)點(diǎn)ci-1∈w（b）

CT=ci-1

CH=GetConverseRecNode（CT）//逆向獲取對CT作出推薦的另一個節(jié)點(diǎn)

t=dCHCTCHrCT//計(jì)算CH對CT的信任強(qiáng)度，并賦予變量t

WhileCT≠ado//若CH為評估主體a，說明推薦鏈終止，否則繼續(xù)

CT=CH//以CH為起點(diǎn)，逆向繼續(xù)查找推薦路徑中的其他節(jié)點(diǎn)

CH=GetConverseNode（CT）

t=（CHdCtCHrCTCHCT）t//利用推薦規(guī)則進(jìn)行綜合

Endwhile

awi=t//輸出a對wi的綜合信任觀念

wib=ci-1b//輸出wi對b的信任觀念

Endif

Endof

依賴關(guān)系（DependentRelationship）

若推薦鏈ei和ej滿足條件：如果x∈ei/a，b，y∈ej/a，b，ei≠ejx∩y=φ，那么就稱ei和ej之間存在依賴關(guān)系。根據(jù)依賴程度的不同，可分為：

e1∩e2={a，c1，cn，b}。

圖2部分依賴關(guān)系的推薦鏈

a對b的綜合信任觀念正確的計(jì)算方法為：從全局的角度出發(fā)，將e1和e2結(jié)合在一起分析，認(rèn)為a對b只存在一條推薦路徑，而推薦路徑中間存在著分叉。則a對b綜合信任觀念的計(jì)算過程用ac1（（c1c2…c1cn）（c1ci+1…c1cn））cnb，以a（c1c2…ci，c1ci+1…cj）cnb表示。

PreTreatDependentLink算法的偽代碼：

ForeachwinW（b）do

Ei=getAllRecLinks（E，w）//求出所有以a為起點(diǎn)，以w為終點(diǎn)的推薦鏈

Ifcount（Et≠1then//說明推薦鏈的個數(shù)大于1

N=getAllPulicNodes（Et）//求出所有推薦鏈中公共節(jié)點(diǎn)

Ifcount（N）≠0then//推薦鏈有公共節(jié)點(diǎn)，即存在著部分依賴關(guān)系

WhileN≠do

NT=lastnode（N）//最后一個節(jié)點(diǎn)

DeleteNTfromN

NH=lastnode（N）//最后一個節(jié)點(diǎn)的前一個節(jié)點(diǎn)

DeleteNHfromN

t={0，0，1}

ForeacheinEtdo

If{NH，NT}inethen//說明推薦鏈e經(jīng)過了節(jié)點(diǎn)Nt和w

t=rNtw//對推薦鏈規(guī)則計(jì)算后的信任觀念使用合意規(guī)則合并

Endif

Endfor

Endfor

函數(shù)GetAllPulicNodes的算法描述：

ForeiinEtdo

ForejinEt//ei≠ej

Ni=firstnode（ei）

WhileNt≠0do

If（Niinej）and（nextnode（Nt）notej）then//從Nt開始分叉

Nt→N

Nt→nextnode（Nt）

Endif

If（Ntnotinej）and（nextnode（Nt）inej）then//說明在下一個節(jié)點(diǎn)收斂

Nextnode（Nt）→N//將下一個節(jié)點(diǎn)添加到N中

Nt=nextnode（Nt）//前進(jìn)下一個節(jié)點(diǎn)

Endif

Endwhile

Endfor

Endfor

Sort（N）//對N中的節(jié)點(diǎn)進(jìn)行排序。按照這些節(jié)點(diǎn)在推薦鏈上的先后順序?qū)排序

完全依賴（FullyDependent）完全依賴關(guān)系的推薦鏈如圖3所示，當(dāng)推薦實(shí)體c4和c5滿足c5∈Acq（c4）和c4∈Acq（c5）時(shí)，計(jì)算a對b的信任觀念將變得非常困難。

當(dāng)推薦鏈之間存在完全依賴關(guān)系時(shí)，將使得交集中實(shí)體的信任觀念無法合理地進(jìn)行綜合。對于此類問題，本文提出以下的解決策略如下：

信任策略3（悲觀策略，Thepessimisticstrategy）：此策略禁止信任網(wǎng)依賴關(guān)系產(chǎn)生，只能允許存在相互獨(dú)立的推薦鏈。它能夠有效地防止完全依賴關(guān)系的產(chǎn)生，但是也部分依賴關(guān)系的存在關(guān)系被禁止了。

信任策略4（樂觀策略，OptimisticStrategy）：此策略允許部分依賴關(guān)系和完全依賴關(guān)系，對于完全依賴關(guān)系的推薦鏈上的信任觀念在進(jìn)行綜合時(shí)，則需要采用特殊的策略才行。

信任策略5（折衷策略，Thecompromisestrategy）：此策略在生成信任網(wǎng)的過程中可以允許依賴關(guān)系的產(chǎn)生，但是必須要區(qū)分完全依賴關(guān)系和部分依賴關(guān)系。其中對于存在完全依賴關(guān)系的推薦鏈可全部忽略掉，而對于部分依賴關(guān)系的推薦鏈則可采用上述方法進(jìn)行解決。

本文采用的是折衷策略。但是在實(shí)際應(yīng)用過程中，則可以根據(jù)具體的實(shí)際情況來確定采用與其相符合的解決策略。

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

以下是對本文提出的各種算法的時(shí)間復(fù)雜度進(jìn)行分析

2.5.1信任網(wǎng)生成算法CreateWebofTrust

深度優(yōu)先搜索過程Dfs（Nt）

Dfs（Nt）的時(shí)間復(fù)雜度隨著NAN和Nd值的增長而迅速增長。最差情況下，信任網(wǎng)中每個推薦節(jié)點(diǎn)的熟人個數(shù)均NAN，每一條推薦路徑的深度均為Nd，這時(shí)計(jì)算復(fù)雜度為NAN的指數(shù)級，即O（NANNd）。

約束算法RestrictWebofTrust（Wot）

此算法所耗費(fèi)的時(shí)間取決于推薦鏈集E的存儲結(jié)構(gòu)。當(dāng)采用二維數(shù)組表示鄰接矩陣作為E的存儲結(jié)構(gòu)時(shí)，所需的時(shí)間為O（n3），其中n為E中的節(jié)點(diǎn)數(shù)；當(dāng)用鄰接表作E的存儲結(jié)構(gòu)時(shí)，所花的時(shí)間為O（H2×Nd），其中H為推薦鏈的個數(shù)。

2.5.2聚集算法AggregateWitnessRep

此算法的時(shí)間復(fù)雜度取決于信任網(wǎng)的存儲結(jié)構(gòu)，當(dāng)采用二維數(shù)組表示鄰接矩陣作為信任網(wǎng)的存儲結(jié)構(gòu)時(shí)，花費(fèi)的時(shí)間為O（n2），當(dāng)采用鄰接表時(shí)，花費(fèi)的時(shí)間為O（n+H），其中n為信任網(wǎng)中的節(jié)點(diǎn)數(shù)。

預(yù)處理算法PreTreatDependenLink

此算法的時(shí)間復(fù)雜度主要依賴于函數(shù)GetAllPulicNodes，其中Sort（N）所需要的時(shí)間為O（Nd2）。總的時(shí)間復(fù)雜度為O（H2×Nd+Nd2）。

對整個推薦機(jī)制而言，最困難的地方在于如何快速地找到從a到b的合法路徑。當(dāng)各個推薦節(jié)點(diǎn)的熟人集變得很大時(shí)，推薦機(jī)制的計(jì)算時(shí)間會快速地增加。在實(shí)際應(yīng)用中，需有效地限制NAN和Nd的值。

對整個推薦機(jī)制來說，如何快速找到從a到b的合法推薦路徑是一個難點(diǎn)。因?yàn)楫?dāng)熟人集很大時(shí)，推薦機(jī)制的計(jì)算時(shí)間會快速增加，須有效限制NAN和Nd的值。

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

用例描述

假設(shè)推薦鏈的深度Nd為3，在提供服務(wù)的過程中，誠實(shí)SP提供良好服務(wù)率為80%以上，惡意SP進(jìn)行的欺騙性在80%以上。各種參數(shù)設(shè)置如表1。

從圖4可得出結(jié)論，所考慮推薦鏈和信任強(qiáng)度越多，SR所訪問到的惡意SP的可能性越小。

4結(jié)束語

WEB服務(wù)中的推薦信任是各種信任和聲譽(yù)模型的重要組成部分，它有效地緩解了實(shí)體間由于直接信息的不足而帶來的評估風(fēng)險(xiǎn)。本文借助社會學(xué)的信任網(wǎng)從直接信任和信任強(qiáng)度進(jìn)行分析，描述了推薦信任在傳遞過程中的變化，歸納推薦鏈之間的依賴關(guān)系并提出相應(yīng)的解決策略。

參考文獻(xiàn)

[1]張仕斌；許春香.基于云模型的信任評估方法研究[J].計(jì)算機(jī)學(xué)報(bào)，2013，369（2）：433-431.

[2]胡春華；吳敏；劉國平.Web服務(wù)工作流中基于信任關(guān)系的QoS調(diào)度[J].計(jì)算機(jī)學(xué)報(bào)，2009，32（1）：43-53.

[3]LIJT，WANGXP，Liu.BPEER-TO-PEER環(huán)境下的TRUST模型[J].環(huán)境下的模型軟件學(xué)報(bào)，2004，15（14）：571-580.

[4]陳剛.關(guān)系網(wǎng)模型-基于社會合作機(jī)制的多AGENT協(xié)作組織方法[J].計(jì)算機(jī)研究與發(fā)展，2003，40（1）：107-114.

[5]杜靜.基于貝葉斯網(wǎng)絡(luò)的多Agent服務(wù)推薦機(jī)制研究[J].計(jì)算機(jī)科學(xué)，2010，38（4）：214-217.

[6]程冬，董才林，喻瑩.一種基于模糊理論的Web服務(wù)信任評估模型[J].計(jì)算機(jī)應(yīng)用與軟件，2012，29（10）：83-84.

[7]申利民.基于博弈論的Web服務(wù)信任評估模型[J].小型微型計(jì)算機(jī)系統(tǒng)，2014，36（8）：1681-1686.

[8]袁東維，李蜀瑜.一種基于信任的Web服務(wù)發(fā)現(xiàn)方法，2011，33（3）：194-198.

第35卷第1期2016年3月計(jì)算技術(shù)與自動化ComputingTechnologyandAutomationVol35，No1Mar.2016第35卷第1期2016年3月計(jì)算技術(shù)與自動化ComputingTechnologyandAutomationVol35，No1Mar.2016endprint