時久超，劉冠峰，李直旭，劉 安，鄭 凱

蘇州大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006

1 引言

近年來，社交網(wǎng)站已經(jīng)被應(yīng)用于各種各樣的活動。例如Reppler（一個提供社交媒體監(jiān)控服務(wù)的網(wǎng)站）曾經(jīng)對300名參與公司招聘流程的專業(yè)人士進(jìn)行了調(diào)查，結(jié)果表明他們中有91%的人使用在線社交網(wǎng)絡(luò)（online social network，OSN）來篩選潛在員工。再例如，一個購買者可以通過OSN（例如Facebook和Twitter）和其他電商網(wǎng)站（例如ThisNext和eBay）建立的聯(lián)系，將電商網(wǎng)站上的產(chǎn)品推薦給他/她在OSN的好友。OSN甚至已經(jīng)被用在了云環(huán)境上[1]，目的是形成一個社交云來幫助云服務(wù)共享參與者之間的社交關(guān)系。在上述活動中，OSN都被用來加強(qiáng)服務(wù)提供。然而，當(dāng)服務(wù)消費者需要從不同提供商提供的大量服務(wù)中選取一個時，除了功能性和服務(wù)質(zhì)量，信任度也是影響服務(wù)消費者做出決定的重要因素之一，此時就需要一個方法來評估出未知服務(wù)提供商的信譽(yù)情況。

在面向服務(wù)的OSN中，每個節(jié)點表示一個服務(wù)消費者或提供商（例如，在圖1中，A提供服務(wù)S1和S2并且使用服務(wù)S3、S5和S8），每條邊對應(yīng)于真實世界或者在線的交互（例如，圖1中的A→B和A→C）。在OSN中，參與者可以根據(jù)之間彼此的直接交互情況給對方一個信任值。由于每個參與者通常會與許多其他參與者進(jìn)行交互，因此，通過串聯(lián)相鄰節(jié)點間可信任的邊，就可以在兩個間接相連的節(jié)點間形成多條信任路徑。例如，在圖1中，A和E通過兩條路徑A→B→D→E和A→C→E間接相連，參與者可以基于路徑中的信任信息來評估彼此的可信度。這個過程叫作信任傳播，這條帶有信任信息并且連接著起點和終點的路徑叫作一條社交信任路徑[2-3]。例如，在圖1中，作為服務(wù)消費者的A可以根據(jù)從A到E的這條社交信任路徑評估出服務(wù)提供商E的可信度。將A稱為源參與者，E成為目標(biāo)參與者。在大型社交網(wǎng)絡(luò)中，源參與者與目標(biāo)參與者之間可能存在成千上萬條社交信任路徑[4]，因此通過計算所有社交信任路徑來評估目標(biāo)參與者的可信度耗時巨大。為了得到目標(biāo)參與者實際的信任評估結(jié)果，源參與者需要參考多個社會信任路徑[5]。因此，如何找到那些擁有較高信任值的高質(zhì)量信任路徑成為一個既有挑戰(zhàn)又十分重要的問題[4]。

Fig.1 Service-oriented social network圖1 面向服務(wù)的社交網(wǎng)絡(luò)圖

在相關(guān)文獻(xiàn)中，Lin等人[6]提出了一種最佳的社交路徑查找方法，將源參與者和目標(biāo)參與者之間的最短路徑確定為最優(yōu)路徑。但是這種方法沒有考慮參與者之間的信任信息。在其他研究中[3]，將具有最大傳播信任值的路徑識別為最值得信賴的社會信任路徑。但是，這種方法并沒有考慮到參與者的社交地位以及社交關(guān)系等相關(guān)社交信息，而這些信息對信任傳播卻有著重要的影響[7-8]。另外，源參與者可能會有不同的社交信任路徑查找標(biāo)準(zhǔn)，并且應(yīng)該能夠在信任傳播的過程中對社交關(guān)系設(shè)置一些限制，這可以幫助源參與者找到具有最可靠的信任評估結(jié)果的社交信任路徑。但是，上面提到的方法并不支持這些功能。

本文的目的是解決如何在包含復(fù)雜社交關(guān)系的社交網(wǎng)絡(luò)中尋找社交信任路徑的問題。本文的主要貢獻(xiàn)總結(jié)如下：

