基于張量建模和進化K均值聚類的社區檢測方法

陳吉成，陳鴻昶

（信息工程大學信息技術研究所，鄭州 450002）

0 引言

社區檢測（Community Detection，CD）［1］是分析復雜網絡的重要工具，其目的是發現強凝聚性群體，此類群體中成員彼此之間的聯系比網絡中其他參與者的聯系更加緊密，由此提取出的社區具有重要統計價值，應用范圍包括語義網本體構建［2］、標簽系統中的話題檢測［3］、個性化搜索和推薦［4］等。

異構網絡中的社區檢測與傳統社區檢測方法稍有不同。傳統社區檢測方法大多僅考慮一種關系，而多關系網絡中的CD 則需要對不同關系上的交互進行整合，并基于不同參與者之間的不同關系，發現共同的底層隱藏社區結構。目前這方面的研究已經有一些研究成果。文獻［5］中針對一維網絡的傳統CD方法的統一定義，提出了一種基于上下文信息的社區檢測（Contextual Information-based Community Detection，CICD）方法，并基于此，嘗試將單關系網絡中的CD 方法擴展到多關系網絡；但該方法假定不同關系彼此獨立，且忽視了關系和參與者的雙向影響。文獻［6］將CD問題建模為一個單目標優化問題，提出了一種基于Memetic 的方法，通過優化模糊度評價指標檢測復雜網絡中的重疊社區結構，并使用“一致續存”度量來修改給定的非重疊社區結構。與之類似，文獻［7］中提出了一種改進的蟻群算法重疊社區發現方法，采用局部擴展的社區識別方法。文獻［8］方法根據關系分配不同權重，反映出網絡中每種關系的不同重要程度。此外，根據關系的概率性權重，將多關系網絡轉換為單關系網絡，應用CD方法，以揭示參與者的社區隸屬度。也有研究者提出了局部譜聚類（Local Spectral Clustering，LSC）［9］和基于聚類融合［10］的方法。聚類融合或共識聚類方法主要應用于單關系網絡，其在網絡不同視圖上應用聚類方法得到多個聚類結果，并在此基礎上找到共享的共識社區結構。

由于矩陣和張量分解已成為復雜網絡分析的重要工具，因此這方面也有很多應用。如：文獻［11］中提出了多張量分解方法，從表示多關系數據的超圖中提取社區，合并來自多個圖的信息。文獻［12］中提出了基于平行因子（PARAllel FACtors，PARAFAC）張量分解的多圖聚類方法，利用系數隱性因子來確定實體的社區軟隸屬度。文獻［13］中提出了基于特征和關系信息的所有相關矩陣的聯合分解的譜框架，以揭示不同類型對象之間的隱藏社區結構。

針對包含同類實體之間異構交互的多關系網絡，為進行多關系網絡建模，本文使用了三階鄰接張量，張量的每個切片表示與參與者之間一種類型的關系相對應的鄰接矩陣。應用張量分解作為關系學習工具，可以揭示參與者的唯一隱性表征。本文的主要工作在于：1）提出了用于多關系網絡表征的基于張量的模型；2）開發了使用非負張量分解和基于遺傳算法（Genetic Algorithm，GA）的K均值的社區檢測框架。實驗結果表明所提方法具有較好的性能。

1 多關系網絡中的社區檢測

本文多關系網絡社區檢測的流程如圖1 所示，利用RESCAL 張量分解和GA-K均值聚類在多關系網絡中進行社區檢測。為了在學習方法中考慮到數據的關系特性，本文使用張量對多關系網絡進行建模。下面對圖1 各個重要環節進行介紹。

圖1 本文方法的流程Fig.1 Flow chart of proposed method

1.1 多關系網絡建模

一個張量可被定義為一個多模數組或一個多維矩陣。一個張量的維數（變量）稱為階、向或模。向量是由一個下標標識的單向張量；矩陣則是具有二維（行和列）的雙向張量。同理，還有更高階的張量。張量纖維是張量的一維片段，類似于矩陣的行或列。張量切片是張量的二維截面（片段），類似于矩陣。本文使用下標小寫字母表示張量或矩陣的一個元素（例如xijk為三階張量X的ijk元素），A?B和表示逐元素矩陣乘法或除法。

