面向社交網絡中多背景的信任評估模型

孟憲佳,馬建峰,王一川,盧笛

(西安電子科技大學計算機學院,710071,西安)

?

面向社交網絡中多背景的信任評估模型

孟憲佳,馬建峰,王一川,盧笛

(西安電子科技大學計算機學院,710071,西安)

針對信任由背景敏感性導致的在社交網絡中難以有效評估用戶間接信任值的問題,提出了一種面向多交互背景的間接信任評估模型(multiple-context trust evaluation,MCTE)。該模型利用相關性概念,通過對各背景下網絡結構和用戶信任關系的綜合分析,建立覆蓋在信任網絡之上的相關性網絡,進而利用交互背景的相關性計算跨背景用戶的間接信任值。模型避免了多背景以及疏散網絡中間接用戶信任路徑難以尋求,以及信任衰減對評估的影響,有針對性地為用戶組建立相關網絡,保證了預測的準確性及合理性。對真實社交網絡的實驗結果表明,MCTE模型不僅可以計算單一背景下用戶的間接信任值,更適用于多交互背景下用戶信任值的預測。與已有模型相比,評估準確度有較大的提高。

社交網絡;信任評估;多背景

線上社交網絡設計的初衷是讓網絡成員能夠與更多的陌生成員進行交互,從而開拓新的商業、政治、交際的可能性[1-3],然而由于其開放性以及廣泛的流行性,用戶的隱私以及數據安全問題成為其達到預期目的的重大阻礙之一[4]。建立一個讓社交網絡成員公開、自由、安全分享信息的平臺是必須要面對的問題[5-6]。社交網絡成員利用信任關系建立交互并處理復雜的系統和信息的不確定性所帶來的各種威脅是解決這一問題的有效途徑。在這種框架下,信任是社會成員之間所有交互的基礎[7],也是分享信息和開發新的社會關系的決定因素[8]。

近年來,眾多學者從事于社交網絡中對未知用戶的信任評估研究。Andersen等提出了基于平均理念的評估方案[9-10],這些方案適用于各種網絡環境中,然而對于社交網絡個體的特殊性不能有效地描述。Golbeck等提出了基于信任傳遞性的評估模型[11-12],這種模型利用信任的傳遞性建立節點間的信任路徑對信任值進行評估,然而這些方法無法建立多背景下的信任路徑。Hang等提出了一種基于網絡相似性的評估機制[13],然而這種機制對于非對稱的信任關系不能有效地區分。

對背景敏感是信任的重要屬性[14-15],如何綜合利用已知背景下的信任信息,對各個背景下未知節點的信任值進行評估是上述方法不能有效解決的問題。本文提出一種基于網絡相關性的信任評估模型(multiple-context trust evaluation,MCTE),這種模型利用相關性的概念計算網絡節點,再利用相關性網絡完善信任網絡。最后,未知的信任值從完善后的信任網絡得到。這種算法不僅適用于單背景下的陌生網絡節點的信任評估,更在多背景環境下有著出色的表現,對于解決跨背景信任評估問題較現有算法有著較大的優勢。通過對真實社交網絡的數據進行測試,發現在準確度方面超過現有的算法,在節點的可計算度方面與傳遞法基本持平,略低于平均法,但是由于平均法的高誤差,MCTE方案在綜合性能上超過現有的算法。

1 相關性網絡

為了建立相關性網絡,本文將共同信任以一種條件概率的形式定義,即假設存在用戶A、B、C,那么A與B共同信任C的概率為,在B信任C的條件下A同樣信任C的概率。本文用T(A/B)表示A對B的信任值,T((A∪B)/C)表示A、B共同對C的信任值,那么在如圖1所示的信任網絡中,當A、B的獨立性無法確定的情況下只能得到

T((A∪B)/C)≠T(A/C)T(B/C)

(1)

然而當T(B/C)=1時可以得到

T((A∪B)/C)≠T(A/C)

(2)

圖1 簡單信任網絡

如上所述,當B完全信任C時,A與B共同信任C的情況就相當于A單獨信任C的情況。信任的準確量化對于社交網絡用戶來說往往是困難的,因此在實際應用中用戶的信任常出現相信或不相信這種二元分布,即信任值為1的情況是大量存在的。

