基于重疊社區發現的信任網絡聚類模型

劉夢霞 盧志剛

(上海海事大學經濟管理學院 上海 201306)

0 引 言

信任網絡由電子商務交易企業之間的信任關系形成。在電子商務信任關系中，用復雜的網絡節點和邊表示企業間的相互聯系，建立信任網絡模型[1]。企業信任網絡存在某些關鍵企業連接多個聯盟，這就允許社區間存在重疊現象。發現信任網絡中存在的具有重疊性的社區結構，有助于企業找到穩定的信任聯盟，從而降低交易風險。

國內外學者主要從兩個方面研究重疊社區。1) 基于節點劃分的方法。將節點作為考慮對象，根據某種策略選擇節點，形成初始社區，然后不斷擴展社區，獲得社區結構。包括CONGA算法[2]、基于局部擴展的方法LFM[3]、派系過濾算法CPM[4]等。CONGA算法[2]是對GN算法的改進，分裂最高介數的節點，再用GN算法進行社區劃分，對分裂節點進行合并。這些方法大都需要先驗知識，比如社區數目。邊信息對社區結構影響較大，但這些方法沒有考慮邊信息。2) 基于邊劃分的方法。網絡中的節點用邊表示，邊用節點表示，將初始網絡轉換成邊網絡，然后在邊網絡上應用社區發現算法，得到社區結構。LINK[5]算法先聚類邊集得到邊的社區，再把邊的社區轉換為對應節點的社區,類似的算法還包括[6-7]等 。LINK[5]算法把全部的邊劃分到社區中，邊的弱連接使社區間產生高度重疊。Kim等[7]用信息論的方法改進LINK算法，仍然無法有效識別網絡中的孤立邊。

現有的重疊社區發現算法大都處理無向無權的網絡，常見的度數、介數等指標未考慮節點間的連接強度，不能適用于大規模的信任網絡。相比無權復雜網絡，加權復雜網絡更能體現實際情況。本文考慮邊的權重，用劃分節點的方法，分析企業間存在的信任關系，提出一種基于節點權重的重疊社區發現算法CDNW來處理加權無向網絡圖，尋找企業信任網絡的信任聯盟和關鍵企業。

1 問題描述

在電子商務交易中，企業之間的信任關系構成信任網絡。在網絡中企業選擇合作伙伴聯盟，進行長期合作和資源共享。對掌握著差異化資源的關鍵企業，其他企業為提升自身創新能力會選擇與關鍵企業合作[8]。通過在信任網絡中劃分出聯盟和關鍵企業，可以幫助企業制定下一步的合作戰略。如圖1所示。

圖1 信任網絡模型

設企業間的信任關系構成一個信任網絡。如圖1(a)所示，信任網絡用加權的網絡圖G=(V,E,T)表示。用節點vi表示企業實體，其集合記作V。用邊ei j表示企業實體間的信任關系，其集合記為E。其中ei j表示節點vi和節點vj間的信任關系。邊權重trij表示企業間的信任強度，其集合記為T。

通過分析信任網絡的結構特征，發現信任網絡的社區和重疊節點，找到信任聯盟Ci和關鍵企業K，可幫助企業制定長期的合作戰略。

2 信任網絡聚類模型

為找出企業聯盟和關鍵企業，用社區發現的方法將信任網絡中的聚類問題建模，建立一種基于節點權重的信任網絡聚類模型。本質上節點與社區的聯系可以由節點之間的距離反映，但在信任網絡中節點之間的距離由不同強度的信任關系表示。根據節點之間的信任值，設置網絡中每個節點的權重，劃分節點到社區。確定社區之間的重疊程度以及節點與社區的關聯度，以優化社區。

2.1 重疊社區發現

設信任網絡可抽象為一張包含節點和連邊的圖，社區是圖的一個子圖，用來表示網絡中存在的“社區中的節點緊密相連，社區間節點聯系稀疏”的密集子圖[9]。尋找網絡中存在的相交的社區結構的過程稱為重疊社區發現，其實質是劃分網絡中的節點為多個可相交的子集。

分析重疊社區劃分的結果，有助于認識真實網絡結構特性和個體行為趨勢的分析。

企業信任聯盟總圍繞那些規模大、資源多的企業形成，要尋找企業聯盟要先找到中心企業。因此信任網絡的社區劃分要先根據信任值來設定節點的權重。節點的權重表示企業被選為中心企業的概率。初始社區從權重最大的節點開始尋找。

遍歷網絡中的節點，并把當前遍歷的節點看成中心節點，以此節點和其所有鄰接節點構成的網絡(記為社區Cvi)來設定節點的權重。節點vi的權重表示該節點被選擇為中心節點的概率，并以社區相對密度denvi來衡量。

