伊 鵬 周 橋 門浩崧

1(國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 鄭州 450001) 2(中華人民共和國(guó)科學(xué)技術(shù)部信息中心 北京 100000)

(15238363586@139.com)

基于HMM的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法

伊 鵬1周 橋1門浩崧2

1(國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 鄭州 450001)2(中華人民共和國(guó)科學(xué)技術(shù)部信息中心 北京 100000)

(15238363586@139.com)

隨著互聯(lián)網(wǎng)的不斷發(fā)展，大多數(shù)社會(huì)網(wǎng)絡(luò)已逐漸顯示出動(dòng)態(tài)特性，動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)社團(tuán)分析對(duì)理解現(xiàn)實(shí)生活中社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)和功能具有非常重要的意義.針對(duì)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)問(wèn)題，提出一種基于隱Markov模型(hidden Markov model, HMM)的HMM_DC算法.該算法考慮到社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)特性，結(jié)合歷史信息，將社團(tuán)發(fā)現(xiàn)轉(zhuǎn)化為求解隱馬爾可夫模型中的最優(yōu)狀態(tài)序列問(wèn)題，將網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)和節(jié)點(diǎn)信息分別采用狀態(tài)鏈和觀察鏈表示，在無(wú)須指定額外參數(shù)的情況下實(shí)現(xiàn)動(dòng)態(tài)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn).最后，利用該算法和其他算法對(duì)VAST數(shù)據(jù)集、ENRON數(shù)據(jù)集和Facebook social network數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)仿真.仿真結(jié)果表明：該算法能夠快速、準(zhǔn)確地發(fā)現(xiàn)真實(shí)動(dòng)態(tài)網(wǎng)絡(luò)中的社團(tuán)，其模塊度Q值和互信息NMI值有很大提升.

動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)；隱Markov模型；最優(yōu)狀態(tài)序列；社團(tuán)結(jié)構(gòu)；社團(tuán)發(fā)現(xiàn)

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，各類新型的關(guān)于社會(huì)網(wǎng)絡(luò)的應(yīng)用層出不窮，并且發(fā)揮著日益重要的作用，社會(huì)網(wǎng)絡(luò)已成為人們?nèi)粘Ｉ钪胁豢苫蛉钡囊徊糠?在許多現(xiàn)實(shí)和人工的系統(tǒng)中，社會(huì)網(wǎng)絡(luò)分析是用來(lái)研究系統(tǒng)結(jié)構(gòu)和功能特性的主要手段.近年來(lái)，對(duì)眾多實(shí)際復(fù)雜網(wǎng)絡(luò)的研究發(fā)現(xiàn)，社會(huì)網(wǎng)絡(luò)普遍存在著社團(tuán)結(jié)構(gòu)這一特性[1-2].同一社團(tuán)內(nèi)成員之間具有共同的屬性或者在網(wǎng)絡(luò)中扮演著相似的角色，聯(lián)系相對(duì)頻繁，社團(tuán)間成員聯(lián)系則相對(duì)稀疏.發(fā)現(xiàn)和研究網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)對(duì)于了解網(wǎng)絡(luò)的內(nèi)部組織結(jié)構(gòu)和網(wǎng)絡(luò)功能具有非常重要的意義，可以分析和挖掘社會(huì)網(wǎng)絡(luò)內(nèi)部所隱含的模式與信息.目前很多算法用于發(fā)現(xiàn)社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu),如基于標(biāo)簽傳播算法[3]、基于模塊度優(yōu)化[4]的算法以及用于發(fā)現(xiàn)網(wǎng)絡(luò)中重疊社團(tuán)結(jié)構(gòu)的算法[5-6].值得指出的是，隨著對(duì)社會(huì)網(wǎng)絡(luò)研究的深入，研究者發(fā)現(xiàn)在現(xiàn)實(shí)生活中，大多數(shù)社會(huì)網(wǎng)絡(luò)都具有動(dòng)態(tài)特性，網(wǎng)絡(luò)中的個(gè)體隨著時(shí)間的推移而增加或者減少，如圖1所示.通過(guò)對(duì)動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)特性的研究，對(duì)理解現(xiàn)實(shí)生活中社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)和功能具有非常重要的意義.

Fig. 1 Community structure in dynamic social network圖1 動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)

1 相關(guān)工作

