基于片段的企業(yè)信任網(wǎng)絡(luò)演化圖聚類算法

盧志剛，解婉婷

(上海海事大學(xué) 經(jīng)濟(jì)管理學(xué)院，上海 201306)(*通信作者電子郵箱575246242@qq.com)

0 引言

在大規(guī)模、開放的網(wǎng)絡(luò)環(huán)境中，企業(yè)由于業(yè)務(wù)行為而產(chǎn)生信任關(guān)系，企業(yè)間的信任關(guān)系可構(gòu)成一個(gè)信任網(wǎng)絡(luò)。由于企業(yè)信任關(guān)系是高度動(dòng)態(tài)的，因此信任網(wǎng)絡(luò)也隨時(shí)間而演變。研究企業(yè)信任網(wǎng)絡(luò)結(jié)構(gòu)隨時(shí)間的演變、發(fā)現(xiàn)網(wǎng)絡(luò)中的隱式社區(qū)[1]、找到內(nèi)部信任關(guān)系穩(wěn)固的信任聯(lián)盟、檢測(cè)聯(lián)盟解散或合并的時(shí)間節(jié)點(diǎn)，可幫助企業(yè)直觀、準(zhǔn)確了解自身所處的動(dòng)態(tài)聯(lián)盟，通過協(xié)同合作取得規(guī)模效益，保持競(jìng)爭(zhēng)活力。

早期關(guān)于信任網(wǎng)絡(luò)的研究主要集中在靜態(tài)網(wǎng)絡(luò)的聯(lián)盟發(fā)現(xiàn)，也涌現(xiàn)出大量方法(基于模塊度優(yōu)化方法[2-3]、基于譜分析方法[4]、基于信息論的模擬退火算法[5]等)。

近些年，關(guān)于信任網(wǎng)絡(luò)的研究集中于動(dòng)態(tài)網(wǎng)絡(luò)的社區(qū)演化，主要分為以下兩類。第一類是基于時(shí)空獨(dú)立評(píng)價(jià)的方法[6-7]，這種方法將網(wǎng)絡(luò)結(jié)構(gòu)劃分和演化評(píng)價(jià)區(qū)分開，用靜態(tài)網(wǎng)絡(luò)發(fā)現(xiàn)算法識(shí)別單時(shí)間快照上的網(wǎng)絡(luò)結(jié)構(gòu)，再對(duì)相鄰時(shí)間的網(wǎng)絡(luò)結(jié)構(gòu)變化進(jìn)行對(duì)比分析，得到網(wǎng)絡(luò)演變信息。另一類是基于時(shí)空集成評(píng)價(jià)的方法，利用短時(shí)平滑性假設(shè)，以相鄰時(shí)間的網(wǎng)絡(luò)結(jié)構(gòu)差異度最小為優(yōu)化目標(biāo)，設(shè)計(jì)動(dòng)態(tài)網(wǎng)絡(luò)劃分算法，包括擴(kuò)展靜態(tài)社區(qū)評(píng)價(jià)體系的方法[8-9]、基于進(jìn)化聚類的方法[10]、基于隱空間的動(dòng)態(tài)網(wǎng)絡(luò)劃分方法[11]等。

以往對(duì)動(dòng)態(tài)信任網(wǎng)絡(luò)的研究基于短時(shí)平滑性假設(shè)，優(yōu)化目標(biāo)通常是發(fā)現(xiàn)核心聯(lián)盟，無法及時(shí)發(fā)現(xiàn)由外部環(huán)境或是網(wǎng)絡(luò)內(nèi)部引發(fā)的聯(lián)盟突變等。本文統(tǒng)籌考慮網(wǎng)絡(luò)演化的短時(shí)平滑性和結(jié)構(gòu)突變的可能，提出基于片段的企業(yè)信任網(wǎng)絡(luò)圖聚類(Graph Clustering, GC)算法，以期發(fā)現(xiàn)一段時(shí)間內(nèi)網(wǎng)絡(luò)演化的穩(wěn)定結(jié)構(gòu)和結(jié)構(gòu)突變的時(shí)間異常點(diǎn)，從而高效發(fā)現(xiàn)聯(lián)盟和跟蹤網(wǎng)絡(luò)。

1 企業(yè)信任網(wǎng)絡(luò)演化

在開放環(huán)境中，處于遠(yuǎn)離平衡態(tài)的企業(yè)信任網(wǎng)絡(luò)在隨機(jī)因素?cái)_動(dòng)(即系統(tǒng)的漲落)的誘發(fā)下，自發(fā)從不穩(wěn)定態(tài)躍遷至一個(gè)新的穩(wěn)定態(tài)[12]。漲落是企業(yè)信任網(wǎng)絡(luò)達(dá)到有序狀態(tài)的根本原因，導(dǎo)致信任網(wǎng)絡(luò)演化重大漲落的因素稱為關(guān)鍵事件。研究企業(yè)信任網(wǎng)絡(luò)演化，就是識(shí)別企業(yè)交互過程中關(guān)鍵事件發(fā)生的時(shí)間點(diǎn)，發(fā)現(xiàn)不同時(shí)間段下信任網(wǎng)絡(luò)的穩(wěn)態(tài)結(jié)構(gòu)?，F(xiàn)采用圖的形式來描述企業(yè)信任網(wǎng)絡(luò)演化，具體如下。

在企業(yè)實(shí)體交互過程中，通常一方為求信方，一方為獲信方，它們之間的信任關(guān)系可形成一個(gè)信任網(wǎng)絡(luò)圖。企業(yè)實(shí)體為網(wǎng)絡(luò)中的頂點(diǎn)，其集合記為V；企業(yè)間信任關(guān)系為網(wǎng)絡(luò)中的邊，其集合記為E。設(shè)企業(yè)信任網(wǎng)絡(luò)頂點(diǎn)集V可分割為兩個(gè)子集{I,J|I∩J=?,I∪J=V}，子集I為求信企業(yè)集合，子集J為獲信企業(yè)集合,則企業(yè)信任網(wǎng)絡(luò)可表示為圖G=(I,J,E)。記企業(yè)實(shí)體ai與bj間的信任關(guān)系為eij，?eij∈E，有ai∈I，bj∈J，故G滿足二分圖結(jié)構(gòu)。

