可信網絡的可信模型與算法設計研究

摘 要：分析了網絡環境下信任的特點，總結了目前可信網絡中常用的算法模型，提出了可信度算法中的一些關鍵問題以及解決方法。

關鍵詞：可信網絡；網絡安全；可信度；算法設計

中圖法分類號：TN915.08文獻標識碼：A

文章編號：1001-3695(2007)06-0142-03

0 引言

現代網絡的飛速發展已經使人們越來越多地依賴網絡，個人可以在網絡上聊天交友，許多企業打破時空界限在網絡上尋找商業合作伙伴，一些組織根據網絡投票的結果進行各種獎勵的給予和頒布。實際上，所有這些事情的前提均假定了網絡信息是可信的，也正是因為人們相信了這些網絡上的信息，才導致了許多網絡欺騙、網絡詐騙、網絡犯罪事件的發生。因此，網絡信息的可信性已經引起了信息安全界和電子商務界的高度重視［1－3］。雖然目前網絡系統為了保證系統的安全和可信已經采取了許多措施，諸如加密算法設計、訪問控制、數字簽名、授權可信等，但是當用戶希望與一個遙遠的陌生合作盟友進行網絡交易時，這些技術并不能為用戶提供一個真實的、可信的盟友相關資料，所以網絡上的可信同樣要包括網絡環境下聲明的真實性、合作雙方的安全保證書的可信性以及服務提供者的信譽、可靠性等。建立一個可信網絡，實際上就是建立起一個安全可信的在線社會網絡，網絡用戶之間由信任關系相互連接，當用戶想與網絡的一方進行交易往來時，用戶只需查看客戶的信任等級即可決定自己的行為。顯然，與傳統的信任相比，可信網絡還應該具有如下特點［4］：

（1）表現性——詳細說明了各個方面的可信性；

（2）適應性——用戶能夠自己解釋可信的含義；

（3）規模性——可信用戶可以大規模地擴充；

（4）實用性——信任能夠局部進化和傳遞，因此使得信念的傳遞更為容易。

正是基于可信網絡的上述特點，因此設計一個可信網絡的最基礎的工作就是要設計一個網絡的可信模型以及相關的信任度的算法。雖然可信網絡研究的內容還有很多，如網絡的體系結構、可控制性、可生存性［1］等，但本文將主要從可信網絡的可信模型、信任度計算等方面研究可信網絡。

1 信任屬性

在人類社會中，個人對他人或一件事情的信任與否依賴于許多因素，包括個人的成長經歷、家庭環境及教育背景等。現實社會中的信任是比較復雜的一個概念。一個人是可信的，可能指的是人品可信，也可能指的是他在某一方面的特長可信，因此可信網絡的數據模型必須考慮到可信內容的多種因素，如信任的范圍、信任的程度等。而信任具有的如下特性也成為信任計算中不能不考慮的主要因素。

1.1 信任的非對稱性

現實生活中，許多相互聯系的個體呈現出信任的非對稱性，父母相信孩子的程度遠不及孩子相信父母的程度；雇員相信顧主，但是顧主卻不一定相信雇員。這種在某些個體之間顯現出的信任的不對稱性在現實世界中比比皆是，而且即使是對同一件事情或者是對同一個人，不同的人也會表現出不同的信任度。這主要是個人站在不同的立場和觀點，從不同的利益出發。但是，為了簡化信任網絡的復雜性，在可信網絡中一般假定網絡是對稱的。

1.2 信任的可組合性

由于社會環境中的人們在社交往來、社會溝通渠道上存在著比較大的差異，可能會得到關于一個人的各種各樣的可信度。圖1中假定甲對于乙和丙有相同的信任度，而乙和丙卻得到了對于丁的不同的信任度。這時，當甲需要得到對丁的可信度時，他會有兩種不同的渠道，當乙和丙將各自對丁的信任度反饋給甲時，甲就需要對這兩種信任度進行組合以確定自己對丁的信任度。

1.3 信任的傳遞性

從嚴格的數學意義上講，信任不總是具有傳遞性。這其中主要是考慮到信任的范圍問題，例如，甲信任乙能夠修理汽車，而乙信任丙能夠搞銷售。但是甲不一定就能信任丙能夠搞銷售，因為信任是對某一個特定領域而言的，所以可信網絡下的信任是針對某一特定領域而言的，這樣，一般假定，可信具有傳遞性。由于可信度的推斷將有可能來源于多個信任鏈，而每個信任鏈的有效連接數是一個信任傳遞中需要解決和研究的問題，這種情形恰如圖2描述的情形。當甲沿著乙的信任鏈得到關于己的信任時，信任鏈的數目不能無限地擴張，同樣下一個信任鏈的有效數目可能與上一個不同，但是同樣也有數量的確定，而信任的推斷則需要不同鏈路的信任組合。這些內容在文獻[5－7]中得到了一些研究結果，而迭代次數對于信任度的影響也在文獻[7]中進行了一些實際仿真實驗。

2 計算與進化模型

可信度的推斷是可信網絡研究的重要內容之一，由于可信網絡具有結構上的復雜性，會隨著時間和空間的改變而改變，可信度的計算和進化算法是模型算法的主要研究內容。

2.1 信任度的值域

信任的計算需要對信任度的范圍和信任等級有一個合理的規劃。目前提出的各種各樣的信任等級的劃分方法有：從絕對不信任到絕對信任的九個信任等級的劃分［8］與將信任值定義在［0，1］區間的劃分方式［9］以及將信任等級劃分為信任、不信任和不知道三個層次［10］，也有一些作者將對目的表示為絕對不信任用負值來表示。表1中給出了一些可信網絡采用的可信等級。

2.2 信任度的計算

