基于邊演化的信任鏈時(shí)序預(yù)測模型

孫特點(diǎn)

（上海海事大學(xué)經(jīng)濟(jì)管理學(xué)院,上海 201000）

0 引言

在網(wǎng)絡(luò)交易中，信任和信譽(yù)機(jī)制顯得尤為重要。甘早斌[1]提出了電子商務(wù)下的信任網(wǎng)絡(luò)構(gòu)造與優(yōu)化，通過Visual Studio提供了信任化網(wǎng)絡(luò)的自動(dòng)生成工具，很好地揭示了電商環(huán)境下的信任關(guān)系。莫家慶[2]運(yùn)用改進(jìn)的Einstein算子，給出信上實(shí)體的評估過程。馬堯[3]用多維向量通過買家的記錄構(gòu)建直接信任度，給出了動(dòng)態(tài)環(huán)境下的信任算法。

近年來，鏈路預(yù)測研究方法受到了極大關(guān)注。張豐基于馬氏鏈[4]對信任進(jìn)行了預(yù)測。郭景峰[5]等利用鏈接之間的結(jié)構(gòu)信息引入時(shí)間序列預(yù)測了通信網(wǎng)絡(luò)鏈接。陳莎等人考慮共同鄰居及偏好，基于混合相似性[6]指標(biāo)提高了鏈路預(yù)測的精度。鄧志宏用鏈路預(yù)測誤差[7]描述了網(wǎng)絡(luò)演化趨勢，對鏈路預(yù)測結(jié)果進(jìn)行了修正。許崗等人提出了時(shí)間敏感的機(jī)會(huì)網(wǎng)絡(luò)拓?fù)鋱D[8]預(yù)測方法，結(jié)果表明有較高精度。針對以上成果及問題，本文將在信任網(wǎng)絡(luò)條件下，以時(shí)間序列的歷史信息建立馬爾科夫鏈，預(yù)測下一步的網(wǎng)絡(luò)狀態(tài)。

1 問題描述

在復(fù)雜的企業(yè)社會(huì)網(wǎng)絡(luò)中，企業(yè)之間存在著由兩個(gè)實(shí)體的直接交易形成的直接信任度和通過傳遞或推薦形成的間接信任度所共同構(gòu)成的信任關(guān)系，經(jīng)過組合、交叉等方式將形成由多個(gè)企業(yè)連接而成的有向信任鏈。在實(shí)際的交易過程中，由于環(huán)境的突變通常無法保證鏈路的穩(wěn)定性，例如節(jié)點(diǎn)的移動(dòng)、關(guān)閉及隨機(jī)突發(fā)事件都可能使鏈路拓?fù)涮幱趧?dòng)態(tài)和間歇性局部連通的狀態(tài)，因此節(jié)點(diǎn)之間可能不再保持原有的端到端完整路徑，必須通過移動(dòng)和其他節(jié)點(diǎn)相遇，形成新的信任鏈。為了實(shí)現(xiàn)企業(yè)快速度響應(yīng)信任鏈的變化，減少不必要的損失，提高市場相率，必須建立信任鏈的演化機(jī)制，以圖的模型考察其隨時(shí)間演化的特性。

定義1信任鏈 在企業(yè)網(wǎng)絡(luò)中，信任是用戶關(guān)系維護(hù)的核心，先給出信任鏈的關(guān)鍵元素。（1）信任路徑：在信任網(wǎng)絡(luò)中，從節(jié)點(diǎn)s到節(jié)點(diǎn)t的一條真路為信任路徑，記為ls,t。（2）信任鏈：信任鏈?zhǔn)沁B接節(jié)點(diǎn)的有向關(guān)系鏈，它由一條或者多條信任路徑組成。可以分為原子信任鏈和組合信任鏈。原子信任鏈?zhǔn)遣话虚g節(jié)點(diǎn)的兩個(gè)實(shí)體之間的信任鏈，實(shí)體之間的信任關(guān)系是直接朋友關(guān)系(fd(i,j))。組合信任鏈?zhǔn)侵赣扇舾蓷l原子信任鏈組成包含了多個(gè)連接點(diǎn)的信任鏈，源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的關(guān)系是間接朋友關(guān)系(fid(i,k))。（3）信任度：表示節(jié)點(diǎn)與節(jié)點(diǎn)之間的信任值。如，若l=(s,e1,e2,…,ek,t)為節(jié)點(diǎn)s與節(jié)點(diǎn)t之間的一條路徑，其中為邊ei的建立時(shí)間，信任傳遞的路徑與各邊的建立時(shí)間持續(xù)相關(guān)，因此可為每條邊以其在觀察的時(shí)間段內(nèi)發(fā)生的變化和持續(xù)時(shí)間為權(quán)值構(gòu)造連接圖。