（1）首先介紹了復(fù)雜的社交網(wǎng)絡(luò)結(jié)構(gòu)并提出了信任質(zhì)量（quality of trust，QoT）的概念[9]，然后，將基于QoT約束的多條社交信任路徑查詢問題建模為多約束K最優(yōu)路徑（multiple constrainedKoptimal paths，MCOP-K）選擇問題，這個問題被證明為NP-完全問題[4]。

（2）為了解決NP-完全的MCOP-K問題，提出了一個由擁有較強(qiáng)社會聯(lián)系的參與者構(gòu)成的名為“強(qiáng)社交圖”（strong social graph，SSG）的概念，并提出了一種查詢SSGs的方法。

（3）根據(jù)建立索引后的SSG，通過運用蒙特卡羅方法和一些優(yōu)化策略提出了一種時間復(fù)雜度是O(MU)的新穎的近似算法SSG-MCBA（strong social graph-Monte Carlo based algorithm），其中M是模擬次數(shù)，U是社交網(wǎng)絡(luò)中的最大出度。

（4）在Enron email和Epinions這兩個真實社交網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了實驗。實驗結(jié)果表明，提出的SSG-MCBA算法在路徑查找的準(zhǔn)確率和效率方面都極大地優(yōu)于現(xiàn)存最好的算法D-MCBA（double-Monte Carlo based algorithm）。

2 相關(guān)工作

2.1 社交網(wǎng)絡(luò)分析

20世紀(jì)60年代，社會網(wǎng)絡(luò)研究證實了社交網(wǎng)絡(luò)中的小世界特征[10]，通過郵件發(fā)送的實驗證明兩個美國人之間建立連接的平均路徑長度約為6.6。20世紀(jì)70年代，Pool等人[11]分析了小世界特征對人們交互的影響。近年來，在計算機(jī)科學(xué)學(xué)院，Mislove等人[12]通過分析幾個流行的在線社交網(wǎng)絡(luò)（如Facebook和Flickr）來驗證在線社交網(wǎng)絡(luò)的小世界和power law特征。

2.2 社交網(wǎng)絡(luò)中的信任度

Yao等人[13]提出了一種名為MATRI的信任推理模型，該模型綜合考慮了信任偏差，共同引用信任和信任推理中的信任耦合等因素。這些因素可以通過矩陣來建模，其中信任推理建模為最小化觀察信任評級集合上的平方誤差。此外，Tang等人[14]提出了一種用于預(yù)測參與者之間的信任度的動態(tài)在線信任模型，該模型考慮了用戶的動態(tài)喜好，用戶對產(chǎn)品的評價以及用戶間的相互關(guān)系等因素。

2.3 OSNs中社交信任路徑的查詢

SmallBlue[6]是一個為IBM員工創(chuàng)建的在線社交網(wǎng)絡(luò)。在該系統(tǒng)中，如果一個源用戶想要找到一個目標(biāo)用戶（例如一個C++程序員），他最多考慮他們間的16條路徑，并且每條路徑的長度都不超過6，其中，最短的那條路徑就被認(rèn)為是最佳路徑。然而，這種方法忽略了一個重要因素，那就是社交網(wǎng)絡(luò)中間節(jié)點之間的信任情況，這些信任信息對用戶的最終決策產(chǎn)生重要影響。Hang等人[3]在這方面做出了改進(jìn)，他們在路徑查找的過程中進(jìn)一步考慮了參與者之間的信任度。在他們的模型中，擁有最大傳播信任值的路徑被選為最佳路徑。該方法考慮了用戶間的信任信息，但他并沒有考慮到用戶之間可能存在不同的信任評估標(biāo)準(zhǔn)。Wang等人[15]提出了一種新的社交信任路徑查找方法。該方法中，源參與者可以指定閾值。如果該方法計算出的某個推薦點的聚合信任值大于源用戶給定的閾值，那么這個推薦點就會被保留在信任網(wǎng)絡(luò)中；否則，該點就會被刪去。刪除節(jié)點后，剩余的社交信任路徑將繼續(xù)做信任評估。文獻(xiàn)[4，9，16-19]綜合考慮了具體的社交關(guān)系的約束。這些已提出的方法雖然綜合考慮了社交網(wǎng)絡(luò)中的許多屬性，并且提高了最終結(jié)果的質(zhì)量，但是當(dāng)應(yīng)用到實時的社交信任網(wǎng)絡(luò)中時，它們的準(zhǔn)確性或者效率就會變得很低[9，16-17]。

