基于片段的企業信任網絡演化圖聚類算法

盧志剛，解婉婷

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

0 引言

在大規模、開放的網絡環境中，企業由于業務行為而產生信任關系，企業間的信任關系可構成一個信任網絡。由于企業信任關系是高度動態的，因此信任網絡也隨時間而演變。研究企業信任網絡結構隨時間的演變、發現網絡中的隱式社區[1]、找到內部信任關系穩固的信任聯盟、檢測聯盟解散或合并的時間節點，可幫助企業直觀、準確了解自身所處的動態聯盟，通過協同合作取得規模效益，保持競爭活力。

早期關于信任網絡的研究主要集中在靜態網絡的聯盟發現，也涌現出大量方法(基于模塊度優化方法[2-3]、基于譜分析方法[4]、基于信息論的模擬退火算法[5]等)。

近些年，關于信任網絡的研究集中于動態網絡的社區演化，主要分為以下兩類。第一類是基于時空獨立評價的方法[6-7]，這種方法將網絡結構劃分和演化評價區分開，用靜態網絡發現算法識別單時間快照上的網絡結構，再對相鄰時間的網絡結構變化進行對比分析，得到網絡演變信息。另一類是基于時空集成評價的方法，利用短時平滑性假設，以相鄰時間的網絡結構差異度最小為優化目標，設計動態網絡劃分算法，包括擴展靜態社區評價體系的方法[8-9]、基于進化聚類的方法[10]、基于隱空間的動態網絡劃分方法[11]等。

以往對動態信任網絡的研究基于短時平滑性假設，優化目標通常是發現核心聯盟，無法及時發現由外部環境或是網絡內部引發的聯盟突變等。本文統籌考慮網絡演化的短時平滑性和結構突變的可能，提出基于片段的企業信任網絡圖聚類(Graph Clustering, GC)算法，以期發現一段時間內網絡演化的穩定結構和結構突變的時間異常點，從而高效發現聯盟和跟蹤網絡。

1 企業信任網絡演化

在開放環境中，處于遠離平衡態的企業信任網絡在隨機因素擾動(即系統的漲落)的誘發下，自發從不穩定態躍遷至一個新的穩定態[12]。漲落是企業信任網絡達到有序狀態的根本原因，導致信任網絡演化重大漲落的因素稱為關鍵事件。研究企業信任網絡演化，就是識別企業交互過程中關鍵事件發生的時間點，發現不同時間段下信任網絡的穩態結構?，F采用圖的形式來描述企業信任網絡演化，具體如下。

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

將信任網絡G轉化為二分圖表示，并考慮網絡演化的時間信息。設T={1,2,…,t,…}為時間戳集合，t是企業信任網絡在時間軸上的唯一標識，則信任網絡的演化可表示為如圖1所示。時間戳集合為T={t,t+1,t+2,t+3,t+4}，求信企業集合為I={a1,a2,a3,a4}，獲信企業集合為J={b1,b2,b3}，企業節點集合I和J不隨時間變化，信任關系集合E動態變化，則信任網絡G隨時間演化。為反映信任網絡隨時間的演化過程，給出如下定義。

定義1 信任網絡流。設時間戳t下的信任網絡為Gt，則不同時間戳下企業信任網絡的集合稱為信任網絡流，記為F={G1,G2,…,Gt,…}。

如圖1所示，信任網絡流為F={Gt,Gt+1,Gt+2,Gt+3,Gt+4}。

圖1 信任網絡的二分圖描述

為進一步描述信任網絡結構隨時間的演變，用編碼圖代替二分圖描述信任網絡，黑色方塊代表企業間具有信任關系，白色方塊代表企業間不具有信任關系，如圖2所示。對信任網絡流進行結構劃分，將類型相同的企業節點劃分到一個分組里，結構相同的信任網絡劃分到一個片段里，現給出如下定義。

圖2 信任網絡編碼示意圖

定義5 信任網絡片段。設T(s)={ts,ts+1,…,ts+1-1}為第s個時間片段，T(s)所對應的信任網絡集合為F(s)={Gts,Gts+1,…,Gts+1-1}，若?t≠t′∈T(s)，在Gt和Gt′中，有It=It′，Jt=Jt′，即F(s)中每個信任網絡的求信企業分組集合和獲信企業分組集合相同，則稱F(s)為第s個信任網絡片段，ts為關鍵事件點。記F(s)中求信企業分組集合為I(s)，獲信企業分組集合為J(s)，信任聯盟集合為TR(s)。

如圖2所示，信任網絡流F中有2個信任網絡片段，分別是：F(s)={Gt,Gt+1,Gt+2}，F(s+1)={Gt+3,Gt+4}，t+3為關鍵事件點。