節點vi的鄰居節點集合Uvi是與節點vi有邊相連的全部節點的集合，即Uvi=vj∈Vvi,vj∈E。

社區Cvi相對密度：

(1)

社區相對密度表示節點vi與鄰居節點的平均連接強度denvi，在[0,1]區間取值，它決定了節點的度和節點的鄰接節點數量之間的相關性。denvi的值表示vi所能形成的聯盟的規模。但僅僅靠社區相對密度的指標，只考慮網絡中邊權重的因素，所得到的社區具有較低的平均相似度。因此引入社區緊密度的概念，考慮網絡的結構特征。

社區Cvi的網絡聚集系數netvi：

(2)

式中：ecvi是社區Cvi的邊數;n是社區Cvi中的節點數;n(n-1)/2是社區全連通時的邊數。

社區Cvi中節點vi的鄰居節點的數量等于連接節點vi的邊數Uvi=n。社區緊密度與網絡聚集系數netvi以及vi的鄰居數量呈正相關關系。

社區Cvi緊密度：

comvi=netvi×Uvi

(3)

(4)

社區緊密度comvi是指相鄰節點之間的連接密度，在[0,1]區間取值。如果僅僅考慮網絡結構特征來設定節點權重會導致社區密度大的中心節點權重大。

節點的權重應由式(1)和式(4)共同設定，根據denvi和comvi對節點的不同影響程度來設置ξ的值。定義為：

wvi=ξ(denvi,comvi)

(5)

2.2 重疊社區優化

企業聯盟中存在某些聯盟重合度較高，為了整合資源和信息，對聯盟進行合并。因此，社區的優化先計算初始社區之間的重疊系數，根據系數合并社區。

2.2.1 重疊系數分析

重疊系數是社區劃分的指標，用于衡量社區之間的重疊程度。初始重疊系數定義為任意兩個社區中公共節點數與總節點數之比：

(6)

式中：Ci和Cj是兩個社區。式(6)在處理兩社區節點個數相差過大的情況下，不能準確反映社區之間的重疊程度。新的重疊系數[10]定義為：

(7)

式中：Ci∩Cj表示社區之間的公共節點數；Min(Ci,Cj)表示節點數最少的社區。δ(Ci,Cj)取值在[0,1]區間，當Ci∩Cj=φ，δ(Ci,Cj)取值為0；當Ci?Cj或Ci?Cj，δ(Ci,Cj)取值為1；式(7)能更準確反映社區的重疊程度。

優化社區時，合并重疊系數大于規定閾值δ(Ci,Cj)≥T的社區。調整結束后得到的重疊節點K是企業聯盟中的關鍵企業，掌握著豐富的信息資源。

2.2.2 關聯度分析

社區合并后，某些企業成員難以適應新的伙伴加入，將會主動解除聯盟并尋找新的合作聯盟。

引入關聯度指標來識別這些節點，并從社區中刪除節點并分配新社區。如果移除節點有一半以上的鄰居位于某個社區，則將它加入這個社區。

關聯度β(μ,C)[11]定義為：

(8)

關聯度描述節點μ隸屬于社區C的程度。若節點μ的全部相連節點都包含在社區C中，則β(μ,C)=1，即節點μ僅屬于社區C；否則β(μ,C)<1，即節點μ屬于多個社區。

遍歷合并社區的節點，刪除關聯程度低于規定閾值β(μ,C)<ε的節點。

3 基于節點權重的重疊社區發現算法

在節點劃分的方法中，基于局部擴展思想的種子選取策略應用最廣泛，但也存在一些不足。比如LFM[3]算法對種子節點的隨機選擇，使發現的社區結構不合理。GCE[12]算法選取最大團的結構作為初始種子節點，團結構的特殊性會使很多節點沒有社區歸屬。

考慮到社區結構的合理性，提出新的CDNW算法。改進種子選取策略，把無權圖中依據節點的度選取種子，轉變為加權圖中依據節點權重選取種子。新算法的基本設計思路：使用改進的種子選擇方法來劃分網絡得到社區。再根據社區間的重疊度，優化調整初始社區。

3.1 社區劃分

初始社區劃分由節點權重來確定節點遍歷的順序，當前遍歷的社區當作中心節點，并把該節點的鄰接節點加入，循環直到被標記的節點全覆蓋網絡時結束。

算法1基于節點權重的社區劃分算法

輸入：節點，邊，邊的權重。

輸出：社區集合C1,C2,…,Cm。

步驟1計算網絡中節點的權重wvi，降序排列節點，記節點的序列為L。

步驟2選擇L中最大權重的節點vi，確定vi是否滿足中心節點的條件：

(1) ifvi未標記else ifvi已標記&&vi有未標記的鄰接節點then轉到步驟3。

(2) else continue。

步驟3建立社區Cvi:

(1)vi為社區的中心節點。