3 語義社交網(wǎng)絡(luò)

本章為了更好地映射到真實世界的社交網(wǎng)絡(luò)，提出了一個包含社會信任、社會關(guān)系和社會地位等復(fù)雜社會環(huán)境的語義社交網(wǎng)絡(luò)（contextual social network，CSN）結(jié)構(gòu)[9,17]。

3.1 語義社交網(wǎng)絡(luò)

語義社交網(wǎng)絡(luò)[9,17]是一個帶標(biāo)記的有向圖G=(V,E,LV,LE)，其中：

（1）V是節(jié)點的集合。

（2）E是邊的集合，(vi,vj)∈E表示從節(jié)點vi到節(jié)點vj的一條有向邊。

（3）LV是定義在點集V上的一個函數(shù)，對于每個節(jié)點v,LV(v)是節(jié)點v的一組標(biāo)簽。節(jié)點標(biāo)簽表示特定域中的一些社交角色。

（4）LE是定義在邊集E上的函數(shù)，對于E中的每條邊(vi,vj)，LE(vi,vj)就是(vi,vj)的一組標(biāo)簽，表示某個特定領(lǐng)域的社交關(guān)系、社交信任以及偏好等。

3.2 社交影響因素

（2）社交親密度：根據(jù)社會心理學(xué)相關(guān)理論[8]，一個參與者往往更傾向于信任和他具有更親密的社會關(guān)系的參與者，并且更愿意跟他們進(jìn)行往來。rAB∈[0,1]表示A和B之間的社交親密度，rAB=0表示A和B沒有任何的社交親密度，rAB=1表示他們有最親近的親密度。

（3）角色影響因子：根據(jù)社會心理學(xué)相關(guān)理論[7]，在某一興趣領(lǐng)域，專家的建議比普通人更為可信。因此，代表A的角色影響因子，即參與者A在領(lǐng)域i中的影響力。當(dāng)時，表示A是該領(lǐng)域的專家并且具有最大影響力；當(dāng)時，表示A對該領(lǐng)域沒有影響力。

雖然很難在各個領(lǐng)域都建立起全面的社交親密度和角色影響因子，但是可以通過利用數(shù)據(jù)挖掘技術(shù)在一些特定的社交網(wǎng)絡(luò)中進(jìn)行挖掘和建立[19-21]。

3.3 語義社交網(wǎng)絡(luò)結(jié)構(gòu)

基于上述定義的社交影響因子，提出了一種復(fù)雜語義社交網(wǎng)絡(luò)的新結(jié)構(gòu)，如圖2所示。基于這種新結(jié)構(gòu)，在下一章中，介紹一種新的社交信任路徑查詢的模型，該模型不僅考慮了社交背景的影響，還考慮了上面提到的社交影響因子的某些約束的規(guī)范。

Fig.2 Contextual social network圖2 語義社交網(wǎng)絡(luò)圖

4 多條社交信任路徑查找

本章提出了一種用于實現(xiàn)端到端并且滿足質(zhì)量信任約束的多條社交信任路徑查詢的新模型[22]。

定義1（信任質(zhì)量（QoT））是指沿著一條社交信任路徑的信任傳播過程中能夠保證一定信任度的能力，它采用社交信任(T)、社交親密度(r)以及社交影響因子 (ρ)。

在本文的模型中，源參與者可以為信任質(zhì)量屬性（即T、r和ρ）設(shè)置多個端對端的約束，并以此作為社交信任路徑上的信任評估需求標(biāo)準(zhǔn)。例如，在圖2中，源參與者A可以為從A到E這條社交信任路徑設(shè)置端到端的信任質(zhì)量約束，用QoC表示，例如分別對應(yīng)著信任質(zhì)量里面的T、r和ρ約束。