定義2演化網(wǎng)絡(luò) 定義G為由n個(gè)時(shí)間片段組成的演化網(wǎng)絡(luò)，gt表示在時(shí)刻t時(shí)演化網(wǎng)絡(luò)的快照，V(gt)表示gt的節(jié)點(diǎn)集，E(gt)表示gt的邊集。給定一種鏈路預(yù)測方法，就是要對任意節(jié)點(diǎn)對(vx,vy)在下一時(shí)刻產(chǎn)生的新的連邊或者消除已有的連邊的可能性給出一種度量方法，記這種可能性為sxy，時(shí)序鏈路預(yù)測方法可以用一個(gè)映射表示：

其中G'?G是已觀測到的歷史信任鏈路拓?fù)湫畔ⅲ切湃捂溠莼A(yù)測的歷史依據(jù)，S表示連邊的可能性矩陣，反映了對未來鏈路的拓?fù)浣Y(jié)構(gòu)的猜測。

定義3時(shí)間窗 時(shí)間窗n是一個(gè)周期時(shí)間的集合,其中 m 是自然數(shù)集N，通常情況下選擇具有一定規(guī)則的時(shí)間窗。P是一個(gè)周期表達(dá)式，Δt是一個(gè)時(shí)間段，表示作用于p時(shí)間點(diǎn)的上界，下界面。

基于圖的分析模型其著眼點(diǎn)是，即使鏈路演化過程的拓?fù)潆y以預(yù)測，但是可以利用節(jié)點(diǎn)的動(dòng)態(tài)變化過程建立一個(gè)“邊過程”連接圖，該圖包含節(jié)點(diǎn)相遇過程的歷史信息，包括起始時(shí)間和持續(xù)時(shí)間，基于這些信息進(jìn)而判斷下一步的演化結(jié)果。采用離散馬爾科夫模型及生滅過程對信任鏈的拓?fù)溲莼斑叺难莼瘯r(shí)間相關(guān)性進(jìn)行建模。信任鏈的演化過程可以表示為如圖1所示的連續(xù)時(shí)間步上的序列：在t0時(shí)刻，存在狀態(tài)G0，是一條包含了n個(gè)節(jié)點(diǎn)的信任鏈l0，經(jīng)過時(shí)間Δt，與若干個(gè)新的節(jié)點(diǎn)相遇，形成G1所示狀態(tài)的信任鏈l1，再經(jīng)過Δt，某個(gè)節(jié)點(diǎn)消失，新的節(jié)點(diǎn)加入，形成新的信任鏈l2，進(jìn)而給出邊獨(dú)立演化的動(dòng)態(tài)鏈路的演化性質(zhì)。

2 信任鏈時(shí)序預(yù)測模型的建立

2.1 信任網(wǎng)絡(luò)演化圖

信任網(wǎng)絡(luò)關(guān)系拓?fù)渚哂兴脑MG=((V,E),F,L)映射，各元素含義分別為：

（1）V是信任網(wǎng)絡(luò)節(jié)點(diǎn)集為網(wǎng)絡(luò)中節(jié)點(diǎn)vi和節(jié)點(diǎn)vj之間的社會(huì)關(guān)系，其強(qiáng)度為 vi和 vj的信任值 Trust，給出因素集U(U1,U2,…Un)和綜合評判集V(V1,V2…Vn)，對因素集賦予權(quán)重w(w1,w2…wn)，其中w1+w2+…wn=1，因此信任值可以根據(jù)公式（1）計(jì)算：

（3）狀態(tài)分配映射函數(shù)是總節(jié)點(diǎn)數(shù)量，vi為網(wǎng)絡(luò)中的移動(dòng)節(jié)點(diǎn)。

（2）E是信任網(wǎng)絡(luò)邊集，邊集由節(jié)點(diǎn)之間建立信任關(guān)系后表示的連接邊構(gòu)成，將信任值映射為5個(gè)狀態(tài)，描述節(jié)點(diǎn)間信任的強(qiáng)度。

（4）標(biāo)記函數(shù)L(eij)將節(jié)點(diǎn)vi,vj之間的建立的連接命名為邊eij，表示信任關(guān)系的建立。

圖1 連續(xù)時(shí)間步上的信任鏈圖序列

設(shè)為有限離散時(shí)間序列，Gi為時(shí)間間隔信任網(wǎng)絡(luò)的一個(gè)狀態(tài)圖SG={}Gi，則為一個(gè)在時(shí)間區(qū)間上的離散時(shí)間演化圖。

2.2 信任的動(dòng)態(tài)計(jì)算

考慮電子商務(wù)企業(yè)中共享信息的特點(diǎn)，給出因素集U{基本信息，交易量，用戶評價(jià)}，綜合評判集V{完全信任，信任，一般信任，不信任，完全不信任},分別用5.4.3.2.1表示。馬爾科夫轉(zhuǎn)移矩陣中的元素代表著節(jié)點(diǎn)之間的連接邊e從行所代表的信任等級轉(zhuǎn)移到對應(yīng)列所代表的等級的可能性pij。初始狀態(tài)下pij=1/v，本文中v=5。第N次交易后馬爾科夫轉(zhuǎn)移矩陣的元素pN

ij可依據(jù)公式（2）得到：

對于每次交易前計(jì)算出的馬爾科夫矩陣有因此：

2.3 馬爾科夫狀態(tài)轉(zhuǎn)移矩陣的建立