目前關(guān)于發(fā)現(xiàn)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)已經(jīng)有了很多成果.一種主流的對(duì)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的結(jié)構(gòu)變化情況進(jìn)行挖掘的方法是將發(fā)生演化的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)轉(zhuǎn)化為不同時(shí)刻的靜態(tài)社會(huì)網(wǎng)絡(luò)，如Berger-Wolf等人[7]提出一種分析動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)框架.該方法著重研究社團(tuán)結(jié)構(gòu)的演化特性，主要關(guān)注3個(gè)方面：1)社會(huì)網(wǎng)絡(luò)中的結(jié)構(gòu)特性；2)發(fā)現(xiàn)社會(huì)網(wǎng)絡(luò)中交互關(guān)系的變化；3)預(yù)測(cè)社會(huì)網(wǎng)絡(luò)的未來(lái)趨勢(shì).動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的社團(tuán)演化情況可以通過(guò)社團(tuán)結(jié)構(gòu)中重大事件的變化來(lái)進(jìn)行分析，如文獻(xiàn)[8]提出的分析動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的Social Cost模型，將動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)問(wèn)題轉(zhuǎn)化為圖的著色問(wèn)題，但是該方法只關(guān)注特定個(gè)體的演化關(guān)系.雖然基于上述模型，動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)問(wèn)題得到了較好的解決，但仍然存在復(fù)雜度較大的問(wèn)題.因此，為了減少?gòu)?fù)雜度，提出了其他動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)算法，如Sun等人[9]提出一種基于信息論的算法GraphScope，用來(lái)發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)和檢測(cè)動(dòng)態(tài)網(wǎng)絡(luò)中發(fā)生變化的個(gè)體而無(wú)需輸入任何參數(shù).文獻(xiàn)[10]提出一種用于發(fā)現(xiàn)動(dòng)態(tài)有向加權(quán)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的算法.Nguyen等人[11]提出一種自適應(yīng)增量算法用于發(fā)現(xiàn)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，對(duì)網(wǎng)絡(luò)中變化的點(diǎn)和邊信息進(jìn)行處理，以及文獻(xiàn)[12-20]提出了其他相關(guān)的動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)方法.

雖然上述方法各有優(yōu)點(diǎn)，在某些數(shù)據(jù)集上表現(xiàn)出較好的計(jì)算性能和準(zhǔn)確性，但這些算法只是單獨(dú)對(duì)每個(gè)時(shí)刻的網(wǎng)絡(luò)快照進(jìn)行社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)，從而找尋各個(gè)時(shí)刻社團(tuán)結(jié)構(gòu)之間的演化關(guān)系，忽略了動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中不同時(shí)刻之間的影響關(guān)系.在動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中，當(dāng)前時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu)信息與前一時(shí)刻或者前幾個(gè)時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu)信息是相關(guān)的，前一時(shí)刻的社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)對(duì)當(dāng)前時(shí)刻社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)存在著影響，而之前的動(dòng)態(tài)算法忽略了歷史信息對(duì)當(dāng)前時(shí)刻網(wǎng)絡(luò)結(jié)構(gòu)的影響，使得社團(tuán)結(jié)構(gòu)的準(zhǔn)確性和穩(wěn)定性偏低.

針對(duì)上述動(dòng)態(tài)算法存在的問(wèn)題，基于圖理論，從隱Markov鏈模型[21](hidden Markov model, HMM)出發(fā)，本文提出一種基于HMM的動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)方法HMM_DC.該方法引入HMM描述社團(tuán)結(jié)構(gòu)與網(wǎng)絡(luò)中個(gè)體間的相互作用，將網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)和節(jié)點(diǎn)信息分別采用狀態(tài)鏈和觀察鏈表示，通過(guò)求解HMM中的最優(yōu)狀態(tài)序列實(shí)現(xiàn)動(dòng)態(tài)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn).應(yīng)用于真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果表明，該模型能夠在無(wú)須指定額外參數(shù)的情況下，快速有效地發(fā)現(xiàn)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)內(nèi)在的社團(tuán)結(jié)構(gòu)，其模塊度Q值和互信息NMI值得到很大提升.

2 模型建立

如圖2所示，HMM是一種描述隨機(jī)過(guò)程統(tǒng)計(jì)特性的概率模型，是一種雙重隨機(jī)過(guò)程，由2個(gè)部分組成：Markov鏈和一般隨機(jī)過(guò)程.其中Markov鏈用轉(zhuǎn)移概率來(lái)描述狀態(tài)的轉(zhuǎn)移.一般隨機(jī)過(guò)程用觀察值概率來(lái)描述狀態(tài)與觀察序列間的關(guān)系.

Fig. 2 Example of the HMM model圖2 HMM 模型示例

本文將動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)按照時(shí)間粒度劃分為多個(gè)網(wǎng)絡(luò)快照，動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)可由多個(gè)時(shí)刻的靜態(tài)網(wǎng)絡(luò)表示.假定相鄰時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu)相關(guān)，對(duì)不同時(shí)刻社會(huì)網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的關(guān)系可用一階Markov鏈描述，由于社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)不能夠被直接觀察到，因此，引入隱Markov模型將不同時(shí)刻社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)描述為HMM中的狀態(tài)鏈.將社會(huì)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)度分布描述為觀察鏈.采用隱Markov模型描述動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)問(wèn)題，求解隱Markov中的最優(yōu)狀態(tài)序列得到社團(tuán)結(jié)構(gòu)，可以更好地理解動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)演化情況.相比于當(dāng)前動(dòng)態(tài)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)方法，本文在考慮前一時(shí)刻社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)信息對(duì)當(dāng)前時(shí)刻網(wǎng)絡(luò)結(jié)構(gòu)信息影響的前提下，將社會(huì)網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)問(wèn)題轉(zhuǎn)化為隱Markov模型中的最優(yōu)狀態(tài)序列的求解問(wèn)題.對(duì)于動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)，其社團(tuán)結(jié)構(gòu)不能夠直接被觀測(cè)出來(lái)，而社會(huì)網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)度等屬性信息是可以直接觀測(cè)的.因此，結(jié)合HMM模型特性和上述動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)的特性，提出了一種HMM_DC方法用于解決動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)問(wèn)題.