采用三階張量X，將實體間的二元關系建模為一個張量。該三階張量中，兩個模由域的實體構成，第三個模則保持著關系。張量的每個frontal 切片表示與多關系網絡的一種關系相對應的鄰接矩陣。給定一個多關系網絡MNet={Ai|1≤i≤m}，其中包含以m種類型的關系{R1，R2，…，Rm}彼此關聯的n個實體的集合{E1，E2，…，En}，則創建出一個大小為n×n×m的三階張量，其中每個frontal 切片i對應于關系的鄰接矩陣Ai。張量條目xijk=1表示第i個實體與第j個實體以第k種關系彼此關聯。而對于不存在關系和未知關系，該條目被設為0。表征為三階張量的多關系網絡如圖2所示。其中，E1，E2，…，En表示實體，R1，R2，…，Rm表示關系。

圖2 多關系數據的張量模型Fig.2 Tensor model of multiple relational data

1.2 利用張量分解揭示隱性特征

將多關系網絡建模為張量是非負的，當且僅當在因子分解上施加了非負約束時，相應的隱性分量才具有物理意義。因此，應采用非負的稀疏因子分解。本文提出的方法中應用了RESCAL分解［14］，與其他非負張量分解（Non-negative Tensor Factorization，NTF）方法相比，RESCAL 分解能夠捕捉學習過程中的全局相依性，支持不受知識庫大小影響的快速查詢訪問。RESCAL 中，實體通過隱性空間唯一表示。而在其他張量分解方法中，例如CP 和Tucker［15］，則根據實體是構成關系中的主體還是對象，存在兩種不同的實體隱性表征。RESCAL 分解方法具有高度擴展性，可有效應用到大規模關系數據上。

1.3 RESCAL分解

RESCAL 是關系學習的隱性因子模型，它將鄰接矩陣X∈Rn×n×m分解為一個單因子矩陣F∈Rn×r和一個核心張量R∈Rr×r×m：

式中：r為用戶給定的分解的秩；×1和×2分別表示模1和模2的積；E為近似相關誤差矩陣。式（1）的展開形式等價為式（2）：

式中：Rk和Xk分別表示R和X的第k個frontal切片，k取小于等于m的正整數。式（1）～（2）中，X的每個元素xijk近似為Rk fj，其中fi，fj∈Rr為F的第i行和第j行。RESCAL 分解如圖3 所示。圖3 中，灰色單元表示條目xijk，第i個和第j個纖維對應于第i個和第j個實體的隱性因子。

圖3 RESCAL分解示意圖Fig.3 Schematic diagram of RESCAL decomposition

該模型中，F的行fi對應第i個實體的隱性表征，張量R的frontal 切片Rk則對第k種關系的隱性變量的交互進行建模。由此，F是包含實體隱性表征的矩陣，R為隱性分量與謂詞的交互。

1.4 RESCAL分解計算

為執行RESCAL分解，需要求解以下優化問題：

假定因子分解的秩值r和正則化參數(λF≥0，λR≥0)為已知。利用任何隨機矩陣對F和Rk進行初始化，或從)的特征分解中對F進行初始化。為計算因子矩陣和核心張量的非負更新，該方法利用式（4）～（5）對F和所有Rk（張量R的第k個切片，最大切片數目為kmax）進行交替更新，直至式（3）中目標函數的相對變化收斂至一些較小閾值或達到最大迭代次數。

在該步驟中，使用RESCAL 分解對表示多關系網絡的張量進行因子分解。該步驟的結果為矩陣F∈Rn×r，其中，n為總條目數，r為因子分解的秩。由于F中包含低維嵌入實體的唯一性表征，可應用聚類方法對F實施聚類以發現不同的社區。

1.5 使用GA-K均值算法進行社區檢測

聚類技術是識別實體集合中內在組織的非監督式技術。K均值算法是廣泛使用的聚類技術，但其存在兩個缺陷：1）陷入局部最優；2）結果的準確度取決于初始聚類中心。