為了考察企業信任聯盟演變機制，研究企業信任網絡演化。通過研究信任網絡流F的演化結構，識別關鍵事件點ts和不同時間片段下的企業信任聯盟的TR(s)，發現企業信任聯盟的穩定結構及其變化情況，幫助企業及時調整合作戰略，達到聯盟企業信息共享、資源互補，實現規模經濟，最終取得市場、增強競爭優勢。

企業信任網絡演化問題的研究思路如圖3所示。問題的求解類似于NP-hard問題的求解過程，對諸多可能解所構成的網絡演化模型進行編碼，通過圖聚類算法搜索最優解，以達到發現企業信任聯盟演變機制的目的。

圖3 企業信任網絡演化問題研究思路

2 企業信任網絡編碼

將企業信任網絡流轉化為二進制串對其編碼，構建編碼成本函數以體現網絡結構的復雜程度。通過對企業進行分組來劃分信任網絡，將結構相同的信任網絡組成片段，從而壓縮編碼，使編碼成本達到最小，發現不同時間段下信任聯盟的穩定結構。

2.1 信任網絡編碼與編碼成本

2.1.1 信任網絡編碼

編碼信任網絡，即將一個含有m個求信企業和n個獲信企業信任網絡轉化為二進制串來描述。如圖1中，信任網絡Gt含4個求信企業與3個獲信企業，其信任關系描述為：

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

由于實際中，m與n數值可能較大，直接編碼會占用大量存儲空間，可采用哈夫曼編碼等標準化無損壓縮方案來編碼，以節約存儲空間。由此，信任網絡的編碼長度可用變為mnH(G)，其中H(G)是編碼熵，是對矩陣中每個元素最小編碼長度的估計：

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

其中：p(1)=|R|/(mn)，表示信任關系的密度，|R|為信任關系總數(矩陣中1的個數)。p(0)=1-p(1)。當矩陣中元素全為1或全為0時，信任網絡結構統一，編碼熵為0。

2.1.2 編碼成本

為了體現信任網絡結構的耗散程度，可構建編碼成本函數Cg：

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

其中，log*表示將整數轉化成二進制的通用編碼長度。有log*x≈lbx+lb lbx+…，每一項分式只保留正整數位。

編碼成本越大，說明信任網絡結構越發散；反之，信任網絡越統一。

2.2 信任網絡企業分組

對信任網絡G，可通過對其m個求信企業和n個獲信企業進行排列組合，將同類型的求信(獲信)企業組織到同一個求信(獲信)分組中，把信任網絡轉化成低熵、均勻的網絡結構，以降低編碼成本。

為此，引入交叉熵的概念來計算企業節點分配到分組的成本[13]。通過比對不同分配成本來確定企業的分組歸屬。

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

將ai所在的求信企業分組與獲信企業分組的信任關系定義為非真實分布Q，Q為二項分布，Qq(1)表示該求信企業分組與第q個獲信企業分組之間信任關系的密度。

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

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

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

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

(1)

同理，對獲信企業執行類似操作，可得獲信企業分組。由此，信任網絡可以根據求信和獲信企業的分組情況重新排列，形成新的網絡結構。如圖2所示，不同時間戳下的網絡根據分組情況劃分出各自的網絡結構分區。

2.3 信任網絡片段編碼

對信任網絡流F，可以考察其中不同時間戳下的信任網絡結構來發現信任聯盟關系的演變。將時間相鄰且結構相似的信任網絡分配到同一個信任網絡片段中，則認為聯盟結構較為恒定。由此，通過將信任網絡劃分到不同信任網絡片段，可以了解信任網絡結構隨時間的變化。

對網絡片段F(s)={Gt,Gt+1,…,Gtt+1-1}進行編碼，成本函數由式(2)給出：

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

(2)

式(2)相關函數項的考慮如下。

1)Be考慮求信企業和獲信企業的個數m和n。

Be=log*m+log*n

2)Bp考慮求信企業分組個數和獲信企業分組個數k和l。

Bp=log*k+log*l

3)Bl考慮信任網絡片段中的網絡個數ts+1-ts。

Bl=log*(ts+1-ts)

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

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

5)∑Cg考慮信任網絡片段中不同時間戳下的信任網絡編碼總成本。

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

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

(3)

其中：γp,q=|Rp,q|/|Fp,q|是Fp,q中信任關系的密度，H(Fp,q)量化了Fp,q結構的耗散程度。編碼熵越小，說明分區內信任關系越統一；反之，則說明分區內信息關系越混亂。

2.4 信任網絡流編碼成本

連續的信任網絡片段組成了信任網絡流，將不同時間段下的信任網絡片段編碼成本進行累加，得到信任網絡流的編碼成本C為：

(4)

其中：C(s)是第s個信任網絡片段的編碼成本，W為網絡片段的總數。