為了得到隱Markov模型中的最優(yōu)狀態(tài)序列，本文采用Viterbi算法[25].Viterbi算法是一種動(dòng)態(tài)規(guī)劃算法，即給出一個(gè)觀測(cè)序列O1,O2,O3,…，找到觀測(cè)序列背后的隱藏狀態(tài)S1,S2,S3,…，由動(dòng)態(tài)規(guī)劃尋找出現(xiàn)概率最大的隱藏狀態(tài)序列.

隱Markov模型作為一種具有統(tǒng)計(jì)特性的概率模型，從統(tǒng)計(jì)意義的角度來(lái)描述動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)過(guò)程.現(xiàn)實(shí)生活中，社會(huì)網(wǎng)絡(luò)往往有可能存在著噪聲，當(dāng)前動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)方法在噪聲的影響下使得結(jié)果的準(zhǔn)確性降低，但是Viterbi算法會(huì)查看整個(gè)序列來(lái)決定最可能的終止?fàn)顟B(tài)，然后通過(guò)后向指針來(lái)找到之前的狀態(tài)，這對(duì)忽略孤立的噪聲非常有用，因此該算法對(duì)于含有噪聲的社會(huì)網(wǎng)絡(luò)同樣適用.

3 算法描述

3.1相關(guān)定義

社會(huì)網(wǎng)絡(luò)通常被抽象成圖，用G=(V,E)來(lái)表示社會(huì)網(wǎng)絡(luò).V表示社會(huì)網(wǎng)絡(luò)中個(gè)體集合，|V|表示網(wǎng)絡(luò)中個(gè)體的總數(shù)；E表示社會(huì)網(wǎng)絡(luò)中個(gè)體間的連接關(guān)系集合，|E|表示社會(huì)網(wǎng)絡(luò)中個(gè)體間連接關(guān)系集合中元素的總數(shù).

如定義1所示，大多數(shù)研究動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的方法都是將動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)G劃分成多個(gè)時(shí)序圖GS來(lái)進(jìn)行研究.在結(jié)合時(shí)刻t的時(shí)序圖GSt僅與前一時(shí)刻的時(shí)序圖GSt-1相關(guān)這一特性的情況下，建立隱Markov模型來(lái)發(fā)現(xiàn)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，給出如下定義.

定義3. 可觀察序列O.基于動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)，定義隱Markov模型中的觀察序列為網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)度大小.觀察序列O=(d1,d2,…,dt,…,dM)，M是從每一狀態(tài)可能輸出的不同的觀察值數(shù)目，dt為時(shí)刻t的某個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)度.

3.2HMM模型參數(shù)

ai j=P{qt+1=Cj|qt=Ci},1≤i,j≤NC,

(1)

表示在時(shí)刻t的狀態(tài)為Ci、時(shí)刻t+1的狀態(tài)為Cj的概率.B為狀態(tài)j的觀察概率矩陣，B=(bj(k))，表示狀態(tài)j輸出相應(yīng)觀察值的概率，其中：

bj(k)=P(Ot=dk|qt=Cj),1≤j≤NC,1≤k≤M.

(2)

為了得到狀態(tài)轉(zhuǎn)移概率矩陣A和觀察概率矩陣B，分別給出如下定義.

設(shè)x和y是二元向量，且x=(x1,x2,…,xn),y=(y1,y2,…,yn)，則x和y向量之間的相似度可定義為

(3)

(4)

(5)

其中，i∈V.

在給出觀察概率p_observe之前，先給出一個(gè)隸屬函數(shù)[7]Com(i,C)的定義.隸屬函數(shù)的物理意義是：社會(huì)網(wǎng)絡(luò)的鄰接矩陣R中節(jié)點(diǎn)i隸屬于某個(gè)群組C的程度：

(6)

定義6. 觀察概率p_observe.給定節(jié)點(diǎn)與各個(gè)社團(tuán)之間的隸屬度Com(i,Cj),j∈(1,NC)，矩陣中的觀察概率為

(7)

3.3HMM_DC算法描述

3.2節(jié)給出了隱Markov模型參數(shù)的定義，本節(jié)基于隱Markov模型介紹發(fā)現(xiàn)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)的HMM_DC算法.

