基于非負矩陣分解的半監(jiān)督動態(tài)社團檢測

常振超，陳鴻昶，黃瑞陽，于洪濤，劉陽

?

基于非負矩陣分解的半監(jiān)督動態(tài)社團檢測

常振超，陳鴻昶，黃瑞陽，于洪濤，劉陽

（國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南鄭州 450002）

如何有效融合不同時刻的網(wǎng)絡(luò)結(jié)構(gòu)信息，是影響復(fù)雜網(wǎng)絡(luò)中動態(tài)社團檢測算法檢測性能的關(guān)鍵和難點。基于此，提出了一種基于非負矩陣分解的半監(jiān)督動態(tài)社團檢測方法SDCD-NMF，該方法首先有效提取了歷史時刻所包含的穩(wěn)定結(jié)構(gòu)單元，然后將其作為正則化監(jiān)督項，指導(dǎo)當(dāng)前時刻的網(wǎng)絡(luò)社團檢測。在真實網(wǎng)絡(luò)數(shù)據(jù)集上的實驗表明，所提方法與已有方法相比具備更高的社團劃分質(zhì)量，更有利于探索網(wǎng)絡(luò)的演變與發(fā)展規(guī)律。

半監(jiān)督；動態(tài)；社團檢測；非負矩陣分解

1 引言

網(wǎng)絡(luò)涵蓋人類生活的方方面面，對網(wǎng)絡(luò)中的社團進行挖掘一直是跨各學(xué)科領(lǐng)域研究者所共同關(guān)注的熱點。社團是密集交互的群組，如社會網(wǎng)絡(luò)中具備相同愛好或者屬性特征的群體、生物網(wǎng)絡(luò)組織中的器官、科學(xué)家合作網(wǎng)絡(luò)中相同領(lǐng)域的研究小組等[1]。網(wǎng)絡(luò)通常用圖來進行表示，圖中節(jié)點表示網(wǎng)絡(luò)中的基本構(gòu)建單元，鏈接表示節(jié)點之間的交互。已有的經(jīng)典算法諸如基于連接的GN算法[2]、圖譜分析方法[3]、非負矩陣分解方法[4]等大多從基于靜態(tài)網(wǎng)絡(luò)分析[5~7]角度出發(fā)。而許多真實的網(wǎng)絡(luò)是持續(xù)演化的[8]，即網(wǎng)絡(luò)結(jié)構(gòu)隨著時間刻度不斷變化，對靜態(tài)分析算法有必要進行進一步地擴展，以適應(yīng)動態(tài)網(wǎng)絡(luò)分析的需求。動態(tài)社團檢測[9]就是從這種變化的網(wǎng)絡(luò)結(jié)構(gòu)中檢測不同時間刻度上密集連接的群組。從靜態(tài)網(wǎng)絡(luò)分析轉(zhuǎn)向?qū)討B(tài)網(wǎng)絡(luò)的演化研究是近年來復(fù)雜網(wǎng)絡(luò)研究的新趨勢。

已有大量針對動態(tài)網(wǎng)絡(luò)的社團檢測的方法被研究者提出，主要可以分為2類[10,11]：一類是基于進化聚類的方式，該方法依據(jù)動態(tài)網(wǎng)絡(luò)變化緩慢的基本特征，在對每個時刻的網(wǎng)絡(luò)進行聚類時，既要使聚類結(jié)果與當(dāng)前時刻的網(wǎng)絡(luò)結(jié)構(gòu)（靜態(tài)快照質(zhì)量）盡量一致，又要滿足當(dāng)前聚類結(jié)果與歷史時刻的網(wǎng)絡(luò)結(jié)構(gòu)差異較?。v史開銷）；另一類是基于增量聚類的方法，增量的方法以歷史時刻網(wǎng)絡(luò)劃分為基礎(chǔ)，僅針對增量相關(guān)的節(jié)點和邊進行處理，算法運算速度較快，但為減少時間上的花費，一般都會對聚類質(zhì)量造成一些犧牲，難以有效應(yīng)對社團數(shù)目發(fā)生變化等情況。非負矩陣分解(NMF, non- negative matrix factorization)作為一種有效的高維數(shù)據(jù)降維方法，具備非負性和易解釋性，在數(shù)據(jù)挖掘領(lǐng)域中得到了廣泛應(yīng)用[12]。由于能夠從本質(zhì)上揭示圖數(shù)據(jù)網(wǎng)絡(luò)的基本組成，研究者們將其成功地運用在社團檢測領(lǐng)域中?；趫D正則化的半監(jiān)督非負矩陣分解方法，將約束信息（部分節(jié)點連接信息）指導(dǎo)分解迭代過程中，能夠有效提升算法的準(zhǔn)確性，在文本聚類、圖數(shù)據(jù)挖掘和靜態(tài)社團檢測等領(lǐng)域已經(jīng)取得了較大的研究進展[4, 13~17]。

基于上述分析，本文從提升動態(tài)網(wǎng)絡(luò)社團檢測精度的角度出發(fā)，采用進化聚類的方式對其展開研究，即如何高效地利用歷史時刻的信息指導(dǎo)當(dāng)前時刻的網(wǎng)絡(luò)劃分，提出了一種基于非負矩陣分解的半監(jiān)督動態(tài)社團檢測方法SDCD-NMF，該方法首先有效提取了歷史時刻所包含的穩(wěn)定結(jié)構(gòu)信息，然后將其作為非負矩陣分解的正則化項，指導(dǎo)當(dāng)前時刻的網(wǎng)絡(luò)社團檢測。本文所提方法首次將半監(jiān)督的非負矩陣分解架構(gòu)應(yīng)用到動態(tài)社團檢測中去，其優(yōu)勢在于有效提取并融合了歷史時刻的約束信息，指導(dǎo)當(dāng)前時刻的社團劃分，為動態(tài)網(wǎng)絡(luò)社團檢測提供了新的研究思路和框架。