將信任網(wǎng)絡(luò)G轉(zhuǎn)化為二分圖表示，并考慮網(wǎng)絡(luò)演化的時(shí)間信息。設(shè)T={1,2,…,t,…}為時(shí)間戳集合，t是企業(yè)信任網(wǎng)絡(luò)在時(shí)間軸上的唯一標(biāo)識(shí)，則信任網(wǎng)絡(luò)的演化可表示為如圖1所示。時(shí)間戳集合為T={t,t+1,t+2,t+3,t+4}，求信企業(yè)集合為I={a1,a2,a3,a4}，獲信企業(yè)集合為J={b1,b2,b3}，企業(yè)節(jié)點(diǎn)集合I和J不隨時(shí)間變化，信任關(guān)系集合E動(dòng)態(tài)變化，則信任網(wǎng)絡(luò)G隨時(shí)間演化。為反映信任網(wǎng)絡(luò)隨時(shí)間的演化過程，給出如下定義。

定義1 信任網(wǎng)絡(luò)流。設(shè)時(shí)間戳t下的信任網(wǎng)絡(luò)為Gt，則不同時(shí)間戳下企業(yè)信任網(wǎng)絡(luò)的集合稱為信任網(wǎng)絡(luò)流，記為F={G1,G2,…,Gt,…}。

如圖1所示，信任網(wǎng)絡(luò)流為F={Gt,Gt+1,Gt+2,Gt+3,Gt+4}。

圖1 信任網(wǎng)絡(luò)的二分圖描述

為進(jìn)一步描述信任網(wǎng)絡(luò)結(jié)構(gòu)隨時(shí)間的演變，用編碼圖代替二分圖描述信任網(wǎng)絡(luò)，黑色方塊代表企業(yè)間具有信任關(guān)系，白色方塊代表企業(yè)間不具有信任關(guān)系，如圖2所示。對(duì)信任網(wǎng)絡(luò)流進(jìn)行結(jié)構(gòu)劃分，將類型相同的企業(yè)節(jié)點(diǎn)劃分到一個(gè)分組里，結(jié)構(gòu)相同的信任網(wǎng)絡(luò)劃分到一個(gè)片段里，現(xiàn)給出如下定義。

圖2 信任網(wǎng)絡(luò)編碼示意圖

定義5 信任網(wǎng)絡(luò)片段。設(shè)T(s)={ts,ts+1,…,ts+1-1}為第s個(gè)時(shí)間片段，T(s)所對(duì)應(yīng)的信任網(wǎng)絡(luò)集合為F(s)={Gts,Gts+1,…,Gts+1-1}，若?t≠t′∈T(s)，在Gt和Gt′中，有It=It′，Jt=Jt′，即F(s)中每個(gè)信任網(wǎng)絡(luò)的求信企業(yè)分組集合和獲信企業(yè)分組集合相同，則稱F(s)為第s個(gè)信任網(wǎng)絡(luò)片段，ts為關(guān)鍵事件點(diǎn)。記F(s)中求信企業(yè)分組集合為I(s)，獲信企業(yè)分組集合為J(s)，信任聯(lián)盟集合為TR(s)。

如圖2所示，信任網(wǎng)絡(luò)流F中有2個(gè)信任網(wǎng)絡(luò)片段，分別是：F(s)={Gt,Gt+1,Gt+2}，F(xiàn)(s+1)={Gt+3,Gt+4}，t+3為關(guān)鍵事件點(diǎn)。

為了考察企業(yè)信任聯(lián)盟演變機(jī)制，研究企業(yè)信任網(wǎng)絡(luò)演化。通過研究信任網(wǎng)絡(luò)流F的演化結(jié)構(gòu)，識(shí)別關(guān)鍵事件點(diǎn)ts和不同時(shí)間片段下的企業(yè)信任聯(lián)盟的TR(s)，發(fā)現(xiàn)企業(yè)信任聯(lián)盟的穩(wěn)定結(jié)構(gòu)及其變化情況，幫助企業(yè)及時(shí)調(diào)整合作戰(zhàn)略，達(dá)到聯(lián)盟企業(yè)信息共享、資源互補(bǔ)，實(shí)現(xiàn)規(guī)模經(jīng)濟(jì)，最終取得市場(chǎng)、增強(qiáng)競(jìng)爭(zhēng)優(yōu)勢(shì)。

企業(yè)信任網(wǎng)絡(luò)演化問題的研究思路如圖3所示。問題的求解類似于NP-hard問題的求解過程，對(duì)諸多可能解所構(gòu)成的網(wǎng)絡(luò)演化模型進(jìn)行編碼，通過圖聚類算法搜索最優(yōu)解，以達(dá)到發(fā)現(xiàn)企業(yè)信任聯(lián)盟演變機(jī)制的目的。

圖3 企業(yè)信任網(wǎng)絡(luò)演化問題研究思路

2 企業(yè)信任網(wǎng)絡(luò)編碼

將企業(yè)信任網(wǎng)絡(luò)流轉(zhuǎn)化為二進(jìn)制串對(duì)其編碼，構(gòu)建編碼成本函數(shù)以體現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜程度。通過對(duì)企業(yè)進(jìn)行分組來劃分信任網(wǎng)絡(luò)，將結(jié)構(gòu)相同的信任網(wǎng)絡(luò)組成片段，從而壓縮編碼，使編碼成本達(dá)到最小，發(fā)現(xiàn)不同時(shí)間段下信任聯(lián)盟的穩(wěn)定結(jié)構(gòu)。

2.1 信任網(wǎng)絡(luò)編碼與編碼成本

2.1.1 信任網(wǎng)絡(luò)編碼