遺傳算法是為尋找全局最優解而設計的隨機搜索技術［16］。提出的方法中，應用遺傳算法作為優化工具，以得到用于K均值聚類算法的最優初始種子。對因子分解的結果（隱性因子矩陣F）應用GA-K均值算法［17］，以得到期望的社區。采用基于GA 方法的原因是該方法在問題空間中執行全局搜索，且便于混雜和擴展，以適應多種問題結構。

GA-K均值聚類算法包含以下三個步驟：

步驟1 隨機生成染色體的初始種群。每個染色體包含K個初始種子，其中K為要形成的聚類數。

步驟2 對每個染色體進行解碼，得到初始種子。利用這些初始種子，執行K均值聚類。其后，計算出適應度函數值。

步驟3 在當前種群上執行遺傳操作，以生成新一代種群。迭代該過程，直至滿足停止標準。提出的方法中，若適應度在連續5次迭代中未得到改善，則終止算法。

1.6 遺傳表征和種群初始化

染色體的長度取決于因子分解的秩和要形成的聚類數。若因子分解的秩為r，聚類數為K，則每個染色體的長度為K×r。矩陣F的每行fi均唯一地表征第i個實體。染色體包含矩陣F的隨機選定的K行。圖4（a）給出了K=5、r=3的一個染色體，初始種群為隨機生成。

1.7 適應度函數的計算

對于種群中的每個染色體，必須測量該染色體的質量，也就是測量該染色體所表征的可能解的適應度。此處使用的適應度函數為聚類間散布矩陣與聚類內散布矩陣的跡比。由此，本文要求解的優化問題為該函數的最大化，即創建出能夠最大化類內相似度和最小化類間相似度的聚類。對于第k個聚類，散布矩陣Sk定義為：

式中：μk為屬于第k個聚類Ck的數據點的平均向量。類內散布矩陣SW表示所有聚類的散度之和，其計算式為：

類間散布矩陣SB計算式為：

式中：Nk為屬于第k個聚類的數據點數量；μk為第k個聚類的平均向量。混合參數向量μ可計算為：

其中，混合參數向量μ表示社區間和社區內的邊的比率，μ的元素數值越低，表示社區質量越高。將類間散布矩陣和類內散布矩陣的跡比取作適應度函數。目標是最大化以下比率fobj：

式中：Tr（）表示求跡運算符。

1.8 新種群的生成

確定了問題編碼的染色體，并選擇合適的適應度函數后，可以應用各種遺傳算子（例如選擇、交叉、變異）開始解的進化。使用這些算子，迭代生成新代的解，直至達到收斂標準。下面將討論研究中使用的選擇、交叉和變異算子。

1）選擇算子。該算子從種群中選擇要應用遺傳交叉的染色體。本文使用的選擇方法為輪盤賭選擇法。該方法也稱為適應度比例選擇，根據染色體的適應度數值來選擇染色體。

2）交叉算子。選擇后，在染色體上應用交叉算子以得到更好的后代。本文研究中使用了均勻交叉算子和改進的全算術算子。

在均勻交叉中，取兩個父染色體P1 和P2，并隨機生成一個二進制mask。取mask 中為1 的第一個父染色體的聚類中心和mask 為0 的第二個父染色體的聚類中心，填充第一個子染色體的聚類中心；取mask 中為0 的第一個父染色體的聚類中心與mask 為1 的第二個父染色體的聚類中心，填充第二個子染色體的聚類中心。圖4（b）展示了對兩個以mask 編碼的父染色體應用均勻交叉算子，生成兩個子染色體的樣例。

算術算子線性地合并兩個父染色體，根據以下計算式生成新染色體：

式中，a為隨機選定的加權因子。本文對算術交叉算子進行了調整，以適應本文的問題定義。在改進全算術算子中，使用一個mask 以選擇要應用算術算子的染色體聚類中心。圖4（c）給出了a=0.7時的改進全算術算子的樣例。

3）變異算子。變異算子在種群中引入多樣性，確保利用整個搜索空間。交叉算子在兩個父染色體上操作，變異算子則通過改變一個或少數幾個性狀，對染色體進行局部修改。本文使用的實值均勻變異算子是針對本文應用而設計的，因為在RESCAL 分解后獲得隱形分量矩陣，其元素都是實數值，實值均勻變異算子是按實數值變異，再對標記的離散量進行四舍五入，均勻變異以較小的均等概率替換原有基因，波動較小，在聚類中心的下限和上限范圍之間選擇任意隨機值。在染色體的該聚類中心內，將基因數值替換為選擇的隨機值。變異操作如圖4所示。