令T(A)為A對任意與其相連的用戶的信任值的期望,則

T(A)=EXT(A/X)

(3)

在信任網絡中,A可能產生信任關系的用戶未必都與其直接相連,對于和A不直接相連用戶的信任值應視為一個缺省值而非0。

由式(1)可得,在不能確定用戶之間的獨立性時同樣滿足

T(A∪B)=EXT((A∪B)/X)

然而,在B對用戶群X完全信任的情況下由式(2)可得

T(A∪B)=EXT(A/X)

(4)

令R(A/B)表示用戶A與用戶B的相關度,它表示A在B完全信任某隨機用戶的條件下同樣信任該用戶的概率。A與B的相關性可以在整個信任網絡中傳播。

R(A/B)的計算方法為

R(A/B)=EX(T((A∪B)/X)/T(B/X)=1)=

EXT(A/X)

(5)

相關性不同于相似性。它們最直觀的區別是相似性是一種對稱的特性,也就是說假使A與B相似,那么B與A也相似,然而本文所述的相關性是非對稱的,即R(A/B)≠R(B/A)。此外,在實際的信任網絡中經常會見到用戶A、B對某用戶個體或群體擁有相同的信任值,不能由這種現象估計A與B的相關性,盡管其行為非常相似。

在定義了用戶的相關性后,可以在信任網絡之上構建相關性網絡,從而擴展信任的傳播性。由式(5)可得,當T(A/X)≠null且T(B/X)=1時,R(A/B)=EXT(A/X)。可以將R(A/B)視作當T(A/X)≠null且T(B/X)=1時的均值,從而由部分T(A/X)觀測值預測未知的T(A/X)值。當用戶樣本非常龐大時,對任意用戶X在T(B/X)=1時,可以近似地估計其信任值

T(A/X)≈R(A/B)

進一步考慮到每一個至少通過某一用戶群體X從而與A相關的用戶B,可以得到

T(A/X)≈EBR(A/B)

(6)

圖2所示為建立在信任網絡之上的相關性網絡,虛線代表相關性,實線代表信任值。

圖2 相關性網絡及底層信任網絡

由式(6)可得用戶A對D的信任值為

T(A/D)=(0.8+0.6)/2=0.7

相關性網絡是建立在信任網絡基礎上的,因此可以依靠相關性網絡由已知用戶的信任關系估計未知用戶的信任關系,將式(5)代入式(6)可得

R(A/X)≈EBR(A/B)=EBEY(A/Y)

(7)

僅當T(B/Y)=1且T(B/X)=1

以上關于相關性網絡的推導均建立在A與B的獨立性不確定的基礎上,但在實際的社交網絡中,用戶的獨立性往往是很明顯的。因此,在確定用戶獨立的基礎上可以得到如下公式

EXT((A∪B)/X)=EXT(A/X)T(B/X)

進一步由式(5)和式(6)可得

R(A/B)=EXT(A/X)T(B/X)/EXT(B/X)

X≠A≠B

(8)

X≠A≠B

(9)

式(8)、式(9)在實際社交網絡中的信任評估有著重要的作用。利用相關性的特點不僅可以對相同交互背景下的節點進行信任評估,同樣適用于不同交互背景下的用戶建立信任評估模型。

2 MCTE模型

假設存在如圖3所示的兩種相互獨立的交互背景A和B,在環境A中用戶C1對用戶C2的信任概率為TA(C1/C2),在環境B中用戶C1對用戶C2的信任概率為TB(C1/C2),那么用戶C1在環境A與環境B中共同信任C2的概率為

TAB(C1/C2)=TA(C1/C2)TB(C1/C2)

圖3 雙背景下的信任網絡示例

在環境A中用戶C1對所有交互對象的信任的期望為EXTA(C1/X),簡記做TA(C1),同理在環境B中C1對所有交互對象的信任的期望為TB(C1)。這里在環境A與環境B中,用戶C1交互的對象集合為同一集合X={x1,x2,…,xi},且xi不等于C1。

用戶C1在環境A與環境B中同時信任集合X的概率為

T(A∪B)(C1)=EX(TA(C1/X)TB(C1/X))

根據貝葉斯公式

TA|B(C1)=