編碼信任網(wǎng)絡(luò)，即將一個(gè)含有m個(gè)求信企業(yè)和n個(gè)獲信企業(yè)信任網(wǎng)絡(luò)轉(zhuǎn)化為二進(jìn)制串來描述。如圖1中，信任網(wǎng)絡(luò)Gt含4個(gè)求信企業(yè)與3個(gè)獲信企業(yè)，其信任關(guān)系描述為：

其中：“1”表示求信企業(yè)與獲信企業(yè)之間存在信任關(guān)系，“0”表示不具有信任關(guān)系，則該信任網(wǎng)絡(luò)可編碼為110 110 001 001(以行排列)。

由于實(shí)際中，m與n數(shù)值可能較大，直接編碼會(huì)占用大量存儲(chǔ)空間，可采用哈夫曼編碼等標(biāo)準(zhǔn)化無損壓縮方案來編碼，以節(jié)約存儲(chǔ)空間。由此，信任網(wǎng)絡(luò)的編碼長(zhǎng)度可用變?yōu)閙nH(G)，其中H(G)是編碼熵，是對(duì)矩陣中每個(gè)元素最小編碼長(zhǎng)度的估計(jì)：

H(G)=-∑p(x) lbp(x);x∈{0,1}

其中：p(1)=|R|/(mn)，表示信任關(guān)系的密度，|R|為信任關(guān)系總數(shù)(矩陣中1的個(gè)數(shù))。p(0)=1-p(1)。當(dāng)矩陣中元素全為1或全為0時(shí)，信任網(wǎng)絡(luò)結(jié)構(gòu)統(tǒng)一，編碼熵為0。

2.1.2 編碼成本

為了體現(xiàn)信任網(wǎng)絡(luò)結(jié)構(gòu)的耗散程度，可構(gòu)建編碼成本函數(shù)Cg：

Cg=log*|R|+log*m+log*n+mnH(G)

其中，log*表示將整數(shù)轉(zhuǎn)化成二進(jìn)制的通用編碼長(zhǎng)度。有l(wèi)og*x≈lbx+lb lbx+…，每一項(xiàng)分式只保留正整數(shù)位。

編碼成本越大，說明信任網(wǎng)絡(luò)結(jié)構(gòu)越發(fā)散；反之，信任網(wǎng)絡(luò)越統(tǒng)一。

2.2 信任網(wǎng)絡(luò)企業(yè)分組

對(duì)信任網(wǎng)絡(luò)G，可通過對(duì)其m個(gè)求信企業(yè)和n個(gè)獲信企業(yè)進(jìn)行排列組合，將同類型的求信(獲信)企業(yè)組織到同一個(gè)求信(獲信)分組中，把信任網(wǎng)絡(luò)轉(zhuǎn)化成低熵、均勻的網(wǎng)絡(luò)結(jié)構(gòu)，以降低編碼成本。

為此，引入交叉熵的概念來計(jì)算企業(yè)節(jié)點(diǎn)分配到分組的成本[13]。通過比對(duì)不同分配成本來確定企業(yè)的分組歸屬。

以劃分求信企業(yè)為例，假定某一求信企業(yè)ai與l個(gè)獲信分組中的企業(yè)可能有信任關(guān)系。ai與獲信企業(yè)分組的信任關(guān)系服從二項(xiàng)分布P。P為真實(shí)分布，Pq(1)(1≤q≤l)表示ai與第q個(gè)獲信企業(yè)分組的信任關(guān)系密度，則Pq(0)=1-Pq(1)為不信任的關(guān)系密度。

將ai所在的求信企業(yè)分組與獲信企業(yè)分組的信任關(guān)系定義為非真實(shí)分布Q，Q為二項(xiàng)分布，Qq(1)表示該求信企業(yè)分組與第q個(gè)獲信企業(yè)分組之間信任關(guān)系的密度。

則交叉熵反映了該求信企業(yè)與其所在分組內(nèi)其他求信企業(yè)信任關(guān)系分布的相似程度，有：

H(Pq,Qq)=∑Pq(x) lbQq(x);x∈{0,1}

H(Pq,Qq)越小，說明信任關(guān)系分布越相似，表明它們信任同類型的獲信企業(yè)，可分配到同一個(gè)求信分組。

則ai分配到求信分組的編碼成本為：

(1)

同理，對(duì)獲信企業(yè)執(zhí)行類似操作，可得獲信企業(yè)分組。由此，信任網(wǎng)絡(luò)可以根據(jù)求信和獲信企業(yè)的分組情況重新排列，形成新的網(wǎng)絡(luò)結(jié)構(gòu)。如圖2所示，不同時(shí)間戳下的網(wǎng)絡(luò)根據(jù)分組情況劃分出各自的網(wǎng)絡(luò)結(jié)構(gòu)分區(qū)。

2.3 信任網(wǎng)絡(luò)片段編碼

對(duì)信任網(wǎng)絡(luò)流F，可以考察其中不同時(shí)間戳下的信任網(wǎng)絡(luò)結(jié)構(gòu)來發(fā)現(xiàn)信任聯(lián)盟關(guān)系的演變。將時(shí)間相鄰且結(jié)構(gòu)相似的信任網(wǎng)絡(luò)分配到同一個(gè)信任網(wǎng)絡(luò)片段中，則認(rèn)為聯(lián)盟結(jié)構(gòu)較為恒定。由此，通過將信任網(wǎng)絡(luò)劃分到不同信任網(wǎng)絡(luò)片段，可以了解信任網(wǎng)絡(luò)結(jié)構(gòu)隨時(shí)間的變化。

對(duì)網(wǎng)絡(luò)片段F(s)={Gt,Gt+1,…,Gtt+1-1}進(jìn)行編碼，成本函數(shù)由式(2)給出：

C(s)=Be+Bp+Bl+mH(M)+nH(N)+∑Cg

(2)

式(2)相關(guān)函數(shù)項(xiàng)的考慮如下。

1)Be考慮求信企業(yè)和獲信企業(yè)的個(gè)數(shù)m和n。