2 相關(guān)工作

真實的網(wǎng)絡(luò)不斷演化，其社團結(jié)構(gòu)隨著時間推進也在發(fā)生變化，例如社團中節(jié)點和連邊的消失和增加、社團的合并和分類等。針對動態(tài)變化的網(wǎng)絡(luò)社團挖掘仍處于起步階段。近幾年來，國內(nèi)外研究者分別針對社團的演化提出了一些不同的模型和方法，主要可以分為2類：增量聚類和進化聚類。下面對這2類方法相關(guān)研究進展進行了簡要回顧。

2.1 基于增量聚類的動態(tài)社團檢測

基于增量聚類的動態(tài)社團檢測是一種動態(tài)更新策略，將歷史時刻的社團劃分作為基礎(chǔ)，在后續(xù)階段進行更新，大多從增量相關(guān)的節(jié)點和邊出發(fā)進行研究，算法的運算效率較高。如Sun等[18]提出的基于信息論的GrapScope算法，以增量的方式選擇信息編碼花費最小的方式進行劃分。黃永鋒等[19]提出了一種基于社會特征周期演化的社團檢測方法，用之服務(wù)于網(wǎng)絡(luò)路由轉(zhuǎn)發(fā)策略的設(shè)計。Ning等[20]提出了一種增量譜聚類的方法，通過引入發(fā)生矩陣來描述網(wǎng)絡(luò)節(jié)點的增、刪以及節(jié)點相似性變化，增量更新譜系統(tǒng)。單波等[21]提出了一種增量IC算法，該算法基于社團數(shù)目是恒定不變的。肖杰斌等[22]提出了一種隨機游走的增量處理相關(guān)節(jié)點的方法，對增量相關(guān)節(jié)點進行隨機游走聚類，擴展了算法的適用性。郭進時等[23]將拓撲勢引入到增量相關(guān)節(jié)點的處理上去，一定程度上提高了算法的檢測精度。Miguel等[24]提出了一種基于張量分析的增量識別算法，將張量分解與異常檢測相融合，通過對不同張量的迭代分析，以獲取增量節(jié)點的社團歸屬。另外，也有其他將經(jīng)典算法進行改進為增量聚類方法，如本征矢量分解方法[25]、Rober[26]提出的切割數(shù)方法和Duan等[27]提出的派系圖方法等。

2.2 基于進化聚類的動態(tài)社團檢測

進化聚類通常假設(shè)歷史信息具備時域平滑性，即當(dāng)前時刻的社團劃分同前一時刻社團劃分結(jié)果相差不大。Chakrabarti等[9]最早提出了一種進化聚類分析架構(gòu)，該方法將當(dāng)前時刻動態(tài)社團劃分結(jié)果看成是當(dāng)前時刻的靜態(tài)快照劃分質(zhì)量與歷史時刻社團劃分結(jié)果的折中，既要滿足靜態(tài)劃分的拓撲一致性，也要使歷史開銷盡量小，即一個好的社團劃分結(jié)果也能夠盡量滿足前一時刻的網(wǎng)絡(luò)基本結(jié)構(gòu)，其劃分質(zhì)量可以用下述公式來進行描述。

2.3 已有算法分析

基于增量聚類的動態(tài)社團檢測，以歷史時刻所獲取的社團劃分為基礎(chǔ)，然后進行增量相關(guān)部分調(diào)整，大多假設(shè)社團的數(shù)目不發(fā)生變化，難以有效應(yīng)對社團的合并、分裂和消亡等數(shù)目變化情況，雖然通常具備較高的運算效率，但一般都會對聚類質(zhì)量造成一些犧牲，導(dǎo)致其算法精度有待提升。而基于進化聚類的動態(tài)社團檢測，從不同時刻的檢測結(jié)果進行綜合考慮，將歷史信息融入到社團檢測中來，利用歷史有效信息減少噪聲的影響，優(yōu)化了當(dāng)前時刻的社團劃分，能夠取得較好的檢測效果，由于其能夠檢測社團中社團數(shù)目變化，具備更好的適應(yīng)動態(tài)社團檢測需求，擁有更好的檢測性能和合理的動態(tài)網(wǎng)絡(luò)解釋性，但如何有效利用歷史信息是進化聚類算法的關(guān)鍵。

綜上所述，本文從提升動態(tài)網(wǎng)絡(luò)社團檢測精度的角度出發(fā)，采用進化聚類的方式展開研究，提出了一種基于非負矩陣分解的半監(jiān)督動態(tài)社團檢測方法。該方法首先提取歷史信息中所包含的穩(wěn)定連接關(guān)系，然后將其作為約束項以指導(dǎo)當(dāng)前時刻的劃分，采用了半監(jiān)督的非負矩陣分解架構(gòu)，克服了線性融合不同時刻的社團劃分需要人工設(shè)定平衡因子的缺陷，有效融合了歷史信息，具備更好的理論基礎(chǔ)和可行性。

3 半監(jiān)督動態(tài)社團檢測

傳統(tǒng)的進化聚類大多采用線性組合不同時刻社團劃分結(jié)果的方法，即將歷史劃分開銷和靜態(tài)快照質(zhì)量開銷進行線性優(yōu)化，需要確定這兩者之間的平衡因子，但該因子通常是人工進行設(shè)定，缺乏有效的優(yōu)化策略，如何有效融合歷史信息是進化聚類算法性能提升的關(guān)鍵。本文采用半監(jiān)督的非負矩陣對社團進行劃分，首先將歷史時刻的穩(wěn)定連接關(guān)系進行提取，作為約束信息（圖正則化項）進而指導(dǎo)當(dāng)前時刻的網(wǎng)絡(luò)劃分，以克服原有算法中需要人工確定平衡因子的缺陷，能夠有效提升動態(tài)社團的檢測精度。

