基于張量建模和進(jìn)化K均值聚類的社區(qū)檢測方法

陳吉成，陳鴻昶

（信息工程大學(xué)信息技術(shù)研究所，鄭州 450002）

0 引言

社區(qū)檢測（Community Detection，CD）［1］是分析復(fù)雜網(wǎng)絡(luò)的重要工具，其目的是發(fā)現(xiàn)強(qiáng)凝聚性群體，此類群體中成員彼此之間的聯(lián)系比網(wǎng)絡(luò)中其他參與者的聯(lián)系更加緊密，由此提取出的社區(qū)具有重要統(tǒng)計價值，應(yīng)用范圍包括語義網(wǎng)本體構(gòu)建［2］、標(biāo)簽系統(tǒng)中的話題檢測［3］、個性化搜索和推薦［4］等。

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

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

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

1 多關(guān)系網(wǎng)絡(luò)中的社區(qū)檢測

本文多關(guān)系網(wǎng)絡(luò)社區(qū)檢測的流程如圖1 所示，利用RESCAL 張量分解和GA-K均值聚類在多關(guān)系網(wǎng)絡(luò)中進(jìn)行社區(qū)檢測。為了在學(xué)習(xí)方法中考慮到數(shù)據(jù)的關(guān)系特性，本文使用張量對多關(guān)系網(wǎng)絡(luò)進(jìn)行建模。下面對圖1 各個重要環(huán)節(jié)進(jìn)行介紹。

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

1.1 多關(guān)系網(wǎng)絡(luò)建模

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

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

圖2 多關(guān)系數(shù)據(jù)的張量模型Fig.2 Tensor model of multiple relational data

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

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

1.3 RESCAL分解

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

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

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

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

該模型中，F(xiàn)的行fi對應(yīng)第i個實(shí)體的隱性表征，張量R的frontal 切片Rk則對第k種關(guān)系的隱性變量的交互進(jìn)行建模。由此，F(xiàn)是包含實(shí)體隱性表征的矩陣，R為隱性分量與謂詞的交互。

1.4 RESCAL分解計算

為執(zhí)行RESCAL分解，需要求解以下優(yōu)化問題：

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

在該步驟中，使用RESCAL 分解對表示多關(guān)系網(wǎng)絡(luò)的張量進(jìn)行因子分解。該步驟的結(jié)果為矩陣F∈Rn×r，其中，n為總條目數(shù)，r為因子分解的秩。由于F中包含低維嵌入實(shí)體的唯一性表征，可應(yīng)用聚類方法對F實(shí)施聚類以發(fā)現(xiàn)不同的社區(qū)。

1.5 使用GA-K均值算法進(jìn)行社區(qū)檢測

聚類技術(shù)是識別實(shí)體集合中內(nèi)在組織的非監(jiān)督式技術(shù)。K均值算法是廣泛使用的聚類技術(shù)，但其存在兩個缺陷：1）陷入局部最優(yōu)；2）結(jié)果的準(zhǔn)確度取決于初始聚類中心。

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

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

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

步驟2 對每個染色體進(jìn)行解碼，得到初始種子。利用這些初始種子，執(zhí)行K均值聚類。其后，計算出適應(yīng)度函數(shù)值。

步驟3 在當(dāng)前種群上執(zhí)行遺傳操作，以生成新一代種群。迭代該過程，直至滿足停止標(biāo)準(zhǔn)。提出的方法中，若適應(yīng)度在連續(xù)5次迭代中未得到改善，則終止算法。

1.6 遺傳表征和種群初始化

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

1.7 適應(yīng)度函數(shù)的計算

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

式中：μk為屬于第k個聚類Ck的數(shù)據(jù)點(diǎn)的平均向量。類內(nèi)散布矩陣SW表示所有聚類的散度之和，其計算式為：

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

式中：Nk為屬于第k個聚類的數(shù)據(jù)點(diǎn)數(shù)量；μk為第k個聚類的平均向量?；旌蠀?shù)向量μ可計算為：

其中，混合參數(shù)向量μ表示社區(qū)間和社區(qū)內(nèi)的邊的比率，μ的元素數(shù)值越低，表示社區(qū)質(zhì)量越高。將類間散布矩陣和類內(nèi)散布矩陣的跡比取作適應(yīng)度函數(shù)。目標(biāo)是最大化以下比率fobj：

式中：Tr（）表示求跡運(yùn)算符。

1.8 新種群的生成

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

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

2）交叉算子。選擇后，在染色體上應(yīng)用交叉算子以得到更好的后代。本文研究中使用了均勻交叉算子和改進(jìn)的全算術(shù)算子。

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

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

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

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

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