Be=log*m+log*n

2)Bp考慮求信企業(yè)分組個(gè)數(shù)和獲信企業(yè)分組個(gè)數(shù)k和l。

Bp=log*k+log*l

3)Bl考慮信任網(wǎng)絡(luò)片段中的網(wǎng)絡(luò)個(gè)數(shù)ts+1-ts。

Bl=log*(ts+1-ts)

4)H(M)和H(N)考慮求信企業(yè)分組分配和獲信企業(yè)分組分配編碼熵。

H(M)是求信企業(yè)分組的編碼熵，M是概率為mp/m的多元隨機(jī)變量，mp表示信任網(wǎng)絡(luò)片段下第p個(gè)求信企業(yè)分組的大小，1≤p≤k。同樣，H(N)是獲信企業(yè)分組的編碼熵，N為概率為nq/n的多元隨機(jī)變量，nq為第q個(gè)獲信企業(yè)分組的大小，1≤q≤l。

5)∑Cg考慮信任網(wǎng)絡(luò)片段中不同時(shí)間戳下的信任網(wǎng)絡(luò)編碼總成本。

其中：|Rp,q|表示Fp,q中信任關(guān)系的總數(shù)，|Fp,q|=mpnq(ts+1-ts)，是信任分區(qū)片段的大小。H(Fp,q)是Fp,q中信任關(guān)系的編碼熵，定義如下：

-[γp,qlbγp,q+(1-γp,q) lb (1-γp,q)]

(3)

其中：γp,q=|Rp,q|/|Fp,q|是Fp,q中信任關(guān)系的密度，H(Fp,q)量化了Fp,q結(jié)構(gòu)的耗散程度。編碼熵越小，說明分區(qū)內(nèi)信任關(guān)系越統(tǒng)一；反之，則說明分區(qū)內(nèi)信息關(guān)系越混亂。

2.4 信任網(wǎng)絡(luò)流編碼成本

連續(xù)的信任網(wǎng)絡(luò)片段組成了信任網(wǎng)絡(luò)流，將不同時(shí)間段下的信任網(wǎng)絡(luò)片段編碼成本進(jìn)行累加，得到信任網(wǎng)絡(luò)流的編碼成本C為：

(4)

其中：C(s)是第s個(gè)信任網(wǎng)絡(luò)片段的編碼成本，W為網(wǎng)絡(luò)片段的總數(shù)。

編碼信任網(wǎng)絡(luò)流，通過最小化編碼成本，試圖將信任網(wǎng)絡(luò)分解成同質(zhì)的分區(qū)，即要么接近完全連接(完全信任)，要么完全斷開連接(不存在信任關(guān)系)，從而發(fā)現(xiàn)信任網(wǎng)絡(luò)中關(guān)系穩(wěn)固的信任聯(lián)盟。將信任聯(lián)盟穩(wěn)固的網(wǎng)絡(luò)置于同一片段中，如果聯(lián)盟結(jié)構(gòu)突變，則開始新的片段。對(duì)網(wǎng)絡(luò)流編碼的目標(biāo)是在支持足夠簡(jiǎn)單分解的前提下，充分捕捉信任網(wǎng)絡(luò)結(jié)構(gòu)隨時(shí)間的變化。

3 圖聚類算法

已知信任網(wǎng)絡(luò)流F，通過企業(yè)分組可以重排網(wǎng)絡(luò)結(jié)構(gòu)，找出信任網(wǎng)絡(luò)潛在的分區(qū)，發(fā)現(xiàn)信任關(guān)系密集的信任聯(lián)盟。再將結(jié)構(gòu)相似的網(wǎng)絡(luò)歸入一個(gè)片段中，從而識(shí)別結(jié)構(gòu)異常的關(guān)鍵事件點(diǎn)。

為發(fā)現(xiàn)信任聯(lián)盟的穩(wěn)定結(jié)構(gòu)，識(shí)別網(wǎng)絡(luò)演化中的關(guān)鍵事件點(diǎn)并自動(dòng)劃分時(shí)間窗口，提出圖聚類算法。算法一共有兩步：

1)企業(yè)分組。給定網(wǎng)絡(luò)片段F(s)，將企業(yè)分組至求信企業(yè)分組集合I(s)和獲信企業(yè)分組集合J(s)。

2)網(wǎng)絡(luò)流分割。分割信任網(wǎng)絡(luò)流F，識(shí)別關(guān)鍵事件點(diǎn)ts。

3.1 初始化

開始一個(gè)新的信任網(wǎng)絡(luò)片段，需要初始化分組數(shù)量和分組內(nèi)的企業(yè)分配。針對(duì)不同的情況，提出兩種初始化方案：

1)全新開始，即處理企業(yè)信任網(wǎng)絡(luò)流中第一個(gè)信任網(wǎng)絡(luò)的初始化。通常做法是將求信企業(yè)分組和獲信企業(yè)分組個(gè)數(shù)k和l的初始值設(shè)為m和n，即一個(gè)企業(yè)節(jié)點(diǎn)構(gòu)成一個(gè)分組集合，第一個(gè)信任網(wǎng)絡(luò)構(gòu)成初始信任網(wǎng)絡(luò)片段，再執(zhí)行算法1進(jìn)行最優(yōu)分組搜索。

2)重新開始，即重新開始一個(gè)新信任網(wǎng)絡(luò)片段時(shí)的初始化。時(shí)間連續(xù)的演化網(wǎng)絡(luò)在結(jié)構(gòu)上具有相似性，在搜索過程中利用這種相似性，即開始一個(gè)新片段時(shí)，令求信(獲信)企業(yè)分組數(shù)量為上一個(gè)片段下的求信(獲信)企業(yè)分組數(shù)量，即k(s+1)=k(s)，l(s+1)=l(s)。同樣，也依據(jù)求信企業(yè)分組集合I(s)和獲信企業(yè)分組集合J(s)對(duì)下一個(gè)片段的I(s+1)和J(s+1)進(jìn)行初始化。