3.1 相關(guān)定義及分析

3.2 非負矩陣分解

由于網(wǎng)絡(luò)節(jié)點間的鏈接總是非負的，即邊權(quán)重都是非負的，因此，非常適合采用非負矩陣分解進行社團檢測[4~8]?；诜秦摼仃囘M行社團檢測的基本定義如下，假設(shè)擁有個節(jié)點的某網(wǎng)絡(luò)的鄰接矩陣為，則NMF定義為：通過尋找最大近似原始網(wǎng)絡(luò)數(shù)據(jù)的2個低秩因子矩陣和來實現(xiàn)社區(qū)發(fā)現(xiàn)，分解后得到的基向量矩陣表示網(wǎng)絡(luò)降維后的社區(qū)特征，具有稀疏性和線性無關(guān)性，而歸屬矩陣則表示相應(yīng)節(jié)點與社區(qū)的隸屬程度。其一般采用歐幾里德距離最小化方式，優(yōu)化的目標(biāo)函數(shù)為

3.3 約束信息獲取

因此，這里半監(jiān)督信息主要關(guān)注成對約束信息，即同一條邊所連接的2個節(jié)點是否屬于同一個社團情況。成對約束主要包括2種信息，即must-link和cannot-link，而這里只關(guān)注must-link，原因是該約束主要用于控制數(shù)據(jù)壓縮之后表示的距離更近；而cannot-link表示不同類別之間的相似度，且在本文中難以進行有效的提取。對must-link信息進行介紹如下。

現(xiàn)在問題轉(zhuǎn)化為如何有效提取歷史時刻的約束信息上，動態(tài)網(wǎng)絡(luò)一般采用時間刻度分析方法，已經(jīng)有大量的提取共有特征的方法，本文采用挖掘歷史時刻穩(wěn)定的微觀結(jié)構(gòu)—三角結(jié)構(gòu)，來確定節(jié)點之間的成對約束關(guān)系。相關(guān)研究表明[37,38]，三角結(jié)構(gòu)是網(wǎng)絡(luò)中較為穩(wěn)定的結(jié)構(gòu)關(guān)系，借助三角結(jié)構(gòu)信息挖掘社團已經(jīng)有了大量的相關(guān)研究。即便出現(xiàn)社團消亡、分裂情況，穩(wěn)定三角結(jié)構(gòu)中包含的成對約束在不同的相鄰時刻里，仍然能夠以較大概率滿足成對約束，其不對具體的聚類標(biāo)示進行修改，而只是表明了節(jié)點處于同一個社團的可能性較大，更能符合社團數(shù)目變化或者節(jié)點對社團歸屬改變的情況，更具備理論指導(dǎo)意義。對三角結(jié)構(gòu)信息的穩(wěn)定性結(jié)合圖2進行分析如下。

在圖2的三角結(jié)構(gòu)中，、和分別為其3個頂點，當(dāng)前時刻該三角結(jié)構(gòu)滿足三角結(jié)構(gòu)，設(shè)定下一時刻該三角結(jié)構(gòu)中任何一條邊（連接）斷掉，即不再滿足must-link的成對約束的概率為，則仍保持圖2(a)三角結(jié)構(gòu)的概率為，跳變?yōu)閳D2(b)只有一條邊（連接）斷掉的概率為，跳變?yōu)閳D2(c)斷掉2條邊（連接）的概率為，3條邊（連接）完全斷掉即跳變?yōu)閳D2(d)的概率為。至此，所有成對約束邊跳轉(zhuǎn)情況分析已經(jīng)結(jié)束。

1) must-link約束：即下一時刻為圖2(a)時，3個節(jié)點中兩兩滿足仍為成對約束情況。

2) must-link約束傳遞：即下一時刻為圖2(b)時，通過2個邊的連接擴展，補充到第3條邊的連接情況，即滿足成對約束的傳遞性。

綜上所述，在歷史時刻中三角結(jié)構(gòu)中的頂點，在當(dāng)前時刻仍處于同一個社團的概率為，此概率值接近于1。原因如下，進化聚類假設(shè)相鄰時刻的網(wǎng)絡(luò)結(jié)構(gòu)不會出現(xiàn)劇烈的變化，即變化部分占據(jù)了很小的比例，體現(xiàn)在微觀的連邊在下一時刻斷掉的概率值很小，其出現(xiàn)圖2(a)和圖2(b)的概率較高，即在當(dāng)前時刻3個節(jié)點仍兩兩近似滿足成對約束。同時，在本文實驗中也驗證了采用三角結(jié)構(gòu)來對歷史穩(wěn)定信息進行刻畫的有效性。

對三角結(jié)構(gòu)作為歷史監(jiān)督信息有效性分析之后，約束信息獲取過程的描述如下所示。

2) 由三角結(jié)構(gòu)的頂點關(guān)系，根據(jù)定義3，構(gòu)造兩兩節(jié)點之間的成對約束矩陣。

3.4 基于圖正則化的非負矩陣分解方法

本節(jié)將給出本文所提出半監(jiān)督動態(tài)檢測方法，這里采用基于圖正則化的非負矩陣分解方法，由于其能夠有效利用部分節(jié)點的先驗信息，已經(jīng)在很多領(lǐng)域得到了成功的應(yīng)用[4~8]。該方法基于流行假設(shè)，即對原始數(shù)據(jù)圖矩陣進行分解之后，在得到的特征矩陣空間上（變換空間后），同一類節(jié)點之間的距離更近，而不同類節(jié)點之間的距離更遠，改進后的半監(jiān)督方法的優(yōu)化目標(biāo)為