EX(TA(C1/X)TB(C1/X))/EXTB(C1/X)

TA|B(C1)是環境A與環境B的相關性函數,為了更加明確地表示,將TA|B(C1)記做RA|B(C1)。再次通過貝葉斯公式可以求得如圖1所示的在環境A中用戶C1對用戶R(A∪B)的信任值。具體方法如下

TB(C1/R(A∪B)))/TB(C1/R(A∪B))-

上述計算方法是通過用戶C1在環境B中對R(A∪B)的信任情況預測該用戶在環境A中對R(A∪B)的信任情況。在現實環境中,可能存在許多C1與R(A∪Y)交互的環境,單獨依靠某一環境的信任狀況作為參考不夠全面,應該對這些環境中的信任情況作綜合考慮。具體方法如下所述:假設存在Y個獨立且與C1擁有共同交互對象R(A∪Y)的環境,由環境Y與環境A的相關性計算用戶C1對R(A∪Y)的信任值TA(C1/RA∪Y),再通過求TA(C1/RA∪Y)的期望,得到在環境A中用戶C1對R的信任值

TA(C1/R)=∑YTA(C1/RA∪Y)/|Y|

(10)

式中:|Y|是不同環境的個數。

3 實 驗

本文提出的MCTE信任評估模型在實際社交網絡中的實驗主要面向兩個問題:第一是信任評估的準確度;第二是在社交網絡中用戶的可評估度。所謂可評估度是指在有一定用戶信任資料以及網絡拓撲結構信息的情況下,可以預測未知用戶信任值的能力。

采用公開的Advogato數據集[16]抽取出用戶在不同背景下的交互以及評價記錄,分別建立相應的信任關系。該數據集的用戶數量十分龐大,考慮到實驗環境等諸多方面的因素,本文抽取500個活躍用戶作為網絡節點,并以其存在的信任關系為邊構建信任網絡。時間方面采用的交互數據起始日期為2012年9月,截止日期為2013年6月,并分別抽取其中連續的3個月進行3次實驗。為了與本文提出的信任模型比較,對以上數據集還分別用兩種現存的方案進行了信任評估。這兩種方案分別是:①平均法,這種方法先找到所有除A外其他用戶對B的信任值,再求出這些值的均值作為A對B的信任值;②傳遞法,這種方法以信任的傳遞性為依據,在A對B進行信任評估時,首先找出在網絡中所有從A到B的路徑,再由這些路徑分別計算信任值,最后綜合這些信任值計算A對B的信任值。在綜合各路徑的信任值時現存的方案有多種,有的采用均值的方法,有的采用最大或最小值的方法,有的對各路徑進行分類,并按照一定的規則對各路徑的影響賦以權值,從而進行綜合評估。本文采用均值法處理各路徑的信任值。至于其他的信任綜合方法與均值法相比顯示的優勢遠不及MCTE模型與其相比的優勢。

首先在同一背景下以相關性網絡方案與其他兩種方案進行比較。圖4描述了相關性網絡方案與其他兩種方案相比在準確度上的優勢。圖中橫坐標S是邊數與節點數的比值,表示每個用戶平均評價其他用戶的數量。由圖可以很明顯地觀察到,相關性網絡方案計算得到的信任值的準確度在全部覆蓋率范圍內保持在0.85±0.04。在覆蓋率小于2的區間,準確度由0.85開始緩慢地減小。在覆蓋率達到4附近時減小到最低,這可能是由于覆蓋率在較低的區間增長,增加了許多干擾信息以使算法的準確度降低。當覆蓋率達到6左右時,準確度又回升到初始的0.85,相關性網絡在準確度方面的優勢較之另外兩種算法是非常明顯的。平均法計算的信任準確度很低的原因是其對個體特殊性的不敏感,從完全均衡的角度來度量用戶的信任值,忽略了信任的主觀特性,因此造成較大的誤差。傳遞法在準確度上比平均法有了很大的提高,其能夠從特定用戶出發,找到一條由評估者到受評估者的路徑,然而和MCTE方法相比還存在一定的差距。

圖4 3種評估方法在單背景下的準確度比較