圖4 染色體表征與遺傳算子Fig.4 Chromosome representation and genetic operator

所提出的多關系網絡中的社區發現方法主要步驟如下：

步驟1 給定一個包含n個實體以及實體間m類關系的多關系網絡，創建一個大小為n×n×m的三階張量。

步驟2 在構建的張量上應用RESCAL 張量分解，其中r為因子分解的秩。該步驟得到的結果為包含實體的唯一性表征的因子矩陣F∈Rn×r。

步驟3 對因子矩陣F應用GA-K均值算法，以得到形成社區所需的實體聚類。

2 實驗與結果分析

本文GA-K均值的性能通常依賴于參數的數值選擇。該啟發式有5 個主要參數，即：交叉率Pc、變異率Pm、種群規模、代數，以及實驗次數。這些參數隨不同類型的數據集而變化。本文實驗中啟發式參數如下：種群規模為100；交叉率Pc為0.8；變異率Pm為0.1。混合參數μ取0.3（向量元素均取0.3）。實驗中采用了精英方法，確保將前代中得到的適應度最高的染色體保留到后代。適應度在連續5 代中未得到改進時，算法終止。為確定合適的隱性分量數量，利用不同數值的r執行因子分解，并將正規化參數λA和λR值設為10。

2.1 評價指標

本文采用純度、重疊歸一化互信息（Overlapping Normalized Mutual Information，ONMI）和F 得分作為評價度量。假定網絡的人工標注真實社區結構表示為C={C1，C2，…，CK}，方法實現的社區結構表示為C′={C′1，C′2，…，C′K}。使用的三個評價度量定義如下：

1）純度：其為外部評價度量，測量一個聚類中包含的數據樣本屬于單個類別的程度［18］。純度為1 表示完美聚類解，其中聚類僅包含單個類別的實體。因此，純度值越大，聚類解越好。純度計算式為：

式中：n為實體總數；|Cj∩C′k|表示Cj與C′k之間的交互。

2）重疊歸一化互信息的具體定義可以參考文獻［19］，ONMI越高，社區劃分越接近真實情況。

3）F得分：該評價度量以網絡真實社區結構C與方法實現的網絡社區結構C′中對象對的公共分類成員為基礎。設T表示C中屬于同一分類的對象對的集合，S表示在C′中被分配到同一個聚類的對象對的集合，則F得分（F-score）計算式為：

F 得分的數值在0 和1 之間，數值越高，表明社區劃分越接近真實。

2.2 數據集

為進行實驗分析，本文使用了一個人工合成數據集和兩個公開的數據集。

1）合成數據集：本文生成了包含三個聚類的合成網絡，這三個聚類分別包含100、150 和250 個成員。利用較低幀率（Lower Frame Rate，LFR）基準模型［20］來生成合成網絡及社區，如圖5 所示，從聚類1 到聚類2，從聚類2 到聚類3，再從聚類3 到聚類1，網絡中包含500 個成員，在聚類間和聚類的內部含有很多交叉關系。對于網絡的每個關系，按照伯努利分布和特定交互概率，在成員之間生成一條鏈路。此外，由于生成的合成數據集是定向的，很多常見的基線社區檢測方法更適用于非定向網絡，因此，將多關系網絡中的每個非對稱關系轉換為對稱關系。

圖5 合成網絡及社區Fig.5 Synthetic network and communities

2）公開的現實數據集的網絡介紹如表1 所示，包括Coauthorship 數據集和Twitter 數據集，且均為先驗可用。Coauthorship 數據集的頂點為作者，邊為合作，共計24 個研究領域，每篇文章被標注了一個或多個研究領域。通過發表途徑（會議/雜志）對（重疊）真實社區進行標記。該網絡中包含103677 個頂點，352183 條邊和1705 個社區。Twitter 數據集包含社交網站Twitter中不同用戶之間的交互。文獻［21］創建了5 個不同子數據集，每個子數據集中，考慮三種關系：提及，關注，以及轉發。這三種關系均被考慮為二元關系。對于每個關系（提及、關注和轉發），從節點i到節點j的定向邊分別表示用戶i在其推文中至少有一次提及、關注或轉發了用戶j。