根據(jù)社會心理學(xué)的相關(guān)理論[23]，采用乘法來聚合路徑中的T和r值，用平均值來聚合路徑中節(jié)點的ρ值。使用AS(A,B)來表示A到B這條路徑上的聚合社交影響因子。其中，具體的聚合方法在文獻(xiàn)[22]有詳細(xì)討論。

在本文的模型中，定義了一個效用函數(shù)（用F表示）來度量社交信任路徑的可信任度，它采用QoT的T、r和ρ作為參數(shù)。

其中ωT、ωr和ωρ分別是T、r和ρ的權(quán)值，并且滿足0＜ωT,ωr,ωρ＜1以及ωT+ωr+ωρ=1。

一條可行的路徑是指它可以滿足多個端到端的信任質(zhì)量約束。多條社交信任路徑查詢的目的就是從多條可行路徑中找出最符合用戶給定的效用函數(shù)的那條路徑。

5 強(qiáng)社交圖以及基于強(qiáng)社交圖的索引

5.1 強(qiáng)社交圖

為了提高NP完全信任路徑選擇方法的準(zhǔn)確率和效率，提出了一種強(qiáng)社交圖的識別方法。在圖論中[24]，一個圖被稱作強(qiáng)連通圖當(dāng)且僅當(dāng)圖中任意兩個節(jié)點都互相可達(dá)?；谏鲜鰪?qiáng)連通的定義，下面給出了強(qiáng)社交圖的定義。

定義2（強(qiáng)社交圖（SSG））在語義社交網(wǎng)絡(luò)中，一個子圖被稱作強(qiáng)社交連通，當(dāng)且僅當(dāng)子圖中的每個節(jié)點在特定領(lǐng)域都有較高的社交影響因子，并且連接節(jié)點的每條邊都具有親密的社交關(guān)系以及較高的社交信任度。

根據(jù)社會心理學(xué)的相關(guān)理論[23]，人們通過長時間的觀察發(fā)現(xiàn)，在強(qiáng)社交圖中，整體的社交結(jié)構(gòu)，社交環(huán)境，包括每條邊上的社交信任度和社交關(guān)系以及每個節(jié)點上的社交影響因子在很長一段時間內(nèi)都會保持穩(wěn)定?；谶@個特性，就可以以更小的代價對強(qiáng)社交圖進(jìn)行索引。

5.2 可達(dá)性索引

為了進(jìn)一步提高NP完全MCOP-K的效率，提出了一種新的索引結(jié)構(gòu)來對SSG中的可達(dá)性和社會關(guān)系進(jìn)行索引。

（1）可達(dá)性索引：該索引記錄了強(qiáng)社交圖中某個節(jié)點能夠調(diào)查到的其他節(jié)點所構(gòu)成的集合，其中每個節(jié)點的具體索引值包含了該節(jié)點的祖先及后繼節(jié)點。

例1圖3是強(qiáng)社交圖在領(lǐng)域j上的一個索引。從圖中可以看出，每個節(jié)點的索引包括兩部分，可達(dá)性索引和社交關(guān)系索引。以節(jié)點E為例，它既有前驅(qū)節(jié)點又有后繼節(jié)點。E的可達(dá)性索引記錄了它的先節(jié)點C(Anc.:C)以及它的后繼節(jié)點H(Des.:H)。類似地，可以為圖3中的其他每個節(jié)點構(gòu)建可達(dá)性索引。如果強(qiáng)社交圖中包含兩個節(jié)點間的社交信任路徑，就可以立刻檢索出它們間的可達(dá)性，從而極大地節(jié)省了運行時間。

（2）社交關(guān)系索引：社交關(guān)系索引是用來記錄數(shù)據(jù)圖中映射路徑的最大聚合社交影響因子。

下面是社交關(guān)系索引的詳細(xì)信息：

①如果兩個節(jié)點間存在的一條路徑的聚合T，r和ρ值比這兩個節(jié)點間其他路徑上的相應(yīng)值都大，就把該路徑長度以及相關(guān)的社交影響因子值作為索引值；

②否則，將最多為3條路徑建立索引，它們分別具有最大的聚合T、r和ρ值。

例2考慮圖3中所展示的社交關(guān)系的索引。以節(jié)點C為例，從C到它的后繼節(jié)點H存在兩條路徑，分別是路徑p1(C,E,H)和路徑p2(C,F,H)，并且AS(p1(C,E,H))比AS(p2(C,F,H))的聚合社交影響因子都大。隨后，記錄p1的聚合社交影響因子。類似地，可以用這種方法對其他節(jié)點構(gòu)建索引。