3.2 企業(yè)分組

已知信任網(wǎng)絡(luò)片段F(s)，對(duì)求信企業(yè)和獲信企業(yè)進(jìn)行分組。核心思想是遍歷初始分組分配，在調(diào)整分組數(shù)量k和l的同時(shí)，更新求信企業(yè)分組和獲信企業(yè)分組內(nèi)。具體來說，交替執(zhí)行以下兩個(gè)步驟，直到編碼成本達(dá)到最小：

1)更新求信企業(yè)分組。對(duì)于每個(gè)求信企業(yè)，將其分配給產(chǎn)生最小分組成本的求信企業(yè)分組。

2)更新獲信企業(yè)分組。對(duì)于每個(gè)獲信企業(yè)，將其分配給產(chǎn)生最小分組成本的獲信企業(yè)分組。

算法1 企業(yè)分組算法。

Input：信任網(wǎng)絡(luò)片段F(s)，初始企業(yè)分組劃分集合I(s)、J(s)。

Output：更新后的分組劃分集合I(s)、J(s)，信任聯(lián)盟集合TR(s)。

//合并

1)找到求信企業(yè)分組(Ip,Ip′)，滿足Ip,Ip′合并后產(chǎn)生更小的編碼成本。

2)根據(jù)式(2)計(jì)算片段編碼成本，如果總編碼成本下降，則將Ip,Ip′合并。

3)重復(fù)1)～2)步驟，直至結(jié)果不再變化。

//分離

4)遍歷所有求信企業(yè)分組，根據(jù)式(3)找到具有最大平均熵的分組。

5)對(duì)該分組的每個(gè)求信企業(yè)執(zhí)行以下步驟：如果沒有該企業(yè)，分組的平均熵減少，則將該企業(yè)標(biāo)記為分組轉(zhuǎn)移企業(yè)。

//更新

6)對(duì)于每個(gè)分組轉(zhuǎn)移企業(yè)，將其分別歸入到k個(gè)求信分組里，根據(jù)式(1)分別計(jì)算分組分配成本，將其分配給產(chǎn)生最小分組分配成本的求信企業(yè)分組。

7)重復(fù)4)～6)步驟，直至結(jié)果不再變化。

8)以同樣的方法搜索獲信企業(yè)分組，直至結(jié)果不再變化。

//尋找信任聯(lián)盟

9)在求得最佳信任分組劃分方案后，執(zhí)行以下步驟：

11)對(duì)于沒有合并的獲信企業(yè)分組，執(zhí)行上述步驟。

13)對(duì)于沒有合并的求信企業(yè)分組，再執(zhí)行上述步驟。

14)重復(fù)步驟9)～13)，直至所有的求信企業(yè)分組和獲信企業(yè)分組都被分配到信任聯(lián)盟中。

15)輸出信任聯(lián)盟劃分集合TR(s)。

3.3 網(wǎng)絡(luò)流分割

當(dāng)新的信任網(wǎng)絡(luò)到達(dá)時(shí)間軸，通過構(gòu)建信任網(wǎng)絡(luò)片段的增量網(wǎng)絡(luò)來計(jì)算編碼成本。如果新的信任網(wǎng)絡(luò)加入當(dāng)前網(wǎng)絡(luò)片段后會(huì)產(chǎn)生較大的壓縮效益，則算法會(huì)將新的信任網(wǎng)絡(luò)與當(dāng)前信任網(wǎng)絡(luò)片段進(jìn)行壓縮編碼；否則開始一個(gè)新的信任網(wǎng)絡(luò)片段。具體算法如下。

算法2 網(wǎng)絡(luò)流分割算法。

Input：信任網(wǎng)絡(luò)片段F(s)及其編碼成本c0，新的信任網(wǎng)絡(luò)Gt。

Output：更新后的網(wǎng)絡(luò)片段，新的信任分組分配方案I(s)、J(s)。

1)計(jì)算新的信任網(wǎng)絡(luò)Gt歸入片段F(s)后新編碼成本cn。

2)將Gt作為一個(gè)新的網(wǎng)絡(luò)片段，計(jì)算Gt的編碼成本c。

//檢查是否有編碼益處

3)如果c+c0>cn，則將Gt歸于片段F(s)。

4)對(duì)于更新后的片段F(s)執(zhí)行算法1，重新搜索k,l。

5)如果c+c0

6)對(duì)于新的片段F(s+1)執(zhí)行算法1，搜索k,l。

4 實(shí)驗(yàn)仿真

4.1 數(shù)據(jù)集

設(shè)企業(yè)信任網(wǎng)絡(luò)流包含100個(gè)求信企業(yè)，100個(gè)獲信企業(yè)，105個(gè)時(shí)間戳。企業(yè)節(jié)點(diǎn)個(gè)數(shù)不隨時(shí)間改變，企業(yè)間信任關(guān)系隨時(shí)間動(dòng)態(tài)變化。為了方便后續(xù)實(shí)驗(yàn)，對(duì)求信企業(yè)節(jié)點(diǎn)使用1～100進(jìn)行唯一編號(hào)，對(duì)每個(gè)獲信企業(yè)使用101～200進(jìn)行唯一編號(hào)。使用R語言ggplot2包中的Tile plot圖來展現(xiàn)求信企業(yè)和獲信企業(yè)之間的信任關(guān)系，橫坐標(biāo)表示求信企業(yè)節(jié)點(diǎn)，縱坐標(biāo)表示獲信企業(yè)節(jié)點(diǎn)，黑色方塊表示求信企業(yè)與獲信企業(yè)之間存在信任關(guān)系。初始時(shí)刻企業(yè)間信任關(guān)系如圖4所示。

圖4 企業(yè)初始信任網(wǎng)絡(luò)

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

在模擬數(shù)據(jù)集上運(yùn)行GC算法。表1是GC算法對(duì)于企業(yè)信任網(wǎng)絡(luò)流中信任網(wǎng)絡(luò)片段分割和信任聯(lián)盟的發(fā)現(xiàn)結(jié)果。