表1 網絡介紹Tab.1 Introduction of networks

2.3 結果統計分析

本文實驗數據集采用合成數據集、公開的Coauthorship數據集和Twitter數據集，并與三個優秀社區檢測方法進行比較，這三個方法分別是：文獻［5］提出的CICD 方法；文獻［6］提出的Memetic 方法，該方法將檢測問題解釋為一種單目標的優化問題；文獻［9］提出的LSC 檢測方法，該方法是一種圖論方法。與文獻［9］類似，文獻［22］也是一種局部譜聚類社區檢測方法，該方法的特點是增加了社區節點屬性和距離度量，從而減少了對所選CD性能的依賴，但對于本文統計性指標沒有本質提升。因此，文獻［9］和文獻［22］作為一類方法進行比較。實驗通過2.1 節中的三個評價指標進行比較。不同方法在純度、ONMI 和F 值方面的性能比較如表2～4 所示。由表2～4 可知，本文方法的純度最少提高了5 個百分點，重疊歸一化互信息（ONMI）最少提高了2 個百分點，F 得分最少提高了3 個百分點，其性能明顯優于CICD［5］、Memetic［6］和LSC［9］。Memetic［6］和CICD［5］的最終結果取決于單個檢測方法的性能。其中，Memetic方法在發現某個非重疊社區結構后，重疊屬性通過后續處理可被發現，因此，這類方法最終的結果質量很大程度上取決于初始的非重疊社區結構。LSC 通過未標簽的數據分析來獲取更多其他數據的潛在分布情況，而類似的數據結構必須具有相同的標簽，LSC 是一種圖論方法，其對檢測方法的選擇具有一定依賴性，最終的結果質量取決于在異構網絡上使用的CD 的性能。本文利用網絡參與者之間隱藏的隱性關系信息進行社區發現，提出了基于鏈路的聚類框架，揭示參與者交互中所共享的社區結構，使用張量分解作為關系學習工具，在學習過程納入關系信息，應用GA-K均值算法進行社區發現。因此，所提方法的性能不取決于任何一個CD，能夠從多個非重疊社區結構中有效地學習社區屬性，其性能更優。此外，多關系方法的性能優于在網絡的每種關系上進行聚類的性能，在社區檢測過程中引入多種關系，有助于揭示共享社區模式。

表2 不同數據集上不同方法的純度性能Tab.2 Purity performance of different methods on different datasets

表3 不同數據集上不同方法的ONMI性能Tab.3 ONMI performance of different methods on different datasets

表4 不同數據集上不同方法的F得分Tab.4 F-score measurement of different methods on different datasets

為了對得出的結果進行統計學分析，本文考慮了假設檢驗的應用。為此，應用Friedman檢驗［23］，比較不同方法在合成數據集和Twitter數據集上的性能的統計差異。Friedman檢驗是一種非參數統計檢驗技術，因此，它不需要對數據的底層分布作任何假設；此外，利用Friedman 檢驗，可基于計算出的秩次，根據方法的相對性能進行排序。

該檢驗中，零假設表明所有方法在性能方面明顯等效。為得到Friedman 統計量，本文使用了排序方法。設N為實驗數據集數量，t為要比較的方法數。對于每個數據集，向t個方法中的每個方法分配從1（最佳結果）到t（最差結果）的秩次。取所有數據集上的平均秩次，計算出每個方法的最終秩次。結果的顯著性取決于得到的統計量p值。若p值小于0.05（顯著水平α=0.05），則拒絕零假設，可假定比較方法之間存在顯著性差異。為進一步分析，選擇秩次最優的方法作為控制方法，并應用一組析因分析程序，以執行其他方法與控制方法的逐對比較。實驗中，針對每個評價度量（即純度、ONMI 和F得分）執行了Friedman檢驗。不同方法的平均秩次如表5所示。從表5 中可以發現，不同方法的p值均非常低（純度的1.58E-6<0.05，F得分的6.40E-6<0.05，ONMI 的4.04E-8<0.05）。因此，假設不成立，并可認為所有方法的性能中存在顯著差異。本文方法秩次最低，因此可被選為控制方法。