基于這種社交關(guān)系索引，可以快速地搜索一個強(qiáng)社交圖中是否存在可行的社交信任路徑以及節(jié)點間是否存在具有最佳效用的最優(yōu)路徑，極大地減少了路徑查詢時間。

5.3 小結(jié)

Fig.3 Index of SSG in domainj圖3 強(qiáng)社交圖在領(lǐng)域 j中的索引

上述兩個索引記錄了強(qiáng)社交圖中社會信任路徑的一些重要信息，基于這些信息，可以快速地判斷出兩個節(jié)點間是否存在可行的社會信任路徑，并且找到包含在強(qiáng)社交圖中的具有最佳效用的最優(yōu)路徑，從而極大地減少了時間。強(qiáng)社交圖的結(jié)構(gòu)和社交關(guān)系通常會在很長的一段時間內(nèi)保持穩(wěn)定。因此，不需要頻繁地更新索引，也就減少了維護(hù)索引的開銷。另外，關(guān)于索引更新的方法在文獻(xiàn)[25-26]中有詳細(xì)的論述。

6 SSG-MCBA

在本章中，基于蒙特卡羅方法[27]，提出了一種新穎的有效并且高效的近似算法SSG-MCBA。

蒙特卡羅方法：蒙特卡羅方法[27]是一種依賴重復(fù)隨機(jī)抽樣來計算結(jié)果的計算算法，是解決NP完全問題[27-28]的方法之一。一般來講，蒙特卡羅方法包含4個步驟：（1）定義輸入；（2）產(chǎn)生隨機(jī)輸入；（3）對每個輸入執(zhí)行計算；（4）將結(jié)果聚合成最終結(jié)果。

算法描述：提出了一種新的高效近似算法SSGMCBA。SSG-MCBA采用蒙特卡羅方法分別從vt（目標(biāo)點）到vs（源點）以及vs到vt進(jìn)行路徑搜索。在每一步的搜索過程中，SSG-MCBA最多選擇K個候選點。接下來，詳細(xì)介紹SSG-MCBA。

在社交信任路徑查找中，如果一條路徑滿足信任質(zhì)量約束，那就意味著這條路徑上的每個信任質(zhì)量屬性（T、r和ρ）都應(yīng)該大于相應(yīng)的給定的信任質(zhì)量約束。因此，提出了一個目標(biāo)方程（式（2））來判斷某條路徑上的聚合屬性值是否滿足給定的信任質(zhì)量約束。從式（2）中可以看出，如果一條社交信任路徑中有一個聚合信任質(zhì)量屬性值不滿足相應(yīng)的信任質(zhì)量約束，那么δ(p)＞1，否則δ(p)≤ 1。

反向搜索：在從vt到vs的反向搜索過程中，SSGMCBA計算從vt到它的當(dāng)前向后擴(kuò)展節(jié)點（BEN，例如圖4中的節(jié)點vd）的社交信任路徑的δ值。如果這個向后擴(kuò)展節(jié)點屬于強(qiáng)社交圖，那么SSG-MCBA就可以通過社交影響因子的索引值計算具有最小δ值的路徑。否則，就需要基于下面的策略1，用SSGMCBA選擇具有前K小個δ值的鄰接點作為候選點（例如圖4中的va、vb和vc）。隨后，就可以基于式（3）選擇其中一個節(jié)點作為接下來的向后擴(kuò)展節(jié)點。

Fig.4 BEN and FDN圖4 BEN和FDN

策略1（查詢最小δ值的K路徑）根據(jù)式（2），如果一條路徑的δ值越小，那么它就越有可能成為一個可行解。因此，當(dāng)給定一個從vt到vd的已經(jīng)部分識別的社交信任路徑時，就可以為每條從vt到vd的每個鄰接點的路徑計算一個δ值，并且記錄下前K個最小值，每個值所對應(yīng)的節(jié)點（例如圖4中的va、vb和vc）都是下一個反向擴(kuò)展節(jié)點的候選節(jié)點。根據(jù)式（3）所計算出來的概率大小選擇候選節(jié)點。

