基于非負(fù)矩陣分解的半監(jiān)督動(dòng)態(tài)社團(tuán)檢測(cè)

常振超，陳鴻昶，黃瑞陽(yáng)，于洪濤，劉陽(yáng)

?

基于非負(fù)矩陣分解的半監(jiān)督動(dòng)態(tài)社團(tuán)檢測(cè)

常振超，陳鴻昶，黃瑞陽(yáng)，于洪濤，劉陽(yáng)

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

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

半監(jiān)督；動(dòng)態(tài)；社團(tuán)檢測(cè)；非負(fù)矩陣分解

1 引言

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

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

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

2 相關(guān)工作

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

2.1 基于增量聚類(lèi)的動(dòng)態(tài)社團(tuán)檢測(cè)

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

2.2 基于進(jìn)化聚類(lèi)的動(dòng)態(tài)社團(tuán)檢測(cè)

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

2.3 已有算法分析

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

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

3 半監(jiān)督動(dòng)態(tài)社團(tuán)檢測(cè)

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

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

3.2 非負(fù)矩陣分解

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

3.3 約束信息獲取

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

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

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

1) must-link約束：即下一時(shí)刻為圖2(a)時(shí)，3個(gè)節(jié)點(diǎn)中兩兩滿(mǎn)足仍為成對(duì)約束情況。

2) must-link約束傳遞：即下一時(shí)刻為圖2(b)時(shí)，通過(guò)2個(gè)邊的連接擴(kuò)展，補(bǔ)充到第3條邊的連接情況，即滿(mǎn)足成對(duì)約束的傳遞性。

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

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

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

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

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

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

(5)

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

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

算法2 融合多屬性算法

5) while not convergent do

8) end while

9) end for

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

3.5 模型選擇

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

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

(6)

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

3.6 復(fù)雜度分析

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

4 實(shí)驗(yàn)

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

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

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

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

4.2 對(duì)比算法

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

4.3 評(píng)價(jià)指標(biāo)

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

4.4 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

[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] 郭昆, 郭文忠, 邱啟榮, 等. 基于局部近鄰傳播及用戶(hù)特征的社區(qū)識(shí)別算法[J]. 通信學(xué)報(bào),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), 陳鴻昶, 劉力雄, 等. 基于強(qiáng)度排序的通信社區(qū)檢測(cè)算法[J]. 通信學(xué)報(bào), 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] 黃永鋒, 董永強(qiáng), 張三峰, 等. 基于社會(huì)特征周期演化的機(jī)會(huì)移動(dòng)網(wǎng)絡(luò)路由轉(zhuǎn)發(fā)策略[J]. 通信學(xué)報(bào), 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: 動(dòng)態(tài)社會(huì)關(guān)系網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的增量識(shí)別算法[J]. 軟件學(xué)報(bào), 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] 肖杰斌, 張紹武. 基于隨機(jī)游走和增量相關(guān)節(jié)點(diǎn)的動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)挖掘算法[J]. 電子與信息學(xué)報(bào), 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] 郭進(jìn)時(shí), 湯紅波, 王曉雷.基于社會(huì)網(wǎng)絡(luò)增量的動(dòng)態(tài)社區(qū)組織探測(cè)[J]. 電子與信息學(xué)報(bào), 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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61171108）；國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金資助項(xiàng)目（No.2012CB315901, No. 2012CB315905）；國(guó)家科技支撐計(jì)劃基金資助項(xiàng)目（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-），男，河北邯鄲人，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心博士生，主要研究方向?yàn)樯鐣?huì)網(wǎng)絡(luò)結(jié)構(gòu)分析。

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

黃瑞陽(yáng)（1986-），男，福建漳州人，博士，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心講師，主要研究方向?yàn)樯鐣?huì)網(wǎng)絡(luò)分析。

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

劉陽(yáng)（1986-），男，湖北隨州人，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心博士生，主要研究方向?yàn)樯鐣?huì)網(wǎng)絡(luò)分析。