根據(jù)基于圖正則化項的半監(jiān)督NMF求解優(yōu)化過程[4]，對于原式中的矩陣和進行求解，為保證求解過程的非凸性，對參數(shù)進行分別更新，此優(yōu)化問題的迭代過程如下所示。

(5)

當(dāng)相鄰2次迭代過程中，目標(biāo)函數(shù)差值滿足較小(通常設(shè)定為10?5)，或其值不再變小時，算法收斂，迭代過程終止。

基于最終的優(yōu)化目標(biāo)函數(shù)和歷史時刻網(wǎng)絡(luò)，對本文所提基于非負矩陣分解的半監(jiān)督動態(tài)社團檢測具體步驟進行描述如下。假設(shè)需要計算時刻的網(wǎng)絡(luò)社團劃分結(jié)構(gòu)，已知時刻到的網(wǎng)絡(luò)結(jié)構(gòu)。首先，基于NMF算法，提取時刻網(wǎng)絡(luò)中的社團結(jié)構(gòu)；然后，根據(jù)，提取出社團結(jié)構(gòu)中包含的三角結(jié)構(gòu)，構(gòu)造時刻的成對約束先驗信息；最后，根據(jù)式(3)，采用基于圖的正則化方法，計算時刻社團結(jié)構(gòu)，依次類推，直到計算出所需要的時刻的社團歸屬矩陣。本文所提方法，按照時刻不同，提取出不同的穩(wěn)定歷史結(jié)構(gòu)信息，在同一個非負矩陣分解框架下，能夠有效利用歷史信息中包含的約束信息，進而指導(dǎo)當(dāng)前時刻的社團檢測。

算法2 融合多屬性算法

5) while not convergent do

8) end while

9) end for

在算法2中，首先經(jīng)過初始化矩陣，通過前一時刻的網(wǎng)絡(luò)社團中約束信息獲取，指導(dǎo)當(dāng)前時刻的社團劃分，矩陣運算過程中，固定其中2個變量，然后反復(fù)迭代運算，直到目標(biāo)函數(shù)收斂，以求得和。

3.5 模型選擇

在動態(tài)網(wǎng)絡(luò)中，需要確定每個時刻上不同的社團數(shù)目，這就是模型選擇問題，即確定社團檢測中的社團數(shù)目，也就是在矩陣分解迭代運算中矩陣的行數(shù)。已經(jīng)有很多種模型選擇方法提出來[17,24,25]，有基于本征值差異方法[39]、交叉驗證貝葉斯方法[7,40]和基于模塊度的方法[5,6]等。需要提前對社團數(shù)目進行預(yù)估計。本文采用文獻[41]所采用譜分析的方法，該方法基于裴龍聚類(Perron clusters)的本征值所決定[42]。

由于本文基于鏈接矩陣作為基矩陣進行估計，社團數(shù)目可由該鏈接矩陣的譜分析進行預(yù)估計。首先構(gòu)造對角方陣，該方陣中的對角線上的值為圖中相應(yīng)節(jié)點度（鏈接個數(shù)）的大小?；谶@2個矩陣構(gòu)造拉普拉斯矩陣，并對其進行正規(guī)化，獲取正規(guī)化矩陣。

(6)

本文所提模型選擇方法用于提前確立不同時刻網(wǎng)絡(luò)結(jié)構(gòu)中的社團數(shù)目，其獨立于社團檢測過程。

3.6 復(fù)雜度分析

本文設(shè)計的動態(tài)社團檢測算法復(fù)雜度主要考慮3個方面：約束信息的獲取、模型選擇和半監(jiān)督的矩陣迭代分解。假定網(wǎng)絡(luò)節(jié)點個數(shù)為，網(wǎng)絡(luò)社團數(shù)目為，在約束信息獲取過程中，需要提取已知社團結(jié)構(gòu)中的三角形，且三角形結(jié)構(gòu)中存在節(jié)點重疊現(xiàn)象，取不同的社團中節(jié)點數(shù)目相等進行計算，且社團中所有節(jié)點均為全連接情況，其算法復(fù)雜度為，在實際情況中，社團內(nèi)部不可能所有的節(jié)點滿足全連接這個假設(shè)，因此，復(fù)雜度應(yīng)遠小于。模型選擇中裴龍聚類包含對角矩陣獲取、規(guī)范化和本征特征值的計算，這3個步驟中，復(fù)雜度最高的為本征值獲取，按照最高的運算復(fù)雜度進行取值，其算法復(fù)雜度為。半監(jiān)督的矩陣分解中，算法復(fù)雜度除了矩陣乘運算之外，還取決于迭代次數(shù)。其算法復(fù)雜度約為，當(dāng)考慮矩陣的稀疏程度時，該值可以進一步降低為，其中，是must-link的先驗信息中節(jié)點對個數(shù)，是矩陣中數(shù)值為1的個數(shù)，即真實存在的邊個數(shù)。綜合三者分析，本文設(shè)計算法的復(fù)雜度最大約為++。

4 實驗

為驗證本文所提算法的有效性，本文在真實網(wǎng)絡(luò)數(shù)據(jù)集上進行了相關(guān)的實驗，并對實驗結(jié)果進行了分析。

4.1 實驗數(shù)據(jù)

對已有文獻中所廣泛應(yīng)用的網(wǎng)絡(luò)仿真數(shù)據(jù)集進行分析，選擇了2類數(shù)據(jù)庫進行驗證：一類是全局背景已知的情況，采用的是常見的網(wǎng)絡(luò)仿真數(shù)據(jù)庫工具LFR進行生成人工網(wǎng)絡(luò)；另一類是3種常見的真實網(wǎng)絡(luò)數(shù)據(jù)庫。3種最常見的數(shù)據(jù)集進行了仿真實驗，包括Enron郵件網(wǎng)絡(luò)[43]、arXiv電子引文網(wǎng)絡(luò)[44]和Facebook社交網(wǎng)絡(luò)[45]。這些網(wǎng)絡(luò)數(shù)據(jù)集覆蓋了一定的時間間隔，借鑒文獻[46]中的實驗數(shù)據(jù)的靜態(tài)圖構(gòu)建方式，對數(shù)據(jù)進行提煉，以構(gòu)造有效的數(shù)據(jù)集，本文所采用的相應(yīng)數(shù)據(jù)庫具體介紹如下。