圖5顯示了在可評估度方面相關性網絡與其他兩種方案的比較。可評估度定義為在所有的網絡節點中可評估節點的百分比。從圖中可以觀察到,平均法在可評估度上占有巨大的優勢,MCTE方案和傳遞法的結果有著近似的表現。在覆蓋率等于2(平均每個用戶只對兩個用戶進行過信任評估)時,僅有8%的可評估度。隨著覆蓋率達到4,可評估度上升到31%。在覆蓋率達到6時,可評估度達到45%,并且上升趨勢開始減慢。由圖還可見,MCTE方案的可評估度在覆蓋率為4左右時上升趨勢最明顯。這一現象的原因是在現實網絡中用戶之間的連線往往出現高度的集群化現象,而非完全隨機的分布,這同樣也說明在稀疏網絡中MCTE方案能夠達到令人滿意的效果。雖然平均法在可評估度上有著較大的優勢,但是由之前的實驗可得其在準確度方面的表現較差。在現實的社交網絡中,信任評估的準確性較之網絡的可評估度對用戶來說往往更為重要。

圖5 3種評估方法在單背景下的可評估度比較

前文中對單背景MCTE方案與其他兩種方案在準確性和可評估度方面做了比較,下文對多背景下信任值的準確性和可評估度做出比較。本文選取用戶在2種和10種相互獨立背景下的信任評估數據,如圖6所示,隨著背景的增加,MCTE模型的準確度也會提高。這是由于MCTE方案隨著背景的增加可以選擇更短并且相關性更強的路徑對用戶信任值進行評估。另外可以觀察到,準確度隨著背景的增長,每增加一個背景即增加0.01±0.005的準確度,這也代表著在每一背景下的平均誤差減少了大約0.01。在實際的社交網絡中,交互背景的數量遠不止幾個或幾十個,MCTE方案的使用將在更多背景的應用場合發揮更大的優勢。

圖6 信任值在多背景下準確度的比較

圖7顯示了在多背景下MCTE方案在可評估度方面的表現。與準確度類似,MCTE方案隨著背景的增加可評估度也隨之提高,其增加幅度大致在0.01±0.01范圍內。舉例來說,從單背景到2背景,可評估度提高的均值為0.03,這代表著網絡中增加了3%的節點可以評估,到10背景時,可評估度提高的均值達到0.09。在實際的社交網絡中存在大量的交互背景,MCTE的性能將進一步提高。

圖7 信任值在多背景下可評估度的比較

4 結 論

社交網絡中的間接信任評估是信任計算中的熱點問題,由于信任對交互背景敏感的特性,本文在分析現存方案所存在的不足后,提出了基于相關性網絡的信任評估模型MCTE,這種模型可以有效地克服現存的模型在以下兩方面的缺點:僅考慮網絡全局性而忽略節點自身特性;僅通過簡單的傳遞模型而忽略信任的衰減。MCTE利用相關性的概念在原有信任網絡之上建立相關性網絡,再由完備的相關性網絡更新信任網絡,從而得到未知網絡成員的信任狀況。這種方法不僅可以計算單背景下的未知用戶的信任值,同樣適用于多背景環境下。對真實社交網絡的實驗結果表明了MCTE模型的可用性,以及較現有模型的優勢。

MCTE對于未知信任節點的評估強烈依賴于現存信任網絡中信任關系的準確性,對于存在惡意或是不能給出準確信任信息的網絡,模型的性能受到較大的限制。如何辨別惡意節點和優化現有信任關系的準確度是將來研究的方向之一。

[1]SHERCHAN W, NEPAL S, PARIS C.A survey of trust in social networks [J].ACM Computing Surveys, 2013, 45(4):47-79.

[2]BARNES J A.Class and committees in a Norwegian island parish [J].Human Relations, 1954, 7(1):39-58.

[3]張賽, 徐恪, 李海濤.微博類社交網絡中信息傳播的測量與分析 [J].西安交通大學學報, 2013, 47(2):124-130.ZHANG Sai, XU Ke, LI Haitao.Measurement and analysis of information propagation in online social networks like microblog [J].Journal of Xi’an Jiaotong University, 2013, 47(2):124-130.

[4]GROSS R, ACQUISTI A.Information revelation and privacy in online social networks [C]∥Proceedings of the ACM Workshop on Privacy in the Electronic Society.New York, USA:ACM, 2005:71-80.