正向搜索：如果通過反向搜索得到一個可行解，那么SSC-MCBA對社交網(wǎng)絡(luò)進(jìn)行一次從vs到vt的正向搜索。該過程使用上述反向搜索提供的信息來判斷是否存在一條比上述返回的可行路徑ps更好的路徑pt(F(pt)＞F(ps))。在該過程中，對于當(dāng)前向前擴(kuò)展節(jié)點的每個鄰接點，如果當(dāng)前擴(kuò)展節(jié)點屬于強(qiáng)社交圖，那么SSG-MCBA就可以根據(jù)強(qiáng)社交圖中的索引信息計算出一條社交信任路徑。否則，SSG-MCBA就會計算從vs到中間節(jié)點vm這條路徑（用表示）的聚合社交信任屬性值。用表示反向搜索得到的一條從vm到vt的路徑，結(jié)合，就可以得到一條從vs到vt的預(yù)測路徑（用表示）。接下來，基于下面的策略2，SSC-MCBA選擇滿足下列條件的K個候選點：（1）vs到vt的這條預(yù)測路徑上的所有正向擴(kuò)展節(jié)點都是可行解；（2）它們具有前K大的F值。那么根據(jù)式（4）計算出來的概率，它們有一個將會成為下一個向前擴(kuò)展節(jié)點。最終，SSG-MCBA計算出從vs到新正向擴(kuò)展節(jié)點的F值，并且根據(jù)策略2更新這條路徑上的聚合信任質(zhì)量屬性值。

策略2（查詢前K個最大F值的路徑）社交信任路徑查詢的目的就是找到那些具有最佳效用同時還滿足信任質(zhì)量約束的路徑。因此，給定一條從vs到vm(vm≠vt)的社交信任路徑，如果pfm是可行的，SSGMCBA就計算出從vs到vm的每個鄰接點的路徑效用值，并且記錄下?lián)碛星癒個最大路徑效用的鄰接點（如圖5中的節(jié)點vx、vy和vz），這些節(jié)點就是下一個正向擴(kuò)展節(jié)點的候選點。由于本文的策略是在每一步的查找過程中選擇不超過K個鄰接點，因此它可以減少搜索空間，提高執(zhí)行效率。

Fig.5 FEN and BDN圖5 FEN和BDN

SSG-MCBA使用雙重蒙特卡羅搜索，因此它的時間復(fù)雜度是O(MU)，其中M是模擬的次數(shù)，U是社交網(wǎng)絡(luò)中節(jié)點的最大出度。根據(jù)power-law特征[12]，在社交網(wǎng)絡(luò)中只有一小部分的節(jié)點擁有較高的出度，因此在SSG-MCBA中，每個節(jié)點在K路徑選擇時，不需要通過大量地修剪鄰接點（候選節(jié)點）就可以保持一個較小規(guī)模的搜索空間，這就使得SSGMCBA會有更高的可能性找到高質(zhì)量的社交信任路徑。另外，如果一個強(qiáng)社交圖包含源節(jié)點和目標(biāo)節(jié)點，SSG-MCBA就可以根據(jù)索引快速搜索到最優(yōu)的社交信任路徑。

7 實驗

目前還沒有一個包含所有社交關(guān)系（如T、r和ρ）[16]的完整的語義社交網(wǎng)絡(luò)。另一方面，由于本文算法的目標(biāo)是在在線社交網(wǎng)絡(luò)中找到多條社交信任路徑，為了研究提出的路徑查詢算法的性能，需要一個包含社交網(wǎng)絡(luò)結(jié)構(gòu)的數(shù)據(jù)集[12]。因此選擇了現(xiàn)實生活中兩個真實的社交網(wǎng)絡(luò)數(shù)據(jù)集，分別是Enron email（cs.cmu.edu/enron/，包含87 474個節(jié)點和300 511條邊）和Epinions數(shù)據(jù)集（trustlet.org，包含88 180個節(jié)點和717 667條邊）。這兩個數(shù)據(jù)集已經(jīng)被證明具有社交網(wǎng)絡(luò)的相關(guān)屬性，并且被廣泛應(yīng)用于在線社交網(wǎng)絡(luò)上的信任度研究中[10,29]。