以節(jié)點(diǎn)對之間的社會(huì)關(guān)系變來判斷演化是否符合馬爾科夫鏈，對于個(gè)n節(jié)點(diǎn)構(gòu)成的信任鏈，對節(jié)點(diǎn)對之間的演化序列圖進(jìn)行統(tǒng)計(jì)，經(jīng)過計(jì)算對邊e建立馬爾科夫狀態(tài)轉(zhuǎn)移概率矩陣如下：

且有：

2.4 算法步驟

本文研究信任鏈演化圖模型的計(jì)算過程如下所示：

①給出時(shí)間窗P的劃分范圍。

②將全部的交易的用戶反饋評價(jià)根據(jù)時(shí)間段分類，按公式（1）評估，以獲取該時(shí)間域內(nèi)節(jié)點(diǎn)間的信任值，并分配給狀態(tài)函數(shù)F(eij)。

③根據(jù)前一次的交易評價(jià)建立當(dāng)前狀態(tài)矩陣，由公式（2）獲得信任等級轉(zhuǎn)移概率 pij。信任值Trust和轉(zhuǎn)移概率pij同時(shí)大于設(shè)定閾值即建立連接邊。

④連續(xù)時(shí)間步內(nèi)的一系列狀態(tài)組成一條馬爾科夫鏈，一個(gè)時(shí)刻的狀態(tài)對應(yīng)一個(gè)演化子圖，對節(jié)點(diǎn)間社會(huì)關(guān)系的歷史信息進(jìn)行統(tǒng)計(jì)，建立狀態(tài)轉(zhuǎn)移概率矩陣，結(jié)合公式（3）和公式（4）預(yù)測下一個(gè)時(shí)間片的關(guān)系狀態(tài)。

3 驗(yàn)證與分析

3.1 預(yù)測正確率分析

為了進(jìn)行對比，選取了不同時(shí)間片內(nèi)的預(yù)測結(jié)果，仿真結(jié)果如表1、表2所示。

表1 邊預(yù)測結(jié)果

3.2 算法性能評估

表1為不同時(shí)間片內(nèi)的ROC曲線值，可以看出，仿真的時(shí)間片越長，ROC曲線越接近左上角，擬合效果越好。表2為不同時(shí)間片內(nèi)AUC的值，隨著運(yùn)行時(shí)間的增加，預(yù)測精度也會(huì)提高。

圖2 不同時(shí)間片內(nèi)的ROC曲線

表2 不同時(shí)間片AUC的值

4 結(jié)語

本文在已有的信任值動(dòng)態(tài)計(jì)算的研究成果上，提出了一種基于馬爾科夫時(shí)間序列的鏈路預(yù)測方法，將信任關(guān)系映射為網(wǎng)絡(luò)拓?fù)洌紤]其歷史信息對預(yù)測關(guān)系的影響，相比單純的鏈路預(yù)測問題，將復(fù)雜鏈路賦予了實(shí)際意義；相比信任值的動(dòng)態(tài)計(jì)算問題，將信任轉(zhuǎn)化為了社會(huì)關(guān)系網(wǎng)絡(luò)拓?fù)鋱D，為企業(yè)網(wǎng)絡(luò)的動(dòng)態(tài)合作提供了決策依據(jù)。

[1]甘早斌，曾燦等.電子商務(wù)下的信任網(wǎng)絡(luò)構(gòu)造與優(yōu)化[J].計(jì)算機(jī)學(xué)報(bào)，2012,35（1）：10.3724.

[2]莫家慶，胡忠望等.基于模糊理論的可信計(jì)算信任評估方法研究[J].計(jì)算機(jī)應(yīng)用，2013,33（1）：142-145.

[3]甘早斌，馬堯等.基于信任網(wǎng)絡(luò)的C2C電子商務(wù)信任算法[J].軟件學(xué)報(bào)，2015,26（8）：1946-1959.

[4]張豐，王箭等.基于馬氏鏈的信任預(yù)測算法[J].計(jì)算機(jī)科學(xué)，2014,41（4）：155-158+183.

[5]郭景峰，代軍麗等.針對通信社會(huì)網(wǎng)絡(luò)的時(shí)間序列鏈接預(yù)測算法[J].計(jì)算機(jī)科學(xué)與探索，2010,4（6）：552-559.

[6]陳莎，朱福喜等.一種基于混合相似性指標(biāo)的網(wǎng)絡(luò)動(dòng)態(tài)鏈路預(yù)測方法[J].小型微型計(jì)算機(jī)系統(tǒng)，2016，37.1798-1801.

[7]鄧志宏，老松楊等.基于預(yù)測誤差修正的時(shí)序鏈路預(yù)測方法[J].電子與信息學(xué)報(bào),2014,36（2）：325-331.

[8]許崗，金海和等.時(shí)間敏感的機(jī)會(huì)網(wǎng)絡(luò)社會(huì)關(guān)系拓?fù)溲莼芯縖J].計(jì)算機(jī)科學(xué)與探索.2015,9（16）：1483-1493.