LFR網(wǎng)絡(luò)[43]：本文中LFR網(wǎng)絡(luò)參考文獻[30]的實驗設(shè)置，生成網(wǎng)絡(luò)數(shù)目為50個，且在相同的參數(shù)設(shè)置下，產(chǎn)生10個網(wǎng)絡(luò)靜態(tài)圖。仿真了節(jié)點個數(shù)為10 000情況下，混合參數(shù)為0.3和0.5的情況。

Enron郵件網(wǎng)絡(luò)[44]：該網(wǎng)絡(luò)包含了150個用戶之間的郵件信息，是Enron公司高級管理人員之間的通信。時間為1999年1月~2012年8月。對原始數(shù)據(jù)進行提煉，挑選其中7個主要的社團，其連接數(shù)大約占了總連接數(shù)目的50%，按照社團的生長過程，當(dāng)連接數(shù)目變化大約為1 000條連接時構(gòu)建新的快照，總共構(gòu)建了21個生長型網(wǎng)絡(luò)快照，即21個時間刻度。

arXiv電子引文網(wǎng)絡(luò)[45]：本文采用的數(shù)據(jù)庫為1996年1月~2003年5月，在本文的實驗中，對最初的1996年~1997年數(shù)據(jù)中所包含的網(wǎng)絡(luò)數(shù)據(jù)進行獲取初始社團結(jié)構(gòu)。采用1998年1月~2003年1月之間的數(shù)據(jù)，按照2個月時間間隔，構(gòu)建了30個靜態(tài)圖，即30個時間刻度。

Facebook社交網(wǎng)絡(luò)[47]：該數(shù)據(jù)集包含了Facebook網(wǎng)絡(luò)中新奧爾良區(qū)域內(nèi)注冊用戶之間的朋友關(guān)系，時間為2006年9月~2009年1月。數(shù)據(jù)集包含了6萬個節(jié)點，150萬個連接關(guān)系。本文中數(shù)據(jù)采用2006年9月~2006年12月的數(shù)據(jù)作為原始網(wǎng)絡(luò)數(shù)據(jù)。按照時間刻度每個月構(gòu)造靜態(tài)圖。從2007年1月~2009年1月總共構(gòu)造25張靜態(tài)圖，即25個時間刻度。

4.2 對比算法

為全面分析比較本文所提算法的性能，實驗挑選3類具備代表性的對比算法。1）NMF[12]，僅針對靜態(tài)圖的進行社團發(fā)現(xiàn)，該方法是一種無監(jiān)督聚類的方法，由于本文是采用歷史信息作為半監(jiān)督信息的NMF方法，故選擇僅對靜態(tài)圖進行社團挖掘的NMF方法作為對比算法。2）FaceNet[29]，該方法基于生成模型進行演化分析，首次將矩陣分解應(yīng)用到此類問題中來，其針對歷史時刻和當(dāng)前時刻分別進行聯(lián)合估計獲取社團劃分，采用平衡因子將兩者劃分進行統(tǒng)一，取得了較好的效果，是常用于對比算法中的經(jīng)典算法。3）A3CS[30]，該方法是動態(tài)社團檢測中提出較新的算法，其從保證模塊度最大化的角度出發(fā)，取得了較好的識別效果和較高的算法運行效率。

4.3 評價指標(biāo)

在本文實驗數(shù)據(jù)中，針對網(wǎng)絡(luò)的真實社團劃分已知和未知的情況，需要采用不同的社團劃分評價指標(biāo)。因此，本文實驗中選取常用的測試指標(biāo)歸一化互信息指標(biāo)NMI[43]和模塊度[1]來測試社團檢測性能。NMI用于衡量已知社團結(jié)構(gòu)下，檢測出來的社團結(jié)構(gòu)與已知社團結(jié)構(gòu)的差異程度，NMI值越大，劃分結(jié)果與已知的社團結(jié)果越相似。模塊度是由Newman和Girvan提出的一種用于評價劃分結(jié)果的重要指標(biāo)，該指標(biāo)通過與隨機網(wǎng)絡(luò)的差異程度，來衡量發(fā)現(xiàn)所發(fā)現(xiàn)網(wǎng)絡(luò)社團的模塊化程度，即網(wǎng)絡(luò)的社團化程度越高，社團結(jié)構(gòu)越明顯，其值越大，相應(yīng)地，通常認為社團檢測算法性能越好。同時，為對算法的效率進行分析，對真實網(wǎng)絡(luò)數(shù)據(jù)集上的運行時間，也進行了實驗分析。

4.4 實驗結(jié)果

1) LFR郵件網(wǎng)絡(luò)

在LFR人工網(wǎng)絡(luò)數(shù)據(jù)集上進行實驗，結(jié)果如圖3所示。由圖3(a)可知，本文所提的方法獲得了較高的NMI取值，且在不同的時刻，該值保持的比較穩(wěn)定。與其余3種算法相比，性能與A3CS大致相當(dāng)，但仍在大部分時刻取得了一定的優(yōu)勢，這說明了本文所提的方法更為準(zhǔn)確地挖掘不同時刻的社團結(jié)構(gòu)，驗證了算法的有效性。在圖3(b）中，隨著混合參數(shù)的增加，網(wǎng)絡(luò)結(jié)構(gòu)更為復(fù)雜，所有算法均出現(xiàn)了一定程度的檢測性能的降低，而本文所提方法仍能夠保持較高的NMI取值，即較好的檢測性能。說明了算法在針對更為復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)時，仍能夠使用。

