時(shí)久超，劉冠峰，李直旭，劉 安，鄭 凱

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

1 引言

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

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

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

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

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

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

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

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

（4）在Enron email和Epinions這兩個(gè)真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yà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年代，社會(huì)網(wǎng)絡(luò)研究證實(shí)了社交網(wǎng)絡(luò)中的小世界特征[10]，通過(guò)郵件發(fā)送的實(shí)驗(yàn)證明兩個(gè)美國(guó)人之間建立連接的平均路徑長(zhǎng)度約為6.6。20世紀(jì)70年代，Pool等人[11]分析了小世界特征對(duì)人們交互的影響。近年來(lái)，在計(jì)算機(jī)科學(xué)學(xué)院，Mislove等人[12]通過(guò)分析幾個(gè)流行的在線社交網(wǎng)絡(luò)（如Facebook和Flickr）來(lái)驗(yàn)證在線社交網(wǎng)絡(luò)的小世界和power law特征。

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

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

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

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

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

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

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

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

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

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

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

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

3.2 社交影響因素

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

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

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

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

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

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

4 多條社交信任路徑查找

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

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

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

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

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

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

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

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

5.1 強(qiáng)社交圖

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

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

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

5.2 可達(dá)性索引

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

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

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

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

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

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

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

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

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

5.3 小結(jié)

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

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

6 SSG-MCBA

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

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

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

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

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

Fig.4 BEN and FDN圖4 BEN和FDN

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

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

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

Fig.5 FEN and BDN圖5 FEN和BDN

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

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

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

7.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

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

7.2 實(shí)驗(yàn)結(jié)果

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

實(shí)驗(yàn)1（平均路徑效用）為了能夠根據(jù)查找到的社交信任路徑的質(zhì)量來(lái)比較算法的效用性，首先用不同的模擬次數(shù)和強(qiáng)社交圖數(shù)量來(lái)檢測(cè)相應(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。這是因?yàn)镾SG-MCBA將強(qiáng)社交圖中兩個(gè)節(jié)點(diǎn)間具有最大聚合社交因子值的社交信任路徑做了索引。這就增加了找到一條擁有較高效用值的路徑的可能性。另外，從圖中可以看出，在相同的模擬次數(shù)下，SSGMCBA得出的路徑平均效用值隨著強(qiáng)社交圖數(shù)目的增加而增加，但是D-MCBA卻不能做到這點(diǎn)。這是因?yàn)槿绻麖?qiáng)社交圖中兩個(gè)節(jié)點(diǎn)間具有最大社交影響因子值的那條社交信任路徑已經(jīng)被建立起索引，那么這種強(qiáng)社交圖的數(shù)量越多，就越有可能找到包含在其中的正向或反向擴(kuò)展節(jié)點(diǎn)。正因?yàn)槿绱?，SSGMCBA更有可能找到一條具有較高效用值的路徑。據(jù)統(tǒng)計(jì)，平均情況下，在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方法所得出的計(jì)算結(jié)果要比D-MCBA的計(jì)算結(jié)果高出11%。

實(shí)驗(yàn)2（可行社交信任路徑的數(shù)量）為了研究算法在多條社交信任路徑查找過(guò)程中的有效性，統(tǒng)計(jì)了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的平均運(yùn)行時(shí)間（Enron email）

Fig.11 Average execution time of SSG-MCBAand D-MCBA(Epinions)圖11 SSG-MCBA和D-MCBA的平均運(yùn)行時(shí)間（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ù)量的增加而增加。這是因?yàn)楫?dāng)模擬次數(shù)相同時(shí)，SSG-MCBA利用社交影響因子值的索引，會(huì)有更高的可能性找到一條可行解。另外，強(qiáng)社交圖的數(shù)量越多，社交影響因子的索引也會(huì)更多。因此，當(dāng)強(qiáng)社交圖的數(shù)量增多時(shí)，SSG-MCBA就可能得出更多的可行解。據(jù)統(tǒng)計(jì)，平均情況下，在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%。

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

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

8 總結(jié)

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