HMM_DC算法的基本思想為：相比于其他算法，本算法充分考慮了動(dòng)態(tài)網(wǎng)絡(luò)中前一時(shí)刻網(wǎng)絡(luò)結(jié)構(gòu)對(duì)當(dāng)前時(shí)刻網(wǎng)絡(luò)結(jié)構(gòu)的影響以及網(wǎng)絡(luò)中節(jié)點(diǎn)和社團(tuán)結(jié)構(gòu)的固有特點(diǎn)，建立隱Markov模型來(lái)解決動(dòng)態(tài)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)問(wèn)題.在當(dāng)前時(shí)刻受到前一時(shí)刻網(wǎng)絡(luò)結(jié)構(gòu)影響的前提下，基于隱Markov鏈模型描述社團(tuán)結(jié)構(gòu)與網(wǎng)絡(luò)個(gè)體間的相互關(guān)系，采用狀態(tài)鏈和觀察鏈分別表示網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)和節(jié)點(diǎn)信息，通過(guò)求解隱Markov鏈模型中的最優(yōu)狀態(tài)序列得到動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu).圖3給出HMM_DC算法模型實(shí)現(xiàn)框架.

Fig. 3 Algorithm model framework圖3 算法模型框架

HMM_DC算法的具體步驟如下：

令時(shí)序圖GSi中的個(gè)體表示為(x1,x2,…,xN).

步驟1. 基于靜態(tài)算法[4]，對(duì)時(shí)序圖GS1進(jìn)行社團(tuán)挖掘，得到初始社團(tuán)結(jié)構(gòu)C_ini.

步驟2. 對(duì)于時(shí)序圖GS1中的節(jié)點(diǎn)，假定其初始狀態(tài)概率分布為隨機(jī)分布，即認(rèn)為某個(gè)節(jié)點(diǎn)在初始時(shí)刻進(jìn)入到某個(gè)社團(tuán)的概率是隨機(jī)的，得到初始時(shí)刻的狀態(tài)概率分布為p_initial.

步驟5. 依照表達(dá)式(5)求得時(shí)刻t的各個(gè)狀態(tài)轉(zhuǎn)移概率p_trans_state.

步驟6. 得到時(shí)序圖中每個(gè)個(gè)體xi與每個(gè)社團(tuán)結(jié)構(gòu)的隸屬度.

步驟7. 對(duì)每個(gè)個(gè)體xi采用表達(dá)式(6)得到社會(huì)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)隸屬于各個(gè)社團(tuán)的隸屬度，再采用表達(dá)式(7)得到觀察概率.

(8)

步驟8. 采用Viterbi算法來(lái)得到最優(yōu)狀態(tài)序列，即時(shí)刻t網(wǎng)絡(luò)的最優(yōu)社團(tuán)結(jié)構(gòu)，令t=t+1.

HMM_DC算法偽代碼如算法1所示：

算法1. HMM_DC算法.

輸入：GSt、GSt+1、初始社團(tuán)結(jié)構(gòu)；

輸出：時(shí)刻t+1最優(yōu)社團(tuán)結(jié)構(gòu)Ct+1.

① 初始化：

len=length(GSt)，

NBC=zeros(len,NC)，

Π=p_initial=Rand(1,NC)；

②for1≤i≤len

③ NBC(i,C(i))=1；

④endfor

⑤for1≤j≤NC

⑥ 找出每個(gè)社團(tuán)結(jié)構(gòu)的核心節(jié)點(diǎn)NCore；

⑦endfor

⑧for1≤i1≤len

⑨for1≤j1≤NC

⑩ 求出相似度Sim(i1,NCore)；

3.4算法復(fù)雜度分析

如算法1所示，n為網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目，m代表網(wǎng)絡(luò)中邊的數(shù)目，NC為初始社團(tuán)個(gè)數(shù)，行②～④的復(fù)雜度為O(n)，雖然行⑤～⑦代碼是針對(duì)每個(gè)社團(tuán)進(jìn)行操作，但最終仍是對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行處理，故復(fù)雜度為O(n)；行⑨～的復(fù)雜度為O(n×NC)；Viterbi算法采用遞歸調(diào)用，其算法復(fù)雜度為O(n2×lgn)；故該算法的復(fù)雜度為O(n)+O(n2×NC)+O(n2×lgn).對(duì)于均勻網(wǎng)絡(luò)，即在該網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)不明顯，社團(tuán)個(gè)數(shù)NC近似于網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)，針對(duì)該種網(wǎng)絡(luò)算法的復(fù)雜度為O(n2×NC)；對(duì)于結(jié)構(gòu)比較明顯的網(wǎng)絡(luò)，由4.1節(jié)給出的數(shù)據(jù)集統(tǒng)計(jì)得到表1.

Tabel 1 Data Set Statistics表1 數(shù)據(jù)集統(tǒng)計(jì)

由表1可知，平均社團(tuán)個(gè)數(shù)NC要遠(yuǎn)小于節(jié)點(diǎn)數(shù)，且lgn?NC，故此種情況下，算法的復(fù)雜度為O(n2×NC).綜上所述，HMM_DC算法的時(shí)間復(fù)雜度為O(n2×NC).