編碼信任網絡流，通過最小化編碼成本，試圖將信任網絡分解成同質的分區，即要么接近完全連接(完全信任)，要么完全斷開連接(不存在信任關系)，從而發現信任網絡中關系穩固的信任聯盟。將信任聯盟穩固的網絡置于同一片段中，如果聯盟結構突變，則開始新的片段。對網絡流編碼的目標是在支持足夠簡單分解的前提下，充分捕捉信任網絡結構隨時間的變化。

3 圖聚類算法

已知信任網絡流F，通過企業分組可以重排網絡結構，找出信任網絡潛在的分區，發現信任關系密集的信任聯盟。再將結構相似的網絡歸入一個片段中，從而識別結構異常的關鍵事件點。

為發現信任聯盟的穩定結構，識別網絡演化中的關鍵事件點并自動劃分時間窗口，提出圖聚類算法。算法一共有兩步：

1)企業分組。給定網絡片段F(s)，將企業分組至求信企業分組集合I(s)和獲信企業分組集合J(s)。

2)網絡流分割。分割信任網絡流F，識別關鍵事件點ts。

3.1 初始化

開始一個新的信任網絡片段，需要初始化分組數量和分組內的企業分配。針對不同的情況，提出兩種初始化方案：

1)全新開始，即處理企業信任網絡流中第一個信任網絡的初始化。通常做法是將求信企業分組和獲信企業分組個數k和l的初始值設為m和n，即一個企業節點構成一個分組集合，第一個信任網絡構成初始信任網絡片段，再執行算法1進行最優分組搜索。

2)重新開始，即重新開始一個新信任網絡片段時的初始化。時間連續的演化網絡在結構上具有相似性，在搜索過程中利用這種相似性，即開始一個新片段時，令求信(獲信)企業分組數量為上一個片段下的求信(獲信)企業分組數量，即k(s+1)=k(s)，l(s+1)=l(s)。同樣，也依據求信企業分組集合I(s)和獲信企業分組集合J(s)對下一個片段的I(s+1)和J(s+1)進行初始化。

3.2 企業分組

已知信任網絡片段F(s)，對求信企業和獲信企業進行分組。核心思想是遍歷初始分組分配，在調整分組數量k和l的同時，更新求信企業分組和獲信企業分組內。具體來說，交替執行以下兩個步驟，直到編碼成本達到最?。?/p>

1)更新求信企業分組。對于每個求信企業，將其分配給產生最小分組成本的求信企業分組。

2)更新獲信企業分組。對于每個獲信企業，將其分配給產生最小分組成本的獲信企業分組。

算法1 企業分組算法。

Input：信任網絡片段F(s)，初始企業分組劃分集合I(s)、J(s)。

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

//合并

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

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

3)重復1)～2)步驟，直至結果不再變化。

//分離

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

5)對該分組的每個求信企業執行以下步驟：如果沒有該企業，分組的平均熵減少，則將該企業標記為分組轉移企業。

//更新

6)對于每個分組轉移企業，將其分別歸入到k個求信分組里，根據式(1)分別計算分組分配成本，將其分配給產生最小分組分配成本的求信企業分組。

7)重復4)～6)步驟，直至結果不再變化。

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

//尋找信任聯盟

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

11)對于沒有合并的獲信企業分組，執行上述步驟。

13)對于沒有合并的求信企業分組，再執行上述步驟。

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

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

3.3 網絡流分割

當新的信任網絡到達時間軸，通過構建信任網絡片段的增量網絡來計算編碼成本。如果新的信任網絡加入當前網絡片段后會產生較大的壓縮效益，則算法會將新的信任網絡與當前信任網絡片段進行壓縮編碼；否則開始一個新的信任網絡片段。具體算法如下。

算法2 網絡流分割算法。

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

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

1)計算新的信任網絡Gt歸入片段F(s)后新編碼成本cn。

2)將Gt作為一個新的網絡片段，計算Gt的編碼成本c。

//檢查是否有編碼益處

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

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

5)如果c+c0

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

4 實驗仿真

4.1 數據集

設企業信任網絡流包含100個求信企業，100個獲信企業，105個時間戳。企業節點個數不隨時間改變，企業間信任關系隨時間動態變化。為了方便后續實驗，對求信企業節點使用1～100進行唯一編號，對每個獲信企業使用101～200進行唯一編號。使用R語言ggplot2包中的Tile plot圖來展現求信企業和獲信企業之間的信任關系，橫坐標表示求信企業節點，縱坐標表示獲信企業節點，黑色方塊表示求信企業與獲信企業之間存在信任關系。初始時刻企業間信任關系如圖4所示。

圖4 企業初始信任網絡

4.2 實驗結果