7.1 實驗設(shè)置

實驗的相關(guān)設(shè)置：

（1）首先，從兩個數(shù)據(jù)集中隨機(jī)地選擇一對源點和目標(biāo)點，并抽取出它們所構(gòu)成的子網(wǎng)絡(luò)。這兩個子網(wǎng)一個包含1 695個節(jié)點，12 175條邊，另一個包含1 746個節(jié)點，13 320條邊。

（2）在現(xiàn)實生活中，社交影響因子的值不存在固定的模式。為了不失一般性，使用Matlab中的函數(shù)rand()函數(shù)隨機(jī)設(shè)置這些影響因子的值。

（3）D-MCBA是目前最優(yōu)的語義社交網(wǎng)絡(luò)中信任路徑查找算法。因此比較了SSG-MCBA和D-MCBA在可信路徑查找中的性能。

（4）考慮到在線社交網(wǎng)絡(luò)中小世界的特點，將最大搜索跳數(shù)設(shè)置為6。另外，設(shè)置一個相對較低的信任質(zhì)量約束(QoCT=0.005,QoCr=0.005,QoCρ=0.005)使得兩種算法有高的可能性在社交網(wǎng)絡(luò)中找到一個可行解。否則，如果兩種算法都沒有解，就無法比較它們的性能。將K值設(shè)置為5、10、15、20和25。

兩個實驗都使用Matlab R2013a運行，運行環(huán)境是 Intel Xeon E5645 2.40 GHz CPU，3 GB RAM，Windows 7專業(yè)版操作系統(tǒng)，數(shù)據(jù)庫是MySQL 5.6。

7.2 實驗結(jié)果

SSG-MCBA和D-MCBA的效用性和運行時間取5次獨立實驗的平均值。結(jié)果見圖6到圖11。

實驗1（平均路徑效用）為了能夠根據(jù)查找到的社交信任路徑的質(zhì)量來比較算法的效用性，首先用不同的模擬次數(shù)和強(qiáng)社交圖數(shù)量來檢測相應(yīng)的路徑平均效用。

圖6和圖7是SSG-MCBA和D-MCBA基于Enron email和Epinions數(shù)據(jù)集中不同數(shù)目的強(qiáng)社交圖，模擬1 000到5 000次所得出的平均路徑效用值。從這兩張圖中可以看出，SSG-MCBA方法求出的平均路徑效用值在所有情況下都要優(yōu)于D-MCBA。這是因為SSG-MCBA將強(qiáng)社交圖中兩個節(jié)點間具有最大聚合社交因子值的社交信任路徑做了索引。這就增加了找到一條擁有較高效用值的路徑的可能性。另外，從圖中可以看出，在相同的模擬次數(shù)下，SSGMCBA得出的路徑平均效用值隨著強(qiáng)社交圖數(shù)目的增加而增加，但是D-MCBA卻不能做到這點。這是因為如果強(qiáng)社交圖中兩個節(jié)點間具有最大社交影響因子值的那條社交信任路徑已經(jīng)被建立起索引，那么這種強(qiáng)社交圖的數(shù)量越多，就越有可能找到包含在其中的正向或反向擴(kuò)展節(jié)點。正因為如此，SSGMCBA更有可能找到一條具有較高效用值的路徑。據(jù)統(tǒng)計，平均情況下，在Enron email數(shù)據(jù)集下，SSGMCBA產(chǎn)生的路徑效用值是0.180 2而D-MCBA是0.159 0，在Epinions數(shù)據(jù)集下，SSG-MCBA產(chǎn)生的路徑效用值是0.181 1，而D-MCBA是0.166 8。提出的SSG-MCBA方法所得出的計算結(jié)果要比D-MCBA的計算結(jié)果高出11%。

實驗2（可行社交信任路徑的數(shù)量）為了研究算法在多條社交信任路徑查找過程中的有效性，統(tǒng)計了SSG-MCBA和D-MCBA查詢出的可行社交信任路徑的數(shù)量。

Fig.6 Average path utility delivered by SSG-MCBAand D-MCBA(Enron email)圖6 SSG-MCBA和D-MCBA得到的平均路徑效用（Enron email）