4 仿真結(jié)果及分析

為了驗(yàn)證該模型的有效性，本文將分別與CDBIA[22], QCA[11], MIEN[23]算法進(jìn)行對(duì)比，仿真實(shí)驗(yàn)環(huán)境為：8 GB內(nèi)存，3.2 GHz Intel Core i7處理器，Matlab R2015b集成環(huán)境，Mysql 5.6數(shù)據(jù)庫(kù).CDBIA算法是一種增量社團(tuán)發(fā)現(xiàn)方法，將動(dòng)態(tài)網(wǎng)絡(luò)中的變化信息轉(zhuǎn)變?yōu)辄c(diǎn)與邊的變化信息進(jìn)行處理得到不同時(shí)刻的社團(tuán)結(jié)構(gòu)；QCA算法是一種自適應(yīng)無(wú)監(jiān)督的用于發(fā)現(xiàn)動(dòng)態(tài)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的算法，分別對(duì)網(wǎng)中的變化信息進(jìn)行處理得到各個(gè)時(shí)刻的社團(tuán)結(jié)構(gòu)；MIEN算法將網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行壓縮和解壓縮來(lái)描述網(wǎng)絡(luò)中的變化信息，并采用快速模塊度方法來(lái)更新社團(tuán)結(jié)構(gòu).

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

為了測(cè)試提出的算法在實(shí)際數(shù)據(jù)集上的效果，采用VAST數(shù)據(jù)集、ENRON數(shù)據(jù)集和Facebook social network數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)仿真.VAST數(shù)據(jù)集來(lái)自IEEE VAST 2008，是一個(gè)開放的競(jìng)賽項(xiàng)目的數(shù)據(jù)集,它包括一組共400人的10 d的通話數(shù)據(jù)；ENRON郵件網(wǎng)絡(luò)數(shù)據(jù)集是來(lái)自ENRON公司內(nèi)部的郵件聯(lián)系網(wǎng)絡(luò)，包含用戶郵件消息的網(wǎng)絡(luò)數(shù)據(jù)集，其時(shí)間跨度為1999-05—2002-03;Facebook social network數(shù)據(jù)集[24]是一組2006-09—2009-01期間Facebook中的好友關(guān)系數(shù)據(jù)集.

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

為了對(duì)社團(tuán)結(jié)構(gòu)結(jié)果進(jìn)行評(píng)價(jià)，采用互信息值NMI[25]、模塊度Q函數(shù)[26]來(lái)進(jìn)行評(píng)價(jià).其中，NMI函數(shù)用來(lái)描述發(fā)現(xiàn)的社團(tuán)結(jié)構(gòu)結(jié)果與真實(shí)劃分結(jié)果之間的相似性，它將互信息的值除以由計(jì)算互信息的雙方信息量所決定的量；模塊度Q函數(shù)定量地描述網(wǎng)絡(luò)中的社團(tuán)，衡量網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的劃分，通過(guò)比較網(wǎng)絡(luò)中各社團(tuán)的邊密度和隨機(jī)網(wǎng)絡(luò)中對(duì)應(yīng)子圖邊密度之間的差異來(lái)度量社團(tuán)結(jié)構(gòu)的顯著性.

給定網(wǎng)絡(luò)中真實(shí)社團(tuán)U以及其劃分結(jié)果V，定義N為混淆矩陣，其中行為真實(shí)社團(tuán)，列為劃分所得社團(tuán)，Ni·為矩陣N中第i行的和，N·j為矩陣N中第j列的和，真實(shí)社團(tuán)中的個(gè)數(shù)為CU，劃分結(jié)果的社團(tuán)數(shù)為CV.則NMI(U,V)定義為

(9)

在每個(gè)時(shí)間粒度劃分得到的所有社團(tuán)中，找到能夠被其結(jié)構(gòu)中的任一社團(tuán)所包含的規(guī)模最大的 社團(tuán).以此社團(tuán)為真實(shí)社團(tuán)，頂點(diǎn)數(shù)超過(guò)此社團(tuán)中的頂點(diǎn)都被視為錯(cuò)誤劃分，小于此標(biāo)準(zhǔn)的社團(tuán)則只將不在真實(shí)社團(tuán)中的頂點(diǎn)視為錯(cuò)誤劃分.

模塊度是由Newman和Girvan提出的一種用于評(píng)價(jià)劃分結(jié)果的重要指標(biāo)[26]，Q函數(shù)定義為

(10)

其中，m為邊的數(shù)目;kυ,kω為節(jié)點(diǎn)υ,ω的節(jié)點(diǎn)度;Aυ ω為鄰接矩陣A中的元素;cυ,cω是節(jié)點(diǎn)υ,ω所屬的社團(tuán).

4.3仿真結(jié)果

