社交網絡中基于強社交圖的可信任服務商選擇*

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

蘇州大學 計算機科學與技術學院，江蘇 蘇州 215006

1 引言

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

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

Fig.1 Service-oriented social network圖1 面向服務的社交網絡圖

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

本文的目的是解決如何在包含復雜社交關系的社交網絡中尋找社交信任路徑的問題。本文的主要貢獻總結如下：

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

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

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

（4）在Enron email和Epinions這兩個真實社交網絡數據集上進行了實驗。實驗結果表明，提出的SSG-MCBA算法在路徑查找的準確率和效率方面都極大地優于現存最好的算法D-MCBA（double-Monte Carlo based algorithm）。

2 相關工作

2.1 社交網絡分析

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

2.2 社交網絡中的信任度

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

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

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

3 語義社交網絡

本章為了更好地映射到真實世界的社交網絡，提出了一個包含社會信任、社會關系和社會地位等復雜社會環境的語義社交網絡（contextual social network，CSN）結構[9,17]。

3.1 語義社交網絡

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

（1）V是節點的集合。

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

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

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

3.2 社交影響因素

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

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

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

3.3 語義社交網絡結構

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

Fig.2 Contextual social network圖2 語義社交網絡圖

4 多條社交信任路徑查找

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

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

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

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

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

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

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

5 強社交圖以及基于強社交圖的索引

5.1 強社交圖

為了提高NP完全信任路徑選擇方法的準確率和效率，提出了一種強社交圖的識別方法。在圖論中[24]，一個圖被稱作強連通圖當且僅當圖中任意兩個節點都互相可達。基于上述強連通的定義，下面給出了強社交圖的定義。

定義2（強社交圖（SSG））在語義社交網絡中，一個子圖被稱作強社交連通，當且僅當子圖中的每個節點在特定領域都有較高的社交影響因子，并且連接節點的每條邊都具有親密的社交關系以及較高的社交信任度。

根據社會心理學的相關理論[23]，人們通過長時間的觀察發現，在強社交圖中，整體的社交結構，社交環境，包括每條邊上的社交信任度和社交關系以及每個節點上的社交影響因子在很長一段時間內都會保持穩定。基于這個特性，就可以以更小的代價對強社交圖進行索引。

5.2 可達性索引

為了進一步提高NP完全MCOP-K的效率，提出了一種新的索引結構來對SSG中的可達性和社會關系進行索引。

（1）可達性索引：該索引記錄了強社交圖中某個節點能夠調查到的其他節點所構成的集合，其中每個節點的具體索引值包含了該節點的祖先及后繼節點。

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

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

下面是社交關系索引的詳細信息：

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

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

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

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

5.3 小結

Fig.3 Index of SSG in domainj圖3 強社交圖在領域 j中的索引

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

6 SSG-MCBA

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

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

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

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

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

Fig.4 BEN and FDN圖4 BEN和FDN

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

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

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

Fig.5 FEN and BDN圖5 FEN和BDN

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

7 實驗

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

7.1 實驗設置

實驗的相關設置：

（1）首先，從兩個數據集中隨機地選擇一對源點和目標點，并抽取出它們所構成的子網絡。這兩個子網一個包含1 695個節點，12 175條邊，另一個包含1 746個節點，13 320條邊。

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

（3）D-MCBA是目前最優的語義社交網絡中信任路徑查找算法。因此比較了SSG-MCBA和D-MCBA在可信路徑查找中的性能。

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

兩個實驗都使用Matlab R2013a運行，運行環境是 Intel Xeon E5645 2.40 GHz CPU，3 GB RAM，Windows 7專業版操作系統，數據庫是MySQL 5.6。

7.2 實驗結果

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

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

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

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

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得到的路徑條數（Enron email）

Fig.9 Number of paths delivered by SSG-MCBAand D-MCBA(Epinions)圖9 SSG-MCBA和D-MCBA得到的路徑條數（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數據集中不同數目的強社交圖，模擬1 000到5 000次所得出的可行社交信任路徑的數量。從圖中可以看出：（1）在所有情況下，SSGMCBA都能比D-MCBA查詢出更多的可行解。（2）在相同的模擬次數下，SSG-MCBA查詢出的可行解隨著強社交圖數量的增加而增加。這是因為當模擬次數相同時，SSG-MCBA利用社交影響因子值的索引，會有更高的可能性找到一條可行解。另外，強社交圖的數量越多，社交影響因子的索引也會更多。因此，當強社交圖的數量增多時，SSG-MCBA就可能得出更多的可行解。據統計，平均情況下，在Enron email數據集下，SSG-MCBA得出的可行解的數量是1 359.5，而D-MCBA得出的可行解數量是858.2，在Epinions數據集下，SSG-MCBA得出的可行解的數量是1 380.8，而D-MCBA得出的可行解數量是883。SSG-MCBA的結果要比D-MCBA高出57.4%。

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

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

8 總結

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