表1 GC算法運(yùn)行結(jié)果

在表1中，s為對(duì)信任網(wǎng)絡(luò)片段的編號(hào)，GC算法將105個(gè)信任網(wǎng)絡(luò)劃分到9個(gè)網(wǎng)絡(luò)片段中。ave_trust為每個(gè)信任網(wǎng)絡(luò)片段中平均每個(gè)信任網(wǎng)絡(luò)含有信任關(guān)系的數(shù)量，num_graph為每個(gè)信任網(wǎng)絡(luò)片段中信任網(wǎng)絡(luò)的個(gè)數(shù)，num_TR為每個(gè)信任網(wǎng)絡(luò)片段中信任聯(lián)盟的個(gè)數(shù)。

對(duì)于每張信任網(wǎng)絡(luò)，GC算法都能挖掘出網(wǎng)絡(luò)圖的隱藏結(jié)構(gòu)，劃分求信企業(yè)分組和獲信企業(yè)分組，找出信任聯(lián)盟。第一個(gè)信任網(wǎng)絡(luò)片段的信任聯(lián)盟劃分如下：

TR1={1,6,11,12,33,40,43,46,47,52,70,72,79,86,101,104,109,110,124,125,142,149,155,156,158,168,169,173,175,176,177,185,196,197,198}

TR2={2,20,23,24,30,31,32,35,53,59,67,73,87,90,92,103,108,113,114,132,143,145,147,150,151,152,162,165,167,172,174,178,184,186,191}

TR3={3,17,25,26,28,51,55,58,78,80,84,91,93,94,105,123,126,135,141,154,188,193,195}

TR4={4,34,38,39,44,54,68,74,75,102,107,171,179,182,200}

TR5={5,9,10,19,27,36,37,41,56,61,62,63,64,66,69,88,98,106,130,138,153,161,189,192}

TR6={7,18,48,57,60,76,95,96,97,100,111,112,115,116,117,119,122,129,136,137,144,146,160,164,180,181,187,190,199}

TR7={8,13,14,42,82,83,131,133,136,140,148,157,159,163,183,194}

TR8={15,16,21,22,29,45,49,50,65,71,77,81,85,89,99,118,120,121,127,128,134,139,166,170}

為了能在Tile plot圖上清晰展示信任聯(lián)盟的結(jié)構(gòu)，對(duì)企業(yè)節(jié)點(diǎn)重新標(biāo)號(hào)，具體算法如下：在區(qū)分求信企業(yè)和獲信企業(yè)的基礎(chǔ)上，根據(jù)求信企業(yè)分組中企業(yè)節(jié)點(diǎn)的最小標(biāo)號(hào)對(duì)信任聯(lián)盟進(jìn)行排序，按信任聯(lián)盟的順序?qū)η笮牌髽I(yè)依次重新標(biāo)號(hào)，要求同一個(gè)求信企業(yè)分組內(nèi)的企業(yè)節(jié)點(diǎn)擁有相鄰標(biāo)號(hào)。再對(duì)獲信企業(yè)分組中的企業(yè)節(jié)點(diǎn)用相同方法重新標(biāo)號(hào)。對(duì)第一個(gè)信任網(wǎng)絡(luò)片段中的企業(yè)節(jié)點(diǎn)執(zhí)行上述操作，重新標(biāo)號(hào)后，聯(lián)盟劃分如下：

TR1={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120}

TR2={16,17,18,19,20,21,22,23,24,25,26,27,28,29,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168}

TR3={30,31,32,33,34,35,36,37,38,39,40,41,42,43,121,122,123,124,125,126,127,128,129}

TR4={44,45,46,47,48,49,50,51,52,53,54,185,186,187,188,189,190}

TR5={55,56,57,58,59,60,61,62,63,64,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147}

TR6={65,66,67,68,69,70,191,192,193,194,195,196,197,198,199,200}

TR7={71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,176,177,178,179,180,181,182,183,184}

TR8={86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,167,168,169,170,171,172,173,174,175}

使用企業(yè)節(jié)點(diǎn)重新標(biāo)號(hào)后的信任網(wǎng)絡(luò)來繪圖，結(jié)果如圖5所示，企業(yè)信任網(wǎng)絡(luò)結(jié)構(gòu)變得非常清晰。

若采用第一個(gè)信任網(wǎng)絡(luò)片段中的標(biāo)號(hào)方案，繪制第9個(gè)信任網(wǎng)絡(luò)片段中的信任網(wǎng)絡(luò)，結(jié)果如圖6(a)所示，發(fā)現(xiàn)信任網(wǎng)絡(luò)的結(jié)構(gòu)已經(jīng)變得非?；靵y，之前信任聯(lián)盟的邊界變得非常模糊。根據(jù)第9個(gè)信任網(wǎng)絡(luò)片段中信任聯(lián)盟劃分方案對(duì)企業(yè)節(jié)點(diǎn)進(jìn)行標(biāo)號(hào)，重新繪制信任網(wǎng)絡(luò)，如圖6(b)所示。對(duì)比兩個(gè)信任網(wǎng)絡(luò)，可發(fā)現(xiàn)企業(yè)信任聯(lián)盟隨著時(shí)間演變，不斷經(jīng)歷著解散、重組與合并。

4.3 算法有效性對(duì)比

將GC算法與GN(Girvan-Newman)算法、FN(Fast Newman)算法這兩種經(jīng)典算法進(jìn)行對(duì)比。實(shí)驗(yàn)均由Dev-C++實(shí)現(xiàn)，硬件環(huán)境為Intel Core i5- 3230 CPU 2.60 GHz，操作系統(tǒng)為Windows 10。實(shí)驗(yàn)通過在模擬數(shù)據(jù)集上運(yùn)行這3種算法，采用6種經(jīng)典評(píng)價(jià)指標(biāo)來衡量聚類結(jié)果的優(yōu)劣這6種指標(biāo)分別為：純度(purity)、精準(zhǔn)率、召回率、F值、蘭德指數(shù)(Rand Index， RI)、標(biāo)準(zhǔn)化互信息(Normalized Mutual Information， NMI)。