1) VAST數(shù)據(jù)集.對(duì)該數(shù)據(jù)集作如下處理：以每一天為一個(gè)時(shí)間粒度，得到10個(gè)時(shí)刻的時(shí)序圖，對(duì)所得到的時(shí)序圖采用HMM_DC算法，得到結(jié)果如圖4～6所示：

Fig. 4 NMI values of VAST data set圖4 VAST數(shù)據(jù)集的NMI值

Fig. 5 Q values of VAST data set圖5 VAST數(shù)據(jù)集的Q值

Fig. 6 Runtime of VAST data set圖6 VAST數(shù)據(jù)集的運(yùn)行時(shí)間

圖4～6分別為HMM_DC算法模型在VAST數(shù)據(jù)集中NMI值和模塊度Q值以及運(yùn)行時(shí)間的曲線圖.在圖4中，雖然在第2個(gè)時(shí)刻互信息NMI值降低了0.08，但是在整體上提高了40%.在圖5中，HMM_DC算法要明顯優(yōu)于其他算法.由于HMM_DC算法考慮了所有節(jié)點(diǎn)在前一時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu)對(duì)當(dāng)前時(shí)刻的影響信息，而且基于隱Markov模型的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)方法采用了Viterbi算法求得最終的社團(tuán)結(jié)構(gòu)，避免了網(wǎng)絡(luò)中噪聲對(duì)算法性能的影響，所以得到的社團(tuán)結(jié)構(gòu)是全局最優(yōu)的，因此HMM_DC算法相比于其他算法在NMI值和模塊度Q值上表現(xiàn)都較為良好.由圖6可知HMM_DC算法的效率要更優(yōu).

2) ENRON數(shù)據(jù)集.對(duì)該數(shù)據(jù)集作如下處理:以每個(gè)月為一個(gè)時(shí)間粒度，對(duì)該數(shù)據(jù)集進(jìn)行劃分，分別得到各個(gè)時(shí)序圖，對(duì)每個(gè)時(shí)刻的時(shí)序圖采用HMM_DC算法，得到結(jié)果如圖7～9所示.圖7～9分別為HMM_DC算法模型在ENRON郵件網(wǎng)絡(luò)中的NMI值和模塊度Q值,NMI值和Q值均大于0.5，整體提高了28%.可以看出，由于HMM_DC算法得到的社團(tuán)結(jié)構(gòu)是全局最優(yōu)的，因此其NMI值和Q值都較優(yōu).從圖8中可以看出，在第8，9時(shí)刻本文算法模塊度值為0.53和0.535，略低于MIEN算法，準(zhǔn)確性較差.這是由于這段時(shí)間在ENRON公司中公司內(nèi)部員工之間的郵件數(shù)減少，使得時(shí)序圖變的較為稀疏，導(dǎo)致結(jié)果略有所降低，然而整體性能相比于其他算法要好很多.由圖9可知，相比于其他2個(gè)算法，HMM_DC算法在算法效率上更優(yōu).

Fig. 7 NMI values of ENRON data set圖7 ENRON數(shù)據(jù)集的NMI值

Fig. 9 Runtime of ENRON data set圖9 ENRON數(shù)據(jù)集的運(yùn)行時(shí)間

Fig. 10 NMI values of Facebook data set圖10 Facebook數(shù)據(jù)集的NMI值

3) Facebook數(shù)據(jù)集.對(duì)該數(shù)據(jù)集作如下處理:以每一個(gè)月為一個(gè)時(shí)間粒度，對(duì)該數(shù)據(jù)集進(jìn)行劃分，分別得到各個(gè)時(shí)序圖，對(duì)每個(gè)時(shí)刻的時(shí)序圖采用HMM_DC算法，得到結(jié)果如圖10～12所示.其中，圖10～12分別為HMM_DC算法模型在Facebook數(shù)據(jù)集中的NMI值和模塊度Q值以及運(yùn)行時(shí)間的曲線圖.圖10可以看出，本文算法在NMI值上要明顯優(yōu)于其他算法，平均提高了20%.從圖11可以看出，模塊度Q值均大于0.5，且相比于MIEN和CDBIA等其他算法提高了0.03.從圖10和圖11可以看出，由于HMM_DC算法得到的社團(tuán)結(jié)構(gòu)是全局最優(yōu)的，因此其NMI值和Q值都較優(yōu).由圖12可知，在效率上，HMM_DC算法與QCA算法相似，略優(yōu)于QCA算法，與MIEN和CDBIA算法相比要明顯效率高.因此，HMM_DC算法在整體性能上要優(yōu)于其他算法.

Fig. 11 Q values of Facebook data set圖11 Facebook數(shù)據(jù)集的Q值

Fig. 12 Runtime of Facebook data set圖12 Facebook數(shù)據(jù)集的運(yùn)行時(shí)間

通過(guò)對(duì)以上3個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)仿真可以看出，HMM_DC算法在準(zhǔn)確性和效率上相比于其他動(dòng)態(tài)社團(tuán)發(fā)現(xiàn)方法，具有較好的性能.

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

