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

?

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

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

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

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

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

1 引言

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

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

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

2 相關工作

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

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

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

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

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

2.3 已有算法分析

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

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

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

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

3.1 相關定義及分析

3.2 非負矩陣分解

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

3.3 約束信息獲取

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

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

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

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

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

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

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

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

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

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

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

(5)

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

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

算法2 融合多屬性算法

5) while not convergent do

8) end while

9) end for

在算法2中，首先經過初始化矩陣，通過前一時刻的網絡社團中約束信息獲取，指導當前時刻的社團劃分，矩陣運算過程中，固定其中2個變量，然后反復迭代運算，直到目標函數收斂，以求得和。

3.5 模型選擇

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

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

(6)

本文所提模型選擇方法用于提前確立不同時刻網絡結構中的社團數目，其獨立于社團檢測過程。

3.6 復雜度分析

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

4 實驗

為驗證本文所提算法的有效性，本文在真實網絡數據集上進行了相關的實驗，并對實驗結果進行了分析。

4.1 實驗數據

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

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

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

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

Facebook社交網絡[47]：該數據集包含了Facebook網絡中新奧爾良區(qū)域內注冊用戶之間的朋友關系，時間為2006年9月~2009年1月。數據集包含了6萬個節(jié)點，150萬個連接關系。本文中數據采用2006年9月~2006年12月的數據作為原始網絡數據。按照時間刻度每個月構造靜態(tài)圖。從2007年1月~2009年1月總共構造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]，該方法基于生成模型進行演化分析，首次將矩陣分解應用到此類問題中來，其針對歷史時刻和當前時刻分別進行聯(lián)合估計獲取社團劃分，采用平衡因子將兩者劃分進行統(tǒng)一，取得了較好的效果，是常用于對比算法中的經典算法。3）A3CS[30]，該方法是動態(tài)社團檢測中提出較新的算法，其從保證模塊度最大化的角度出發(fā)，取得了較好的識別效果和較高的算法運行效率。

4.3 評價指標

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

4.4 實驗結果

1) LFR郵件網絡

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

2) Enron郵件網絡

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

3) arXiv電子引文網絡

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

4) Facebook社交網絡

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

5 結束語

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

[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]. 通信學報,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)紅權, 陳鴻昶, 劉力雄, 等. 基于強度排序的通信社區(qū)檢測算法[J]. 通信學報, 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] 尚凡華. 基于低秩結構學習數據表示[D]. 西安: 西安電子科技大學, 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] 黃永鋒, 董永強, 張三峰, 等. 基于社會特征周期演化的機會移動網絡路由轉發(fā)策略[J]. 通信學報, 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)社會關系網絡社區(qū)結構的增量識別算法[J]. 軟件學報, 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] 肖杰斌, 張紹武. 基于隨機游走和增量相關節(jié)點的動態(tài)網絡社團挖掘算法[J]. 電子與信息學報, 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] 郭進時, 湯紅波, 王曉雷.基于社會網絡增量的動態(tài)社區(qū)組織探測[J]. 電子與信息學報, 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

國家自然科學基金資助項目（No.61171108）；國家重點基礎研究發(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-），男，河北邯鄲人，國家數字交換系統(tǒng)工程技術研究中心博士生，主要研究方向為社會網絡結構分析。

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

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

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

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