表5 不同方法的平均秩次Tab.5 Mean ranks of different methods

2.4 計算參數分析與收斂性

涉入度函數可以評估這個頂點多大程度上屬于這個社區，涉入程度有兩個重要方面可以體現，即：接近中心度和一致存續性［24］。其中：接近中心度可以度量某個頂點與社區其他頂點的相似度；一致存續性可以度量頂點在其社區中的存續性。這里主要討論混合參數μ的選擇，μ表示社區間和社區內的邊的比率，μ數值越低，表示社區質量越高。μ與OMNI的關系如圖6 所示。可以看出，隨著混合參數μ的增加，涉入度函數的ONMI 值逐漸變低，即：混合參數μ的逐漸增加使得社區劃分質量逐漸降低，但依然保持較高的水平，最低為0.75。本文使用兩種不同涉入度函數度量，其中一致續存性評價頂點在社區的存在延續性接近中心度評價頂點與社區其他頂點的相似度，從結果來看，兩種函數度量均能準確顯示ONMI 的變化趨勢，且保持了較高的社區劃分質量，因此，兩種涉入度函數均取得了良好性能。

圖6 混合參數與ONMI的關系Fig.6 Relationship between hybrid parameter and ONMI

為消除隨機誤差的影響，本文在每個數據集上使用不同的解，因此，單次運行方法無法證明方法的有效性或效率。為了展示遺傳算法后續各代的適應度變化，本文在數據集上運行10次算法，并繪制適應圖如圖7所示。其中，圖7（a）給出了不同運行下，不同代的種群最優適應度的進化情況；圖7（b）給出了不同運行下，不同代的種群平均適應度的變化情況。由圖7 可知，平均適應度得分遵循相似模式。但從圖7（a）中發現，近嚴格遞減的平均標準誤差，即每代的最佳適應度數值范圍會在下一代縮減。圖7（b）展示了各代在進化時間線上的均值，初始少數幾輪的標準誤差較小，算法本質上具有探索性，對搜索空間中各種不同的候選解進行探索；因此，曲線在開始時逐漸上升，其后開始收斂，但并非嚴格一致。這意味著算法在探索搜索空間時，也同時在探索最優解并收斂。

圖7 10次實驗的100代適應度Fig.7 100 generation fitness in 10 experiments

2.5 運行效率

對于每個數據集，不同方法所需的運行時間如表6 所示。本文方法包括兩個計算步驟：1）在數據的張量表征上執行張量分解；2）對因子分解步驟的結果應用GA-K均值。針對分解步驟，所提方法耗時屬于中等，時間復雜度主要由基于GA 的K均值算法決定。Memetric 方法的計算時間較長，其收斂時間大于RESCAL分解。LSC的運行時間大于K均值，因為譜聚類的計算量大于K均值聚類。K均值和LSC 的計算時間明顯少于其他方法，這是因為聚類算法的復雜度普遍較低。雖然本文方法的時間復雜度屬于中等，但社區檢測性能優于其他方法。

表6 不同方法在不同數據集上的運行時間 單位：sTab.6 Running times of different methods on different datasets unit：s

3 結語

本文利用網絡參與者之間隱藏的隱性關系信息進行社區發現，提出了基于鏈路的聚類框架，揭示了參與者交互中所共享的社區結構。該方法利用三階張量對多關系網絡進行建模，并使用張量分解作為關系學習工具，在學習過程納入關系信息，應用GA-K均值算法進行社區發現。在合成和真實數據集上進行大量實驗，實驗結果驗證了所提方法的有效性和高效率。

接下來，我們將進一步分析社區的動態性和時態性。此外，結合軟聚類方法和其他聚類標準，利用不同長度的染色體表征對本文方法進行擴展，以確定網絡中社區的最優數量。由于GA 方法耗時較久，以后還可嘗試通過并行版本的算法來提高運行速度。