本文提出了一種基于隱Markov模型動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法.HMM_DC通過(guò)隱Markov模型對(duì)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)進(jìn)行模型建立，將動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)建模為HMM中的狀態(tài)鏈，而將動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)成員的節(jié)點(diǎn)度建模為HMM中的觀察鏈，將求解動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)問(wèn)題轉(zhuǎn)化為求解隱Markov模型中的最優(yōu)狀態(tài)序列問(wèn)題，最后通過(guò)Viterbi算法可以得到全局最優(yōu)的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu).通過(guò)對(duì)真實(shí)網(wǎng)絡(luò)仿真證明了HMM_DC算法適用于較大規(guī)模且相對(duì)稠密的網(wǎng)絡(luò)，不僅能夠發(fā)現(xiàn)具有實(shí)時(shí)性、準(zhǔn)確性的動(dòng)態(tài)社團(tuán)結(jié)構(gòu)，而且具有較低的時(shí)間復(fù)雜度.

然而，正如仿真結(jié)果中所示，HMM_DC算法在網(wǎng)絡(luò)中稀疏圖的性能上較差，由于稀疏圖中的節(jié)點(diǎn)信息較少，HMM_DC算法不能得到足夠的有效信息而無(wú)法得到全局最優(yōu)的社團(tuán)結(jié)構(gòu).而部分社交網(wǎng)絡(luò)的動(dòng)態(tài)特性使其在某個(gè)時(shí)刻具有稀疏性，因此，如何改善該算法在稀疏圖上的表現(xiàn)是未來(lái)將要研究的一個(gè)問(wèn)題.

[1]Gregory S. Ordered community structure in networks[J]. Physica A: Statistical Mechanics and Its Applications, 2012, 391(8): 2752-2763

[2]Jin Songchang, Li Aiping, Yang Shuqiang, et al. A MapReduce and information compression based social community structure mining method[C]Proc of the 16th IEEE Int Conf on Computational Science and Engineering (CSE). Piscataway, NJ: IEEE, 2013: 971-980

[3]Lou Hao, Li Shenghong, Zhao Yuxin. Detecting community structure using label propagation with weighted coherent neighborhood propinquity[J]. Physica A: Statistical Mechanics and Its Applications, 2013, 392(14): 3095-3105

[4]Walker D M, Tordesillas A. Examining overlapping community structures within grain property networks[C]Proc of 2014 IEEE Int Symp on Circuits and Systems (ISCAS). Piscataway, NJ: IEEE, 2014: 1275-1278

[5]Wu Zhihao, Lin Youfang, Wan Huaiyu, et al. Efficient overlapping community detection in huge real-world networks[J]. Physica A: Statistical Mechanics and Its Applications, 2012, 391(7): 2475-2490

[6]Lin Chuncheng, Liu Wanyu, Deng Derjiunn. A genetic algorithm approach for detecting hierarchical and overlapping community structure in dynamic social networks[C]Proc of Wireless Communications and Networking Conf (WCNC). Piscataway, NJ: IEEE, 2013: 4469-4474

[7]Berger-Wolf T Y, Saia J. A framework for analysis of dynamic social networks[C]Proc of the 12th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2006: 523-528

[8]Tantipathananandh C, Berger-Wolf T Y, Kempe D. A framework for community identification in dynamic social networks[C]Proc of the 13th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2007: 717-726

[9]Sun Jimeng, Faloutsos C, Papadimitriou S, et al. GraphScope: Parameter-free mining of large time-evolving graphs[C]Proc of the 13th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2007: 687-696

[10]Liu Yao, Liu Qiao, Qin Zhiguang. Community detecting and feature analysis in real directed weighted social networks[J]. Journal of Networks, 2013, 8(6): 1432-1439

[11]Nguyen N P, Dinh T N, Xuan Y, et al. Adaptive algorithms for detecting community structure in dynamic social networks[C]Proc of 2011 INFOCOM. Piscataway, NJ: IEEE, 2011: 2282-2290

[12]Rossetti G, Guidotti R, Pennacchioli D, et al. Interaction prediction in dynamic networks exploiting community discovery[C]Proc of the 2015 IEEEACM Int Conf on Advances in Social Networks Analysis and Mining. New York: ACM, 2015: 553-558

[13]Zhou Xu, Liu Yanheng, Li Bin, et al. Multiobjective biogeography based optimization algorithm with decomposition for community detection in dynamic networks[J]. Physica A: Statistical Mechanics and Its Applications, 2015, 436: 430-442

[14]Xin Yu, Xie Zhiqiang, Yang Jing. The adaptive dynamic community detection algorithm based on the non-homogeneous random walking[J]. Physica A: Statistical Mechanics and Its Applications, 2016, 450: 241-252

[15]Liu Ying, Moser J, Aviyente S. Network community structure detection for directional neural networks inferred from multichannel multi-subject EEG data[J]. IEEE Trans on Biomedical Engineering, 2014, 61(7): 1919-1930