2) Enron郵件網(wǎng)絡(luò)

在Enron網(wǎng)絡(luò)數(shù)據(jù)集上進行實驗，結(jié)果如圖4所示。由圖4(a)可知，在對Enron郵件網(wǎng)絡(luò)進行仿真時，隨著時間間隔的增加，本文所提算法SCD-NMF，相比于其他3種方法，均取得了較高的值，其中，僅對靜態(tài)圖進行社團檢測的方法，由于缺少相關(guān)的監(jiān)督信息，值最小，因此，本文算法更能適應(yīng)網(wǎng)絡(luò)的動態(tài)變化，更能有效挖掘網(wǎng)絡(luò)中存在的社團結(jié)構(gòu)信息。同時，郵件網(wǎng)絡(luò)的值較低，說明了該網(wǎng)絡(luò)的社團結(jié)構(gòu)化不是很明顯。由圖4(b)可知，隨著網(wǎng)絡(luò)規(guī)模的增大，本文所提的方法在運行時間上僅略高于A3CS方法，但要極大地低于其他2種基于矩陣分解的方法FaceNet和NMF，且隨著網(wǎng)絡(luò)規(guī)模的增加，算法的運行時間增加并不多。原因在于，基于NMF的社團發(fā)現(xiàn)，在算法運行時間上與單次迭代的時間和迭代次數(shù)相關(guān)，本文所提方法，由于結(jié)合了歷史監(jiān)督信息，極大地減少了算法的迭代次數(shù)，加快了算法收斂性，減少了運行時間。因此，算法運行效率較高。

3) arXiv電子引文網(wǎng)絡(luò)

在arXiv網(wǎng)絡(luò)數(shù)據(jù)集上進行實驗，結(jié)果如圖5所示。由圖5(a)可知，在對arXiv電子引文網(wǎng)絡(luò)進行仿真時，本文所提算法SCD-NMF，相比于其他3種方法，也同樣均取得了較高的值，其中僅對靜態(tài)圖進行社團檢測的方法，由于缺少相關(guān)的監(jiān)督信息，值下降的最為厲害，分析可知，隨著網(wǎng)絡(luò)規(guī)模的急速增加，網(wǎng)絡(luò)的社團結(jié)構(gòu)化越不明顯，此時，僅僅依靠對單個靜態(tài)圖的分析，難以有效反映社團結(jié)構(gòu)的變化。同時，算法在電子引文網(wǎng)絡(luò)上的值較高，說明了該網(wǎng)絡(luò)的社團結(jié)構(gòu)化較為明顯。由圖5(b)可知，本文所提的方法在運行時間上僅略高于A3CS方法，但要極大地低于其他2種基于矩陣分解的方法FaceNet和NMF，且隨著網(wǎng)絡(luò)規(guī)模的增加，算法的運行時間增加并不多，原因在圖4(b)的分析中已經(jīng)給出，驗證了利用歷史信息，能夠有效地減少迭代次數(shù)，提高了算法運行效率。

4) Facebook社交網(wǎng)絡(luò)

在Facebook網(wǎng)絡(luò)數(shù)據(jù)集上進行實驗，結(jié)果如圖6所示。由圖6(a)可知，由于本文社團檢測時，采用已知的賬戶進行采集數(shù)據(jù)，其Facebook社交網(wǎng)絡(luò)更具備社團化結(jié)構(gòu)，因此，隨著朋友的不斷加入，其值呈增加狀態(tài)。在不同的時刻上進行仿真可知，本文所提算法SCD-NMF，相比于其他3種方法，均取得了較高的值，且相比其他算法，本文所取得值增加幅度很大，原因在于，F(xiàn)acebook社交網(wǎng)絡(luò)的歷史信息起了很大的指導(dǎo)作用，即前一時刻的網(wǎng)絡(luò)連接——朋友信息，一般會保持下去，不會出現(xiàn)劇烈的斷連接情況，但其網(wǎng)絡(luò)變化仍劇烈，因為社團規(guī)模不斷增加，因此，其他3種方法取得的效果增加率小于本文所提算法。同時，由圖6(b)可知，本文所提的方法也具備了較高的運行效率，原因見圖3(b)的詳細分析。

5 結(jié)束語

本文從提升動態(tài)網(wǎng)絡(luò)社團檢測性能的角度出發(fā)，提出了一種基于非負矩陣分解的半監(jiān)督動態(tài)社團檢測方法SDCD-NMF，并通過真實網(wǎng)絡(luò)上的實驗驗證了本文的有效性。該方法有效提取了歷史時刻的網(wǎng)絡(luò)信息，并將其在同一個社團檢測架構(gòu)中進行融合分析，為動態(tài)網(wǎng)絡(luò)社團檢測提供了新的研究思路和框架，更有利于深入探索網(wǎng)絡(luò)的演變與發(fā)展規(guī)律。此外，動態(tài)變化的社會網(wǎng)絡(luò)，為社團檢測提供了更大規(guī)模和更多異構(gòu)的信息源（不同的鏈接關(guān)系、不同的節(jié)點屬性和多種信息來源等），如何有效應(yīng)對這種“異質(zhì)多源”的海量動態(tài)媒體數(shù)據(jù)，進而挖掘其中存在的社團結(jié)構(gòu)，將是下一步工作的研究重點。

[1] FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2010,486(3-5):75-174.

[2] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proc Natl Acad Sci, 2002, 99 (2002)：7821-7826.

[3] LUXBURG U. A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 17(4):395-416.

[4] YANG L, CAO X C, JIN D. A unified semi-supervised community detection framework using latent space graph regularization[J]. IEEE Transactions on Cybernetics, to Appear 2015, DOI: 10. 1109/TCYB. 2014. 2377154.