所提出的多關(guān)系網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)方法主要步驟如下：

步驟1 給定一個包含n個實(shí)體以及實(shí)體間m類關(guān)系的多關(guān)系網(wǎng)絡(luò)，創(chuàng)建一個大小為n×n×m的三階張量。

步驟2 在構(gòu)建的張量上應(yīng)用RESCAL 張量分解，其中r為因子分解的秩。該步驟得到的結(jié)果為包含實(shí)體的唯一性表征的因子矩陣F∈Rn×r。

步驟3 對因子矩陣F應(yīng)用GA-K均值算法，以得到形成社區(qū)所需的實(shí)體聚類。

2 實(shí)驗(yàn)與結(jié)果分析

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

2.1 評價指標(biāo)

本文采用純度、重疊歸一化互信息（Overlapping Normalized Mutual Information，ONMI）和F 得分作為評價度量。假定網(wǎng)絡(luò)的人工標(biāo)注真實(shí)社區(qū)結(jié)構(gòu)表示為C={C1，C2，…，CK}，方法實(shí)現(xiàn)的社區(qū)結(jié)構(gòu)表示為C′={C′1，C′2，…，C′K}。使用的三個評價度量定義如下：

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

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

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

3）F得分：該評價度量以網(wǎng)絡(luò)真實(shí)社區(qū)結(jié)構(gòu)C與方法實(shí)現(xiàn)的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)C′中對象對的公共分類成員為基礎(chǔ)。設(shè)T表示C中屬于同一分類的對象對的集合，S表示在C′中被分配到同一個聚類的對象對的集合，則F得分（F-score）計算式為：

F 得分的數(shù)值在0 和1 之間，數(shù)值越高，表明社區(qū)劃分越接近真實(shí)。

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

為進(jìn)行實(shí)驗(yàn)分析，本文使用了一個人工合成數(shù)據(jù)集和兩個公開的數(shù)據(jù)集。

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

圖5 合成網(wǎng)絡(luò)及社區(qū)Fig.5 Synthetic network and communities

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

表1 網(wǎng)絡(luò)介紹Tab.1 Introduction of networks

2.3 結(jié)果統(tǒng)計分析

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

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

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

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

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

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

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

2.4 計算參數(shù)分析與收斂性

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

圖6 混合參數(shù)與ONMI的關(guān)系Fig.6 Relationship between hybrid parameter and ONMI

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

圖7 10次實(shí)驗(yàn)的100代適應(yīng)度Fig.7 100 generation fitness in 10 experiments

2.5 運(yùn)行效率

對于每個數(shù)據(jù)集，不同方法所需的運(yùn)行時間如表6 所示。本文方法包括兩個計算步驟：1）在數(shù)據(jù)的張量表征上執(zhí)行張量分解；2）對因子分解步驟的結(jié)果應(yīng)用GA-K均值。針對分解步驟，所提方法耗時屬于中等，時間復(fù)雜度主要由基于GA 的K均值算法決定。Memetric 方法的計算時間較長，其收斂時間大于RESCAL分解。LSC的運(yùn)行時間大于K均值，因?yàn)樽V聚類的計算量大于K均值聚類。K均值和LSC 的計算時間明顯少于其他方法，這是因?yàn)榫垲愃惴ǖ膹?fù)雜度普遍較低。雖然本文方法的時間復(fù)雜度屬于中等，但社區(qū)檢測性能優(yōu)于其他方法。

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

3 結(jié)語

本文利用網(wǎng)絡(luò)參與者之間隱藏的隱性關(guān)系信息進(jìn)行社區(qū)發(fā)現(xiàn)，提出了基于鏈路的聚類框架，揭示了參與者交互中所共享的社區(qū)結(jié)構(gòu)。該方法利用三階張量對多關(guān)系網(wǎng)絡(luò)進(jìn)行建模，并使用張量分解作為關(guān)系學(xué)習(xí)工具，在學(xué)習(xí)過程納入關(guān)系信息，應(yīng)用GA-K均值算法進(jìn)行社區(qū)發(fā)現(xiàn)。在合成和真實(shí)數(shù)據(jù)集上進(jìn)行大量實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果驗(yàn)證了所提方法的有效性和高效率。

接下來，我們將進(jìn)一步分析社區(qū)的動態(tài)性和時態(tài)性。此外，結(jié)合軟聚類方法和其他聚類標(biāo)準(zhǔn)，利用不同長度的染色體表征對本文方法進(jìn)行擴(kuò)展，以確定網(wǎng)絡(luò)中社區(qū)的最優(yōu)數(shù)量。由于GA 方法耗時較久，以后還可嘗試通過并行版本的算法來提高運(yùn)行速度。