在模擬數據集上運行GC算法。表1是GC算法對于企業信任網絡流中信任網絡片段分割和信任聯盟的發現結果。

表1 GC算法運行結果

在表1中，s為對信任網絡片段的編號，GC算法將105個信任網絡劃分到9個網絡片段中。ave_trust為每個信任網絡片段中平均每個信任網絡含有信任關系的數量，num_graph為每個信任網絡片段中信任網絡的個數，num_TR為每個信任網絡片段中信任聯盟的個數。

對于每張信任網絡，GC算法都能挖掘出網絡圖的隱藏結構，劃分求信企業分組和獲信企業分組，找出信任聯盟。第一個信任網絡片段的信任聯盟劃分如下：

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圖上清晰展示信任聯盟的結構，對企業節點重新標號，具體算法如下：在區分求信企業和獲信企業的基礎上，根據求信企業分組中企業節點的最小標號對信任聯盟進行排序，按信任聯盟的順序對求信企業依次重新標號，要求同一個求信企業分組內的企業節點擁有相鄰標號。再對獲信企業分組中的企業節點用相同方法重新標號。對第一個信任網絡片段中的企業節點執行上述操作，重新標號后，聯盟劃分如下：

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}

使用企業節點重新標號后的信任網絡來繪圖，結果如圖5所示，企業信任網絡結構變得非常清晰。

若采用第一個信任網絡片段中的標號方案，繪制第9個信任網絡片段中的信任網絡，結果如圖6(a)所示，發現信任網絡的結構已經變得非?；靵y，之前信任聯盟的邊界變得非常模糊。根據第9個信任網絡片段中信任聯盟劃分方案對企業節點進行標號，重新繪制信任網絡，如圖6(b)所示。對比兩個信任網絡，可發現企業信任聯盟隨著時間演變，不斷經歷著解散、重組與合并。

4.3 算法有效性對比

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

圖5 重編碼后的信任網絡

圖6 信任網絡編碼前后對比

純度的計算公式為：

purity=cor_num/num

其中：cor_num為正確聚類企業的個數，num為聚類企業總數。

精準率(P)、召回率(R)、F值和蘭德指數(Rand Index， RI)均采用排列組合原理去評價聚類結果，計算公式分別式(5)～(8)所示：

(5)

(6)

(7)

(8)

其中：TP(True Positive)指被聚在一類的兩個企業被正確聚類了，TN(True Negative)指不應該被聚在一類的兩個企業被正確分開了，FP(False Positive)指不應該被聚在一類的企業被錯誤地聚在了一類，FN(False Negative)指不應該分開的企業被錯誤的分開，β為權重系數，在下面的實驗中，β取值為1。

標準化互信息(NMI)是信息論中的一種度量[15]，通過熵的形式來衡量聚實驗結果和標準結果的重合程度，計算公式如式(9)所示：

(9)

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

(10)

上述指標從多種角度來衡量實驗結果與標準結果之間的差距，取值都在[0,1]區間，取值越大說明聚類效果越好。若實驗結果接近標準結果，則指標值接近1；若實驗結果與標準結果差之甚遠，則指標值接近0。

用以上6種指標綜合衡量3種算法對企業信任網絡的聚類結果的準確性，指標值對比表2所示。

表2 3種算法準確度對比

通過觀察比較，發現GC算法的準確度高于其他算法，說明GC算法的聚類結果更加接近于企業真實信任聯盟分布情況。

4.4 算法效率分析

采用人工數據集進行算法性能對比。每個時間戳的人工網絡包含50個企業節點、200條左右的企業信任關系，第一個時間片段包含第一個時間戳的企業信任關系數據，第二個時間片段包含前兩個時間戳的企業信任關系數據，以此類推。

用3種算法處理這8個時間片段，分別記錄不同算法處理每個時間片段所用的時長，來比較算法在計算效率上的性能優劣。實驗結果如圖7所示。

圖7 3種算法計算時間對比

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

該實驗說明在處理隨時間動態變化的信任網絡流時，GC算法更具有性能上的優勢，可以快速識別信任聯盟和檢測網絡結構突變的關鍵事件點。

5 結語

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

References)

[1] 王莉,程學旗.在線社會網絡的動態社區發現及演化[J].計算機學報,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] 張學武,沈浩東,趙沛然,等.基于事件框架的社區進化預測研究[J].計算機學報,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] 成全,焦玉英,陸泉,等.基于耗散結構理論的Wiki社區交流動力機制研究[J].圖書情報工作,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] 查日軍,張德平,聶長海,等.組合測試數據生成的交叉熵與粒子群算法及比較[J].計算機學報,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] 馮健,丁媛媛.基于重疊社區和結構洞度的社會網絡結構洞識別算法[J].計算機工程與科學,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.