[5] ZHANG Z Y. Community structure detection in complex networks withpartial background information[J]. Europhys Lett, 2013, 101(4): Art. ID 48005.

[6] 郭昆, 郭文忠, 邱啟榮, 等. 基于局部近鄰傳播及用戶特征的社區(qū)識別算法[J]. 通信學(xué)報,2015, 36(2):2015035-1—2015035-12.

GUO K, GUO W Z, QIU Q R, et al. Community detection algorithm based on local affinity propagation and user profile[J]. Journal of Communications, 2015, 36(2):2015035-1—2015035-12.

[7] 衛(wèi)紅權(quán), 陳鴻昶, 劉力雄, 等. 基于強度排序的通信社區(qū)檢測算法[J]. 通信學(xué)報, 2014, 35(10): 165-170.

WEI H Q, CHEN H Q, LIU L X, et al. Communication community detection algorithm based on ranking of strength[J]. Journal of Communications, 2014, 35(10): 165-170.

[8] EUSTACE J, WANG X Y, CUI Y Z, et al. Overlapping community detection using neighborhood ratio matrix[J]. Physica A, 2015, 421(2015): 510-521.

[9] CHAKRABARTI D, KUMAR R, TOMKINS A S, et al. Evolutionary clustering[C]//The 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. c2006:554-560.

[10] CAZABET R, AMBLARD F. Dynamic community detection[M]. Encyclopedia of Social Network Analysis and Mining. Springer New York Press, 2014.

[11] CHARU A, KARTHIK S. Evolving network analysis: a survey[J]. ACM Computing Surveys, 2014, 47(1):1-36.

[12] LEE D D, SEUNG H S. Learning the parts of objects by non-negative matrix factorization[J]. Nature, 1999, 401(6755): 788-791

[13] LAI J H, WANG C D, YU P. Dynamic community detection in weighted graph streams[C]//The 2013 SIAM International Conference on Data Mining, c2013:151-161.

[14] CHENG Y, REGE M, DONG M, et al. Non-negative matrix factorization for semi-supervised data clustering[J]. Knowledge and Information Systems, 2008, 17(3): 355-379

[15] WANG H, NIE F P, HUANG H. Nonnegative matrix tri-factorization based high-order co-clustering and its fast implementation[C]// The 2011 SIAM International Conference on Data Mining. c2011: 774- 783.

[16] 尚凡華. 基于低秩結(jié)構(gòu)學(xué)習(xí)數(shù)據(jù)表示[D]. 西安: 西安電子科技大學(xué), 2012.

SHANG F H. The low rank structure learning based on data representation[D]. Xi’an: Xidian University, 2012.

[17] CAI D, HE X F, HAN J W, et al. Graph regularized non-negative matrix factorization for data representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 8(33): 1548-1560.

[18] SUN J M, PAPADIMITRIOU S, YU P S, et al. Graphscope: parameter-free mining of large time-evolving graphs[C]//The 13th ACM SIGKDD Int’l Conf on Knowledge Discovery and Data Mining. c2007: 687-696.

[19] 黃永鋒, 董永強, 張三峰, 等. 基于社會特征周期演化的機會移動網(wǎng)絡(luò)路由轉(zhuǎn)發(fā)策略[J]. 通信學(xué)報, 2015, 36(3): 2015055.

HUANG Y F, DONG Y Q, ZHANG S F, et al. Message forwarding based on periodically evolving social characteristics in opportunistic mobile networks[J]. Journal of Communications, 2015, 36(3): 2015055-1—2015055-12.

[20] NING H Z, XU W, CHI Y, et al. Incremental spectral clustering by efficiently updating the eigen-system[J]. Pattern Recognition, 2010, 43(1):113-127.

[21] 單波, 姜守旭, 張碩. IC: 動態(tài)社會關(guān)系網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的增量識別算法[J]. 軟件學(xué)報, 2009, 20(1): 184-192.

SHAN B, JINAG S X, ZHANG S. IC: incrementalalgorithm for community identification in dynamic socialnetworks[J]. Journal of Software, 2009, 20(1):184-192.

[22] 肖杰斌, 張紹武. 基于隨機游走和增量相關(guān)節(jié)點的動態(tài)網(wǎng)絡(luò)社團挖掘算法[J]. 電子與信息學(xué)報, 2013, 35(4):977-981.

XIAO J B, ZHANG S W. An algorithm of integrating random walk and increment correlative vertexes for mining community of dynamic networks[J]. Journal of Electronics & Information Technology, 2013, 35(4):977-981.

[23] 郭進時, 湯紅波, 王曉雷.基于社會網(wǎng)絡(luò)增量的動態(tài)社區(qū)組織探測[J]. 電子與信息學(xué)報, 2013, 35(9): 2240-2246.

GUO J S, TANG H B, WANG X L. A dynamic community structure detection scheme based on social network incremental[J]. Journal of Electronics & Information Technology, 2013, 35(9): 2240-2246.

[24] MIGUEL A, SPIROS P, STEPHAN G, et al. 1Com2: fast automatic discovery of temporal ('Comet') communities[C]//The PAKDD. c2014:271-283.

[25] NIGN H Z, XU W, CHI Y, et al. Incremental spectral clustering with application to monitoring of evolving blog communities[C]//The 2007 SIAM International Conference on Data Mining. c2007: 261-272.

[26] ROBERT G, TANJA H, DOROTHEA W. Dynamic graph clustering using minimum-cut trees[J]. Journal of Graph Algorithms and Applications, 2012, 16(2):411-446.

[27] DUAN D S, LI Y H, LI R X, et al. Incremental-clique clustering in dynamic social networks[J]. Artificial Intelligence, 2012, 38(2): 129-147.