[16]Chen Mingming, Nguyen T, Szymanski B K. On measuring the quality of a network community structure[C]Proc of 2013 Int Conf on Social Computing (SocialCom). Piscataway, NJ: IEEE, 2013: 122-127

[17]Cheng Feng, Wang Zuxi. Network community structure in hyperbolic space[J].Engineering Journal of Wuhan University: Engineering Science, 2013, 46(5): 630-634 (in Chinese) (程峰, 王祖喜. 雙曲空間中的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)[J]. 武漢大學(xué)學(xué)報(bào): 工學(xué)版, 2013, 46(5): 630-634)

[18]Shang Jiaxing, Liu Lianchen, Li Xin, et al. Targeted revision: A learning-based approach for incremental community detection in dynamic networks[J]. Physica A: Statistical Mechanics and Its Applications, 2016, 443: 70-85

[19]Wei Wei，Qi Yong. Information potential fields navigation in wireless ad-hoc sensor networks[J]. Sensors, 2011, 11(5): 4794-4807[20]Song Houbing, Brandt-Pearce M. Model-centric nonlinear equalizer for coherent long-haul fiber-optic communication systems[C]Proc of 2013 IEEE Global Communications Conf. Piscataway, NJ: IEEE, 2013: 2394-2399

[21]Lin Chuncheng, Liu Wanyu, Deng Derjiunn. A genetic algorithm approach for detecting hierarchical and overlapping community structure in dynamic social networks[C]Proc of Wireless Communications and Networking Conf (WCNC). Piscataway, NJ: IEEE, 2013: 4469-4474

[22]Li Jingyong, Lan Huang, Bai Tian, et al. CDBIA: A dynamic community detection method based on incremental analysis[C]Proc of IEEE 2012 Int Conf on Systems and Informatics (ICSAI). Piscataway, NJ: IEEE, 2012: 2224-2228

[23]Dinh T N, Xuan Ying, Thai M T. Towards social-aware routing in dynamic communication networks[C]Proc of the 28th IEEE Int Conf on Performance Computing and Communications (IPCCC). Piscataway, NJ: IEEE, 2009: 161-168

[24]Viswanath B, Mislove A, Cha M, et al. On the evolution of user interaction in Facebook[C]Proc of the 2nd ACM Workshop on Online Social Networks. New York: ACM, 2009: 37-42

[25]Cui Jinzhong, Zhou Yuanbin, Chen Leiting. Implementation and optimization of embedded speech recognition system based on DHMM[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(6): 930-934 (in Chinese)(崔金鐘, 周遠(yuǎn)彬, 陳雷霆. 基于DHMM的嵌入式語(yǔ)音識(shí)別系統(tǒng)的實(shí)現(xiàn)與優(yōu)化[J]. 電子科技大學(xué)學(xué)報(bào), 2013, 42(6): 930-934)

[26]Li Xiaojia, Zhang Peng, Di Zengru, et al. Community structure in complex networks[J].Complex Systems and Complexity Science, 2008, 5(3): 19-42 (in Chinese)(李曉佳, 張鵬, 狄增如, 等. 復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2008, 5(3): 19-42)

YiPeng, born in 1977. PhD, professor. His main research interests include complex network.

ZhouQiao, born in 1993. Master. His main research interests include computer network, complex network.

MenHaosong, born in 1978. Master. His main research interests include complex network.

DynamicSocialNetworkCommunityDetectionAlgorithmBasedonHiddenMarkovModel

Yi Peng1, Zhou Qiao1, and Men Haosong2

1(National Digital Switching System Engineering amp; Technology Research amp; Development Center, Zhengzhou 450001)2(Department of Information, Ministry of Science amp; Technology of the People’s Republic of China, Beijing 100000)

With the continuous development of the Internet, most social networks have gradually demonstrated dynamic characteristics, and dynamic analysis of social network community has a very important significance on the understanding of the structure and function of social networks in real life. The HMM_DC algorithm (hidden Markov model based on dynamic community detection) is proposed according to the HMM (hidden Markov model) to detect the community in dynamic social network. Firstly, the algorithm transforms the community detection problem to get the optimal status chain in hidden Markov model considering the history information and characteristics in dynamic social networks. And the algorithm uses the observed chain and status chain to represent the community structure and node information, and can identify the community structure without extra information. Finally, this algorithm and three other algorithms are used to make comparable simulation experiments with VAST data set, ENRON data set and Facebook social network data set. Experimental results show that HMM_DC algorithm performs effectively and accurately in identifying the community structure in the dynamic social network and the value ofQandNMIcan be raised greatly compared with other three algorithms.

dynamic social network; hidden Markov model (HMM); optimal status chain; community structure; community detection

2016-10-11；

2017-02-06

國(guó)家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目(2015AA016102)

This work was supported by the National High Technology Research and Development Program of China (863 Program) (2015AA016102).

周橋(zhouqiao_ndsc@163.com)

TP393