圖5 重編碼后的信任網(wǎng)絡(luò)

圖6 信任網(wǎng)絡(luò)編碼前后對(duì)比

純度的計(jì)算公式為：

purity=cor_num/num

其中：cor_num為正確聚類企業(yè)的個(gè)數(shù)，num為聚類企業(yè)總數(shù)。

精準(zhǔn)率(P)、召回率(R)、F值和蘭德指數(shù)(Rand Index， RI)均采用排列組合原理去評(píng)價(jià)聚類結(jié)果，計(jì)算公式分別式(5)～(8)所示：

(5)

(6)

(7)

(8)

其中：TP(True Positive)指被聚在一類的兩個(gè)企業(yè)被正確聚類了，TN(True Negative)指不應(yīng)該被聚在一類的兩個(gè)企業(yè)被正確分開了，F(xiàn)P(False Positive)指不應(yīng)該被聚在一類的企業(yè)被錯(cuò)誤地聚在了一類，F(xiàn)N(False Negative)指不應(yīng)該分開的企業(yè)被錯(cuò)誤的分開，β為權(quán)重系數(shù)，在下面的實(shí)驗(yàn)中，β取值為1。

標(biāo)準(zhǔn)化互信息(NMI)是信息論中的一種度量[15]，通過熵的形式來衡量聚實(shí)驗(yàn)結(jié)果和標(biāo)準(zhǔn)結(jié)果的重合程度，計(jì)算公式如式(9)所示：

(9)

其中：C和C′分別表示真實(shí)聯(lián)盟標(biāo)簽和算法聚類結(jié)果；H(C)和H(C′)分別表示聯(lián)盟標(biāo)簽和聚類結(jié)果簇大小分布的熵；MI(Mutual Information)為C和C′的交互信息，如式(10)所示：

(10)

上述指標(biāo)從多種角度來衡量實(shí)驗(yàn)結(jié)果與標(biāo)準(zhǔn)結(jié)果之間的差距，取值都在[0,1]區(qū)間，取值越大說明聚類效果越好。若實(shí)驗(yàn)結(jié)果接近標(biāo)準(zhǔn)結(jié)果，則指標(biāo)值接近1；若實(shí)驗(yàn)結(jié)果與標(biāo)準(zhǔn)結(jié)果差之甚遠(yuǎn)，則指標(biāo)值接近0。

用以上6種指標(biāo)綜合衡量3種算法對(duì)企業(yè)信任網(wǎng)絡(luò)的聚類結(jié)果的準(zhǔn)確性，指標(biāo)值對(duì)比表2所示。

表2 3種算法準(zhǔn)確度對(duì)比

通過觀察比較，發(fā)現(xiàn)GC算法的準(zhǔn)確度高于其他算法，說明GC算法的聚類結(jié)果更加接近于企業(yè)真實(shí)信任聯(lián)盟分布情況。

4.4 算法效率分析

采用人工數(shù)據(jù)集進(jìn)行算法性能對(duì)比。每個(gè)時(shí)間戳的人工網(wǎng)絡(luò)包含50個(gè)企業(yè)節(jié)點(diǎn)、200條左右的企業(yè)信任關(guān)系，第一個(gè)時(shí)間片段包含第一個(gè)時(shí)間戳的企業(yè)信任關(guān)系數(shù)據(jù)，第二個(gè)時(shí)間片段包含前兩個(gè)時(shí)間戳的企業(yè)信任關(guān)系數(shù)據(jù)，以此類推。

用3種算法處理這8個(gè)時(shí)間片段，分別記錄不同算法處理每個(gè)時(shí)間片段所用的時(shí)長(zhǎng)，來比較算法在計(jì)算效率上的性能優(yōu)劣。實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 3種算法計(jì)算時(shí)間對(duì)比

結(jié)果發(fā)現(xiàn)，隨著信任網(wǎng)絡(luò)快照的更新，GN算法與FN算法均采用“全新處理”的方式，無法通過相鄰網(wǎng)絡(luò)結(jié)構(gòu)的相似性實(shí)現(xiàn)快速處理，因此，在小規(guī)模網(wǎng)絡(luò)中，這兩種算法的處理時(shí)間與數(shù)據(jù)量成正比，運(yùn)算效率均低于GC算法。而GC算法基于信息論計(jì)算，時(shí)間復(fù)雜度減小，從而縮短計(jì)算時(shí)間。除此之外，GC算法利用相鄰網(wǎng)絡(luò)結(jié)構(gòu)的相似性，實(shí)現(xiàn)算法性能上的增益。如圖7所示，隨著數(shù)據(jù)量的增多，GC算法的處理時(shí)間并沒有顯著上升。當(dāng)?shù)?個(gè)網(wǎng)絡(luò)快照到達(dá)的時(shí)候，GC算法檢測(cè)出信任網(wǎng)絡(luò)結(jié)構(gòu)的突變，重新計(jì)算企業(yè)信任分組，處理時(shí)間增多，將第6個(gè)時(shí)間戳標(biāo)記為一個(gè)關(guān)鍵事件點(diǎn)，與預(yù)期相符。

該實(shí)驗(yàn)說明在處理隨時(shí)間動(dòng)態(tài)變化的信任網(wǎng)絡(luò)流時(shí)，GC算法更具有性能上的優(yōu)勢(shì)，可以快速識(shí)別信任聯(lián)盟和檢測(cè)網(wǎng)絡(luò)結(jié)構(gòu)突變的關(guān)鍵事件點(diǎn)。

5 結(jié)語