[28] CHI Y, SONG X D, ZHOU D Y, et al. Evolutionary spectral clustering by incorporating temporal smoothness[C]//The 13th ACM International Conference on Knowledge Discovery and Data Mining. c2007: 153-162.

[29] LIN Y R, CHI Y, ZHU S H, et al. Analyzing communities and their evolutions in dynamic social networks[J]. ACM Transactions on Knowledge Discovery from Data, 2009, 3(2):8:1-8:31.

[30] THANG N D, NGUYEN N P, THAI M T. An adaptive approximation algorithm for community detection in dynamic scale-free networks[C]//The 2013 IEEE INFOCOM. c2013: 55-59.

[31] GORKE R, MAILLARD P, SCHUMM A, et al. Dynamic graph clustering combining modularity and smoothness[J]. ACM Journal of Experimental Algorithmics, 2013, 18(1):1.5:1.1-1.5:1.29.

[32] BECCHETTI L, BOLDI P, CASTILLLO C, et al. Efficient semi- streaming algorithms for local triangle counting in massive graphs[C]// The 14th ACM SIGKDD international conference on Knowledge discovery and data mining. c2008:16-24.

[33] KIM M S, HAN J W. A particle-and-density based evolutionary clustering method for dynamic networks[C]//The 35th International Conference on Very Large Databases. c2009:622-633.

[34] TANG L, LIU H, ZHANG J P. Identifying evolving groups in dynamic multimode networks[J]. IEEE Trans on Knowledge and Data Engineering, 2012, 24(1):72?85.

[35] XU KS, KLIGER M, HERO A O. Adaptive evolutionary clustering[J]. Data Mining and Knowledge Discover, 2014, 28(2): 304-336.

[36] MA H F, ZHAO W Z, SHI Z Z. A nonnegative matrix factorization framework for semi-supervised document clustering with dual constraints[J]. Knowledge and Information Systems September, 2013, 36(3):629-651.

[37] WASSERMAN S, FAUST K. Social network analysis: methods and applications[M]. Cambridge University Press, 1994.

[38] PALLA G, DETRNYI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(1):814-818.

[39] NEWMAN M. Spectral methods for network community detection and graph partitioning[J]. Phys Rev E, 2013, 88(4):042822:1-042822:11.

[40] AIROLDI E M, BLEI D M, FIENBERG S E, et al. Mixed membership stochastic block models[J]. J Mach Learn Res, 2009, 9(1):1981-2014.

[41] CHRISTOPHER M, MAES. A regularized active-set method roe sparse convex quadratic programming[M]. 2010 Ph D Dissertation Stanford university.

[42] WEBER M, RUNGSARITYOTIN W, SCHLIEP A. Perron cluster analysis and its connection to graph partitioning for noisy data[M]. Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2004.

[43] LANCICHINETTI A, FORTUNATO S. Community detection algorithms: a comparative analysis[J].Phys Rev E 2009, 80(5):733-737.

[44] SUN J, FALOUTSOS C, PAPADIMITRIOU S, et al. Graphscope: parameter-free mining of large time-evolving graphs[C]//The 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. c2007:687-696.

[45] ArXiv dataset[EB/OL]. http://www.cs.cornell.edu/projects/kddcup/ datasets.html. 2003.

[46] NGUYEN N P, DINH T N, XUAN Y, et al. Adaptive algorithms for detecting community structure in dynamic social networks[C]//The 2011 INFOCOM. c2011:2282-2290.

[47] VISWANATH B, MISLOVE A, CHA M, et al. On the evolution of user interaction in facebook[C]//The 2nd ACM workshop on Online social networks. c2009:37-42.

Semi-supervised dynamic community detection based on non-negative matrix factorization

CHANG Zhen-chao, CHEN Hong-chang, HUANG Rui-yang, YU Hong-tao, LIU Yang

(National Digital Switching System Engineering & Technological Research Center, Zhengzhou 450002, China)

How to effectively combine the network structures on different time points was the key and difficulty to affect the performance of detection algorithms. Based on this, a semi-supervised dynamic community algorithm SDCD based on non-negative matrix factorization, which effectively extracted the historical stability structure unit firstly, and then use it as a regularization item supervision of nonnegative matrix decomposition, to guide the network community detection on current moment. Experiments on the real network data sets show that the method has a higher community detection quality compared with existing methods, which can accurately mine the relationship among different time, and explore network evolution and the law of development more advantageously.

semi-supervised, dynamic, community detection, non-negative matrix factorization

TN915.0

A

10.11959/j.issn.1000-436x.2016039

2015-07-15；

2015-11-06

國家自然科學(xué)基金資助項目（No.61171108）；國家重點基礎(chǔ)研究發(fā)展計劃基金資助項目（No.2012CB315901, No. 2012CB315905）；國家科技支撐計劃基金資助項目（No.2014BAH30B01）

The National Natural Science Foundation of China (No. 61171108), The State Key Development Program for Basic Research of China (No. 2012CB315901, No. 2012CB315905), The National Key Technology R&D Program (No.2014BAH30B01)

常振超（1987-），男，河北邯鄲人，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心博士生，主要研究方向為社會網(wǎng)絡(luò)結(jié)構(gòu)分析。

陳鴻昶（1964-），男，河南鄭州人，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心教授、博士生導(dǎo)師，主要研究方向為社會網(wǎng)絡(luò)分析。

黃瑞陽（1986-），男，福建漳州人，博士，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心講師，主要研究方向為社會網(wǎng)絡(luò)分析。

于洪濤（1970-），男，河南鄭州人，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心教授、碩士生導(dǎo)師，主要研究方向為社會網(wǎng)絡(luò)分析。

劉陽（1986-），男，湖北隨州人，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心博士生，主要研究方向為社會網(wǎng)絡(luò)分析。