[5]MOLM L D, TAKAHASHI N, PETERSON G.Risk and trust in social exchange:an experimental test of a classical proposition [J].American Journal of Sociology, 2000, 105(5):1396-1427.

[6]ZAPPEN J P, HARRISON T M, WATSON D.A new paradigm for designing e-government:Web 2.0 and experience design [C]∥Proceedings of the International Conference on Digital Government Research.Berlin, Germany:Springer, 2008:17-26.

[7]ABDUL-RAHMAN A, HAILES S.Supporting trust in virtual communities [C]∥Proceedings of the 33rd Hawaii International Conference on System Sciences.Piscataway, NJ, USA:IEEE, 2000:1-9.

[8]DWYER C, HILTZ S R, PASSERINI K.Trust and privacy concern within social networking sites:a comparison of Facebook and Myspace [C]∥Proceedings of the 13th Americas Conference on Information Systems.Atlanta, GA, USA:Association Information Systems, 2007:1725-1735.

[9]ANDERSEN R, BORGS C, CHAYES J, et al.Trust-based recommendation systems:an axiomatic approach [C]∥Proceedings of the 17th International Conference on Intelligent User Interfaces.New York, USA:ACM, 2008:199-208.

[10]O’DONOVAN J, SMYTH B.Trust in recommender systems [C]∥Proceedings of the 10th International Conference on Intelligent User Interfaces.New York, USA:ACM, 2005:167-174.

[11]GOLBECK J, HENDLER J.Inferring binary trust relationships in web based social networks [J].ACM Transactions on Internet Technology, 2006, 6(4):497-529.

[12]HUANG Zan, CHEN H, ZENG D.Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering [J].ACM Transactions on Information Systems, 2004, 22(1):116-142.

[13]HANG C W, SINGH M P.Trust based recommendation based on graph similarities [EB/OL].(2010-11-13) [2014-09-10].http:∥www.csc.ncsu.edu/faculty/mpsingh/papers/mas/aamas-trust-10-graph.pdf.

[14]TOIVONEN S, LENZINI G, UUSITALO I.Context-aware trust evaluation functions for dynamic reconfigurable systems [C]∥Proceedings of the Models of Trust for the Web Workshop.Berlin, Germany:Springer, 2006:11.

[15]ROUSSEAU D M, SITKIN S B, BURT R S, et al.Not so different after all:a cross-discipline view of trust [J].Academy Management Review, 1998, 23(3):393-404.

[16]MASSA P, SOUREN K, SALVETTI M, et al.Trustlet, open research on trust metrics [J].Journal of Scalable Computing:Practice and Experience, 2008, 9(4):341-351.

(編輯 武紅江)

MCTE:a Trust Evaluation Model for Multiple Context in Social Networks

MENG Xianjia,MA Jianfeng,WANG Yichuan,LU Di

(School of Computer Science and Technology, Xidian University, Xi’an 710071, China)

A novel multiple-context trust evaluation model, named MCTE, is proposed for social networks to deal with the problem that it is difficult to effectively evaluate indirect trust value between users due to the context sensitivity of trust.A relevance network on top of trust networks is established by taking advantages of the relevant concepts, and through a comprehensive analysis of network structures and user’s trust relationship in each context.Then user’s indirect trust across the context is calculated by using the relevance of context.The Model avoids the effect of the trust attenuation on evaluation and the problem that the trust path between indirect users is difficult to find in multiple context and sparse networks, so that relevance networks of user groups can be built, and the evaluation accuracy and reasonableness are ensured.Experimental results on real social networks shows that the MCTE model can compute the indirect trust value in one single context, and is suitable for the prediction of user’s indirect trust in multiple context.Comparison with an existing model shows that the evaluation accuracy of the proposed model improves a lot.

social networks; trust evaluation; multiple context

2014-10-15。 作者簡介:孟憲佳(1985—),男,博士生;馬建峰(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金資助項目(61174146,61221063)。

時間:2015-03-04

http:∥www.cnki.net/kcms/detail/61.1069.T.20150304.1641.002.html

10.7652/xjtuxb201504012

TP309

A

0253-987X(2015)04-0073-05