Fig.7 Average path utility delivered by SSG-MCBAand D-MCBA(Epinions)圖7 SSG-MCBA和D-MCBA得到的平均路徑效用（Epinions）

Fig.8 Number of paths delivered by SSG-MCBAand D-MCBA(Enron email)圖8 SSG-MCBA和D-MCBA得到的路徑條數(shù)（Enron email）

Fig.9 Number of paths delivered by SSG-MCBAand D-MCBA(Epinions)圖9 SSG-MCBA和D-MCBA得到的路徑條數(shù)（Epinions）

Fig.10 Average execution time of SSG-MCBAand D-MCBA(Enron email)圖10 SSG-MCBA和D-MCBA的平均運行時間（Enron email）

Fig.11 Average execution time of SSG-MCBAand D-MCBA(Epinions)圖11 SSG-MCBA和D-MCBA的平均運行時間（Epinions）

圖8和圖9是SSG-MCBA和D-MCBA基于Enron email和Epinions數(shù)據(jù)集中不同數(shù)目的強(qiáng)社交圖，模擬1 000到5 000次所得出的可行社交信任路徑的數(shù)量。從圖中可以看出：（1）在所有情況下，SSGMCBA都能比D-MCBA查詢出更多的可行解。（2）在相同的模擬次數(shù)下，SSG-MCBA查詢出的可行解隨著強(qiáng)社交圖數(shù)量的增加而增加。這是因為當(dāng)模擬次數(shù)相同時，SSG-MCBA利用社交影響因子值的索引，會有更高的可能性找到一條可行解。另外，強(qiáng)社交圖的數(shù)量越多，社交影響因子的索引也會更多。因此，當(dāng)強(qiáng)社交圖的數(shù)量增多時，SSG-MCBA就可能得出更多的可行解。據(jù)統(tǒng)計，平均情況下，在Enron email數(shù)據(jù)集下，SSG-MCBA得出的可行解的數(shù)量是1 359.5，而D-MCBA得出的可行解數(shù)量是858.2，在Epinions數(shù)據(jù)集下，SSG-MCBA得出的可行解的數(shù)量是1 380.8，而D-MCBA得出的可行解數(shù)量是883。SSG-MCBA的結(jié)果要比D-MCBA高出57.4%。

實驗3（效率性）為了研究算法的效率，檢測了在不同模擬次數(shù)和不同強(qiáng)社交圖數(shù)目的情況下兩種算法的平均運行時間。

圖10和圖11是SSG-MCBA和D-MCBA基于Enron email和Epinions數(shù)據(jù)集中不同數(shù)目的強(qiáng)社交圖，模擬1 000到5 000次所得出的平均運行時間。從圖中可以看出，在所有情況下，SSG-MCBA的執(zhí)行時間都要少于D-MCBA。另外，當(dāng)模擬次數(shù)相同的情況下，強(qiáng)社交圖的數(shù)量越多，SSG-MCBA所需的運行時間就越少。這是因為如果某個強(qiáng)社交圖包含一個正向擴(kuò)展節(jié)點或反向擴(kuò)展節(jié)點，SSG-MCBA可以直接計算出這些可行路徑的最佳效用值，因此極大地減少了運行時間。據(jù)統(tǒng)計，平均情況下，在Enron email下SSG-MCBA的運行時間是1.113 s，D-MCBA的運行時間是1.478 s，在Epinions數(shù)據(jù)集下，SSGMCBA的運行時間是1.195 s，而D-MCBA的運行時間是1.594 s。本文算法可以節(jié)省33.5%的運行時間。

8 總結(jié)

本文提出了語義社交網(wǎng)結(jié)構(gòu)以及NP完全的多約束社交信任路徑查詢問題。為了解決這些極具挑戰(zhàn)的問題，提出了強(qiáng)社交圖這個概念，并且介紹了關(guān)于它的索引方法。根據(jù)強(qiáng)社交圖的索引，提出了一個高效的近似算法SSG-MCBA來解決社交網(wǎng)絡(luò)中多條社交信任路徑查找的問題。在兩個真實數(shù)據(jù)集上的實驗結(jié)果表明，提出的SSG-MCBA方法無論是在路徑查找的質(zhì)量還是效率方面都要優(yōu)于目前最好的信任路徑查找算法，D-MCBA。