發(fā)現(xiàn)企業(yè)信任聯(lián)盟的穩(wěn)定結(jié)構(gòu)及其變化，揭示企業(yè)信任聯(lián)盟演變機(jī)制，是企業(yè)聯(lián)盟合作的核心問題。本文對(duì)信任網(wǎng)絡(luò)流進(jìn)行編碼，構(gòu)建編碼成本函數(shù)來反映網(wǎng)絡(luò)流結(jié)構(gòu)復(fù)雜度，通過圖聚類(GC)算法搜索最優(yōu)結(jié)構(gòu)劃分方案以劃分時(shí)間片段和信任分區(qū)，從而找到不同時(shí)間段下的信任聯(lián)盟。不同于其他算法，GC算法不需要用戶定義的任何參數(shù)，是完全自動(dòng)的。而且，該算法適用于動(dòng)態(tài)流式環(huán)境，隨著不斷到達(dá)的信任網(wǎng)絡(luò)快照，GC算法可以高效跟蹤動(dòng)態(tài)信任網(wǎng)絡(luò)，自動(dòng)識(shí)別信任聯(lián)盟的穩(wěn)定結(jié)構(gòu)和聯(lián)盟結(jié)構(gòu)突變的時(shí)間戳，發(fā)現(xiàn)企業(yè)信任聯(lián)盟的演變過程。最后，通過對(duì)電商信任網(wǎng)絡(luò)模擬數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，發(fā)現(xiàn)GC算法能自動(dòng)挖掘出有意義的信任聯(lián)盟，并識(shí)別出網(wǎng)絡(luò)結(jié)構(gòu)突變的關(guān)鍵事件點(diǎn)。在與經(jīng)典社區(qū)發(fā)現(xiàn)算法進(jìn)行性能對(duì)比時(shí)，發(fā)現(xiàn)GC算法的準(zhǔn)確性和運(yùn)行效率方面均優(yōu)于經(jīng)典算法。

References)

[1] 王莉,程學(xué)旗.在線社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)社區(qū)發(fā)現(xiàn)及演化[J].計(jì)算機(jī)學(xué)報(bào),2015,38(2):219-237.(WANG L, CHENG X Q. Dynamic community in online social networks [J]. Chinese Journal of Computers, 2015, 38(2): 219-237.)

[2] BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large networks [J]. Journal of Statistical Mechanics Theory & Experiment, 2008(10): 155-168.

[3] KARRER B, NEWMAN M E J. Stochastic blockmodels and community structure in networks [J]. Physical Review E: Statistical Nonlinear & Soft Matter Physics, 2010, 83(2): 016107.

[4] CAPOCCI A, SERVEDIO V D P, CALDARELLI G, et al. Detecting communities in large networks [J]. Physica A: Statistical Mechanics & Its Applications, 2005, 352(2/3/4): 669-676.

[5] LANCICHINETTI A, FORTUNATO S. Community detection algorithms: a comparative analysis [J]. Physical Review E: Statistical Nonlinear & Soft Matter Physics, 2009, 80(5): 056117.

[6] CSHEN H, CHENG X, CAI K, et al. Detect overlapping and hierarchical community structure in networks [J]. Physica A: Statistical Mechanics & Its Applications, 2009, 388(8): 1706-1712.

[7] 張學(xué)武,沈浩東,趙沛然,等.基于事件框架的社區(qū)進(jìn)化預(yù)測(cè)研究[J].計(jì)算機(jī)學(xué)報(bào),2017,40(3):729-742.(ZHANG X W, SHEN H D, ZHAO P R, et al. Research on community evolution prediction based on event-based frameworks [J]. Chinese Journal of Computers, 2017, 40(3): 729-742.)

[8] BASSETT D S, PORTER M A, WYMBS N F, et al. Robust detection of dynamic community structure in networks [J]. Chaos, 2013, 23(1): 013142.

[9] MUCHA P J, RICHARDSON T, MACON K, et al. Community structure in time-dependent, multiscale, and multiplex networks [J]. Science, 2010, 328(5980): 876-878.

[10] LIN Y, CHI Y, ZHU S, et al. FacetNet: a framework for analyzing communities and their evolutions in dynamic networks [C]// Proceedings of the 17th International Conference on World Wide Web. New York: ACM, 2008: 685-694.

[11] SARKAR P, MOORE A W. Dynamic social network analysis using latent space models [J]. ACM SIGKDD Explorations Newsletter, 2005, 7(2): 31-40.

[12] 成全,焦玉英,陸泉,等.基于耗散結(jié)構(gòu)理論的Wiki社區(qū)交流動(dòng)力機(jī)制研究[J].圖書情報(bào)工作,2008,52(11):62-65.(CHENG Q, JIAO Y Y, LU Q, et al. Dynamic mechanisms of communication in Wiki community based on the dissipative structure theory [J]. Library and Information Service, 2008, 52(11): 62-65.)

[13] 查日軍,張德平,聶長(zhǎng)海,等.組合測(cè)試數(shù)據(jù)生成的交叉熵與粒子群算法及比較[J].計(jì)算機(jī)學(xué)報(bào),2010,33(10):1896-1908.(ZHA R J, ZHANG D P, NIE C H, et al. Test data generation algorithms of combinatorial testing and comparison based on cross-entropy and particle swarm optimization method [J]. Chinese Journal of Computers, 2010, 33(10): 1896-1908.)

[14] 馮健,丁媛媛.基于重疊社區(qū)和結(jié)構(gòu)洞度的社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)洞識(shí)別算法[J].計(jì)算機(jī)工程與科學(xué),2016,38(5):898-904.(FENG J, DING Y Y. A structural hole identification algorithm in social networks based on overlapping communities and structural hole degree [J]. Computer Engineering and Science, 2016, 38(5): 898-904.)

[15] WU J, XIONG H, CHEN J. Adapting the right measures forK-means clustering [C]// Proceedings of the 2009 ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2009: 877-886.

This work is partially supported by the Basic Research Project of Shanghai (15590501800).

LUZhigang, born in 1973, Ph. D., professor. His research interests include business intelligence, supply chain optimization.

XIEWanting, born in 1994, M. S. candidate. Her research interests include information management, e-commerce.