(2) 將vi的所有相鄰節點加入社區，從序列L中刪除vi。

步驟4重復上述操作，直到被標記節點全覆蓋網絡。

3.2 社區調整

對任意的兩社區計算重疊系數δ(Ci,Cj)，合并δ(Ci,Cj)≥T的社區。對于社區在合并過程中出現個別節點不適應新社區的情況，在合并的社區中移除關聯度β(u,C)小于閾值的節點，對移除節點采取重新分配社區。

算法2基于重疊系數和關聯度的社區調整算法

輸入：社區集合C1,C2,…,Cm，閾值T，ε。

步驟1對任意兩社區Ci和Cj計算重疊系數δ(Ci,Cj)。

步驟2當δ(Ci,Cj)大于閾值T(通常取0.7)時，合并Ci和Cj為一個社區。

步驟3對于合并社區中的每個節點u，計算關聯度β(u,C)，將β(u,C)<ε(通常取0.5)的節點從社區移除，每移除一個節點，重新計算剩余節點的關聯度，直到?u∈c,β(u,C)≥ε。

步驟4當所有的重疊系數δ(Ci,Cj)都小于閾值T時，調整結束，否則返回步驟1繼續循環。

步驟5遍歷社區，將沒有分配社區的節點，分配給包含其相鄰節點最多的社區。若存在兩社區包含的相鄰節點數相同，選擇相鄰節點的權重之和最大的社區。

4 實驗及結果分析

實驗采用LFR基準程序隨機生成的2類數據集來驗證算法的準確性和有效性：(1) 小規模人工數據集；(2) 大規模人工數據集。在小規模的人工數據集上，詳細展示企業形成信任聯盟的過程。在大規模人工數據集中，選擇兩種代表性的聚類算法，LFM算法和GN算法進行比較。實驗結果用NMI指標進行評價。實驗環境：處理器為Intel?CoreTMi5-3337U CPU，主頻為1.80 GHz，內存為4 GB，操作系統為Windows7。算法使用JAVA語言編程實現。

4.1 小規模人工數據集

企業信任網絡數據通過模擬生成，隨機選取企業實體的數量。圖2描述的是初始的企業信任網絡，包含73個企業，以及73個企業相互合作形成的229條信任關系。

圖2 初始的信任網絡

圖3是算法劃分后的企業信任網絡。企業用節點表示，并且相同顏色的節點形成社區。不同顏色的社區表示企業間不同的聯盟。圖中的73個企業，被算法劃分成8個社區。社區分別為：

C1={〗1,11,12,13,18,27,31,56,70}；

C2={2,4,14,39,41,60,65}；

C3={5,7,24,34,37,48,67}；

C4={15,20,21,28,42,43,45,52,55,57,72}；

C5={3,9,23,30,32,47,50,53,54,61,64,73}；

C6={6,8,10,16,33,40,49,62}；

C7={19,22,26,35,46,58,59,63,69,70,71}；

C8={17,25,29,36,38,44,51,58,59,66,68,69}。

圖3 劃分后的企業網絡

在圖3中，節點權重較大的是社區的中心節點。這些通常是規模大，資源豐富的企業，信任聯盟主要圍繞這些節點形成。

規模小且相對資源較少的企業在與其他企業合作時無法掌握主動權，選擇聯盟伙伴較謹慎，一般只加入一個或兩個聯盟。聯盟減少了企業的機會主義行為以及由于企業合作伙伴選擇不當導致的解散風險。社區之間有不同程度的重疊。節點54、58、59、69、70是重疊節點。

重疊處的企業往往是網絡中的關鍵企業K，這些企業能夠進行更多的信息交流以及擁有豐富的資源。大多數企業更愿意選擇重疊處的企業進行聯盟，能獲得更多的資金和技術支持來進行產品創新。然而重疊處的企業長期面對來自多個聯盟中不確定性的共同影響，若無法有效整合資源并充分利用，很難維系長期的合作。

4.2 大規模人工數據集

LFR是Lancichinetti等[3]提出的基準網絡，用于檢測社區發現算法。它通過算法模擬真實網絡產生的網絡數據集，通過設定參數產生不同類型的網絡。LFR基準網絡具有已知的標準社區結構，互信息NMI可用于評估社區發現算法的準確性。基準網絡的具體參數如表1所示。

表1 LFR基準網絡參數說明

為評價各個算法在不同的社區結構下劃分社區的質量，采用4個標準的數據集對算法進行比較。根據社區的大小和邊的密度的差異，選取四種類型的網絡：稀疏網絡小社區(SS)，稀疏網絡大社區(SL),稠密網絡小社區(DS),稠密網絡大社區(DL)。參數設置如表2所示。

表2 LFR基準網絡參數說明