信任度計算的精確性和適用的廣泛性是衡量一個模型算法的有效標準。目前，在模型的算法設計方面已經取得了一些研究進展。Yu 和Singh 在信任具有對稱性和任意傳遞性的假設下，提出了一個可信網絡的框架和算法［11］；Kamvar等人研究了Peer to Peer環境下的信任傳遞模型［12］；但是他們提出的算法沒有在實際的數據中得到驗證；而Guha等人提出的信任和非可信傳播模型與算法在實際網絡（Epinions.com）中的應用顯示：該算法應用到130 000人的800 000個可信評估數據是有效的，而且在系統中個體對于個體之間表示出的信任和不信任等級也具有較高的準確率［7］。但是，該算法應用的信任的傳遞算法對于迭代次數沒有給出一個理論解釋，這也是目前信任傳遞的一個主要研究內容，即信息的傳遞在傳遞多少次以后信任值將沒有意義。下面介紹幾種典型的信任度算法。2.2.1 基于信任傳遞的簡單迭代法

該基于信任傳遞的簡單迭代法的計算公式表示如下：

Golbeck等人［13］對該算法進行了分析，并在實際的網絡上進行了驗證，表明算法具有較高的準確率。該算法也被應用于一個影評網站中（http://trust.mindswap.org/Filmtrust）， 允許讀者對電影進行等級評定并進行評論，而對于某一部電影，網絡則將具有信任度的人的評論維護在一起。

2.2.2 基于原子傳遞的矩陣迭代法

文獻[7]在計算信任度時，不僅考慮了信任的傳遞模型，同時將不信任的傳遞納入了算法的模型中，并在計算中進行了信任和不信任的有效組合。

該模型算法采用了基于原子傳遞的矩陣迭代法。所謂矩陣，實際上就是由一些介于0和1之間的數值代表的信任度組成的集合，并將信任傳遞總結為四種類型的原子傳遞：

（1）直接傳遞。甲信任乙，乙信任丙，則甲信任丙。

（2）共同引用。甲信任乙和丙，則乙的信任度能夠傳遞給丙。

（3）逆向信任。甲信任乙，則乙的信任度能夠傳遞給甲。

（4）信任耦合。甲和乙都信任丙，則甲的信任度能夠傳遞給乙。

這樣，信任和不信任的傳遞實際上就是以上四種傳遞模型的組合，而傳遞方式為下面三種：

（1）信任。在傳遞過程中只有信任的情形下，可以按照上面的幾種信任進行傳遞。

（2）一步不信任。不信任在傳遞過程中只進行一次，其余步驟按照信任傳遞模型進行。

（3）不信任傳遞。信任和不信任一起組合進行傳遞。

在此基礎上，出了信任度的計算公式：

2.2.3 基于主觀邏輯的迭代計算法

由于可信網絡系統的復雜性，一些學者放棄規范性的網絡研究手段，轉而從主觀邏輯的角度對可信網絡進行了簡化和分析，借用結構化符號對可信傳遞與信任路徑的組合進行了描述，提出進行可信網絡計算的具體步驟如下［14］：

（1）確定可能的路徑，在信任網絡中找到可以計算信任度的路徑；

（2）確定各種路徑的信任度并行組合計算方法的優化；

（3）用主觀邏輯進行信任度的推算。

該模型從統計的觀點給出了可信網絡的簡化方法，即通過主觀邏輯推理與信任并行圖的結合推算出節點的可信度。該方法同時提出了一個可信度加時間的觀點，這種時間可信度對于信任度的作用顯然是非常重要的。

從前面幾種模型和算法設計中可以看出，由于可信網絡的復雜性，研究人員在對模型進行設計時一般都作了假設，這對算法的設計與簡化無疑非常重要，也符合模型和算法設計的基本原則。但是由于可信網絡的種類繁多，信任的范圍廣泛，信任的時間跨度久遠，在可信網絡的可信傳遞和進化算法設計等方面還有待研究和改進：

（1）算法自適應設計方面。

這是任何一種算法都不可回避的問題，因為所有的算法都是在假定信任具有傳遞性下設計的。而現實中即使是遠房親戚的來訪，也有許多人表現出難有的熱情，信任的傳遞在可信網絡中應該有一定數量的限制。

（2）可信網絡的初始數值的設計。

可信值的初始化也是一個需要研究的內容，雖然這些算法中少有提及。實際上，一個人的可信度是經過許多事情逐步形成的，所以人們對自己的可信都十分珍惜，如果可信網絡給的可信度初始值比較高，則其進化給可信度的貢獻就會較小，這也不太符合實際情況。可信度的初始值應該給予合理設計。

（3）可信度的進化計算。可信度是一定時期的產物，不能不看過去，即要從辨證發展的觀點看待一個節點的可信度，比如一個原來可信度較低的企業，經過幾年的臥心嘗膽，企業取得了長足的進步，社會可信度也大大提高。這從網絡的進化中如何體現，即如果將以前得到的可信度和現在的可信度進行加權，雙方占的比例要經過大量的實驗才能確定。

3 結束語

計算機網絡系統過去的研究以追求高效行為為目標，而今天的計算機需要建立高可信的網絡服務，因此，構建一個安全的可信網絡成為人們關注的焦點。網絡不僅關注本身系統和數據的安全，更要關注系統的內容和行為的可信，可信網絡模型和算法設計作為可信網絡研究的重要內容之一。信任的傳遞性、非對稱性等特點使算法設計呈現出一定的復雜性。由于目前這方面的研究也是剛剛開始，本文總結了目前這方面研究的一些進展，進而提出了一些尚需研究和探討的問題。將來的工作包括需要進一步完善算法的理論基礎，并在實踐中檢驗算法的合理性，同時實現跨網絡間的可信度傳遞，為網絡的發展提供一個安全、可信的平臺。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。