在每種類型的網絡中，改變混合參數μ的大小，從0.1開始以步長0.1逐漸增加到0.9。圖4-圖7顯示了在四個網絡上運行的三種算法的結果。橫坐標是混合參數μ，縱坐標是衡量算法劃分質量的標準互信息NMI。

圖4 SS網絡下算法的NMI對比

圖5 SL網絡下算法的NMI對比

圖6 DS網絡下算法的NMI對比

圖7 DL網絡下算法的NMI對比

從圖4-圖7的結果可以看出，三種算法的準確度隨著參數μ的增加而減小。混合參數越接近1，社區的結構特征越不明顯，算法得到的社區質量越差。另外，從三個算法NMI值急劇下降的走勢分析，LFM和GN算法均存在較大的局限性，對μ的參數變化太敏感。GN算法能準確識別社區但無法識別重疊節點導致其正確率最低。LFM算法在μ<0.4的情況下，識別重疊社區的準確度在三個算法中最高。但隨著μ越來越大，LFM算法劃分結果得到越來越多的孤立節點，孤立節點是不利于社區結構的。GN算法和LFM算法在μ>0.4的情況下，劃分出的社區數量不斷減少，其中初始網絡是它的一個劃分。此時GN算法和LFM算法不能發現有意義的社區。

CDNW算法在NMI指標上優于GN算法，次于LFM算法。它基于企業信任進行社區劃分，形成的企業信任聯盟不易過大，企業選擇聯盟的伙伴數量適量。否則更高的網絡密度將導致企業間聯系冗余，資源不集中。

在算法的適用性上，CDNW對μ的適用范圍更大，適用于更普遍的社區結構。尤其當社區結構不明顯時，仍然能劃分出較多規模較小的社區。說明當企業所處的市場環境高度不確定時，企業之間形成的聯盟依然存在，只是聯盟規模有所降低。在四種不同特性的大規模人工網絡中，CDNW算法在處理社區結構不明顯的數據集時表現出較好的劃分能力，且具有一定的穩定性。

5 結 語

在本文中，根據企業信任網絡的特點，利用節點權重來描述企業節點之間的信任關系。建立基于重疊社區的信任網絡聚類模型，對信任聯盟和關鍵企業進行劃分。基于節點權重的重疊社區發現算法(CDNW)根據節點權重劃分初始社區；使用重疊系數來合并具有較高重疊度的社區；用節點對社區的關聯度指標調整合并的社區，得到信任網絡的聚類結果。實驗在大規模人工的網絡上進行，與LFM算法和GN算法進行對比。實驗結果表明，CDNW算法可以找到企業信任聯盟和關鍵企業，并且找到的社區結構更符合真實網絡結構。此外，它具有更好的劃分社區結構不明顯的數據集的能力。在模型中，如果引入更全面的真實網絡數據，實驗結果可能更加符合現實情況。未來的工作將使用更多的真實網絡進行實驗，選擇更合理的實驗參數。算法并沒有考慮企業因市場環境變化而發生的聯盟變化問題。下一步將研究時序變化下的企業動態社區演化問題，并致力于提高算法的效率。

參考文獻

[1] 張少中, 方朝曦, 陳軍敢,等. 基于社會網絡的電子商務信任社區聚類模型[J]. 浙江大學學報(工學版), 2013, 47(4):656-661.

[2] Gregory S. An Algorithm to Find Overlapping Community Structure in Networks[C]// European Conference on Principles and Practice of Knowledge Discovery in Databases. Springer-Verlag, 2007:91-102.

[3] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure of complex networks[J]. New Journal of Physics, 2008, 11(3):19-44.

[4] Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043):814-818.

[5] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multiscale complexity in networks[J]. Nature, 2009, 466(7307):761-764.

[6] Evans T S, Lambiotte R. Line graphs, link partitions, and overlapping communities[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2009, 80(1Pt2):016105.

[7] Kim Y, Jeong H. Map equation for link communities[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2011, 84(2):026110.

[8] Krackhardt D. Structural Holes: The Social Structure of Competition[J]. Administrative Science Quarterly, 1995.

[9] Girvan M, Newman M E. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12):7821.

[10] Pan L, Dai C, Wang C, et al. Overlapping Community Detection via Leader-Based Local Expansion in Social Networks[C]// IEEE, International Conference on TOOLS with Artificial Intelligence. IEEE, 2012:397-404.

[11] Chen D, Shang M, Lv Z, et al. Detecting overlapping communities of weighted networks via a local algorithm[J]. Physica A Statistical Mechanics & Its Applications, 2010, 389(19):4177-4187.

[12] Lee C, Reid F, Mcdaid A, et al. Detecting highly overlapping community structure by greedy clique expansion[C]// Proc of the 4th Int Workshop on Social Network Mining and Analysis(SNNKDD′10),New York:ACM,2010:33-42.