一種基于高斯混合模型、結(jié)合拓?fù)渑c內(nèi)容的大規(guī)模社團(tuán)發(fā)現(xiàn)方法

羅國華,龔欣哲,王英奎,何東曉,金 弟

(天津大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,天津 300350)

1 引 言

社團(tuán)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)中最重要的拓?fù)鋵傩灾?具有“同一社團(tuán)內(nèi)之結(jié)點(diǎn)相互連接緊密、不同社團(tuán)間之結(jié)點(diǎn)相互連接稀疏”之特點(diǎn)[1].社團(tuán)發(fā)現(xiàn)的目的就是要探測出復(fù)雜網(wǎng)絡(luò)中具有的社團(tuán)結(jié)構(gòu),可幫助人們理解復(fù)雜網(wǎng)絡(luò)的功能、發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中隱藏的規(guī)律、預(yù)測復(fù)雜網(wǎng)絡(luò)的行為等.它不僅吸引了大量不同學(xué)科的研究工作者,而且已被應(yīng)用于如:恐怖組織識別、組織結(jié)構(gòu)管理、蛋白質(zhì)功能預(yù)測、搜索引擎等諸多領(lǐng)域[2,3].

對復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)挖掘是一個十分經(jīng)典的研究課題,已經(jīng)有很多先前的相關(guān)研究,早期的研究方法主要有圖分割法,聚類方法和譜分析法幾種,而這些研究方法基本上都與圖論有關(guān),圖論是一種簡單明了又具有很大研究空間的數(shù)學(xué)學(xué)科分支,是由數(shù)學(xué)家歐拉開創(chuàng)的一項重要的工作.現(xiàn)在已經(jīng)在計算機(jī)科學(xué)界擁有巨大的研究價值.人們對網(wǎng)絡(luò)的研究經(jīng)歷了幾個階段,從開始的規(guī)則網(wǎng)絡(luò)中節(jié)點(diǎn)之間關(guān)系的研究,到后來的隨機(jī)網(wǎng)絡(luò)中節(jié)點(diǎn)間關(guān)系的研究,直到現(xiàn)在的復(fù)雜網(wǎng)絡(luò)中關(guān)系的研究,都離不開圖論.

關(guān)于復(fù)雜網(wǎng)絡(luò)中進(jìn)行社團(tuán)發(fā)現(xiàn)的問題,目前已經(jīng)有了許多種解法,大致上分為兩類:

1)忽略內(nèi)容信息而更加關(guān)注處理網(wǎng)絡(luò)中的拓?fù)湫砸约巴卣剐詥栴}.

2)同時關(guān)注內(nèi)容信息以及拓?fù)湫畔?從本質(zhì)上來看,第二種方式是在第一種方法的基礎(chǔ)上的提高,因為內(nèi)容信息可以為提升推斷社團(tuán)的質(zhì)量提供幫助.但是這種方法在網(wǎng)絡(luò)的擴(kuò)展時,會面臨更多的成本問題[4].

為了能夠在網(wǎng)絡(luò)中發(fā)現(xiàn)社團(tuán)結(jié)構(gòu),研究者們做出了許多努力.在接下來的研究中,一些研究者們專注于研究在連接關(guān)系上的社團(tuán)劃分,這是由社團(tuán)結(jié)構(gòu)的直觀定義:社團(tuán)結(jié)構(gòu)是一種內(nèi)部連接緊密而與外部連接稀疏的結(jié)構(gòu)來得出的方法.這方面的算法根據(jù)采用的技術(shù)或理論的不同,它們主要可以分為:凝聚或分裂算法[5]、基于模塊度優(yōu)化的方法[6]、譜方法[7]、動力學(xué)方法[8]等.

上述方法只是利用的鏈接關(guān)系而忽略網(wǎng)絡(luò)中每個節(jié)點(diǎn)所含有的內(nèi)容信息,導(dǎo)致在一些問題中,劃分結(jié)果不能反映每個聚類中的主題關(guān)系.在一些社團(tuán)發(fā)現(xiàn)問題,如推薦好友時,內(nèi)容信息是十分重要的,如果只考慮連接關(guān)系的話,就只能夠找到與用戶關(guān)系最為密切的好友,但無法找到和用戶所關(guān)注的興趣愛好最為相近的好友.所以同時利用網(wǎng)絡(luò)中節(jié)點(diǎn)的拓?fù)溥B接關(guān)系與內(nèi)容信息來發(fā)現(xiàn)社團(tuán)的方法也在不斷地被更多人所重視.

同樣的,也有許多利用內(nèi)容信息幫助發(fā)現(xiàn)社團(tuán)的研究,其中之一的方法就是概率生成模型,這是一種基于一個或多個潛變量,結(jié)合內(nèi)容和拓?fù)溥B接,估計條件分布來尋找社區(qū)分配的方法.例如:Leskovec 等[9]同時利用網(wǎng)絡(luò)拓?fù)渑c結(jié)點(diǎn)屬性,提出了一個可擴(kuò)展性的重疊社團(tuán)檢測算法.基于結(jié)點(diǎn)隸屬每個社團(tuán)的概率,首先面向網(wǎng)絡(luò)拓?fù)錁?gòu)建概率生成模型;然后針對結(jié)點(diǎn)的屬性構(gòu)建Logistic模型;最后合并兩個模型,并采用極大似然估計求解.Yu 等[10]通過把原始網(wǎng)絡(luò)轉(zhuǎn)化為“結(jié)點(diǎn)-鏈接”交互(NEI)圖,將網(wǎng)絡(luò)拓?fù)?、結(jié)點(diǎn)上的內(nèi)容和鏈接上的內(nèi)容有效融合;通過在每一步更新的NEI 圖上采用異步隨機(jī)游走方法,動態(tài)檢測網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu).

面對如今規(guī)模越來越大的網(wǎng)絡(luò)數(shù)據(jù),對圖像進(jìn)行采樣再進(jìn)行聚類的方法越來越吸引人們的注意力,如果一個圖結(jié)構(gòu)中的邊界經(jīng)過采樣變得盡可能的少,那么社團(tuán)發(fā)現(xiàn)算法就能夠用更少的空間、占據(jù)更小的存儲空間來得出與原圖經(jīng)過社團(tuán)發(fā)現(xiàn)算法操作后相近的結(jié)果.2013年,Ruan 等人提出了基于TF-IDF方法的,對于網(wǎng)絡(luò)中節(jié)點(diǎn)的內(nèi)容信息進(jìn)行處理,以達(dá)到結(jié)合拓?fù)渑c內(nèi)容進(jìn)行社團(tuán)發(fā)現(xiàn)的目的的CODICIL算法[4].該算法中的TF-IDF方法維度過高,不能夠準(zhǔn)確的描述每個節(jié)點(diǎn)內(nèi)容信息的特征情況,并且計算量十分龐大.對此,本文基于此算法,使用高斯混合模型(GMM)擬合結(jié)合網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)以及節(jié)點(diǎn)內(nèi)容信息的社團(tuán)發(fā)現(xiàn)算法,通過在真實(shí)世界網(wǎng)絡(luò)數(shù)據(jù)集中的比較,表明這一算法相對于只考慮網(wǎng)絡(luò)中的拓?fù)湫畔⒌纳鐖F(tuán)發(fā)現(xiàn)算法,可以比較好的在網(wǎng)絡(luò)中進(jìn)行社團(tuán)發(fā)現(xiàn),且在精度和速度上比原算法優(yōu)越.

2 方 法

一個圖結(jié)構(gòu)可以被分為三個部分:圖中的節(jié)點(diǎn),圖中的邊和圖中每個節(jié)點(diǎn)所代表的內(nèi)容信息.我們定義符號ζt=(V,εt,T)來表示圖,其中,ζt表示有n個節(jié)點(diǎn)V=v1,v2,…,vn的集合,而在圖中會存在t條連接節(jié)點(diǎn)與節(jié)點(diǎn)間邊εt.同時,由于每個節(jié)點(diǎn)有其節(jié)點(diǎn)本身所含有的內(nèi)容信息,而這些內(nèi)容信息可以被看作一個向量,我們稱其為詞向量(term vectors)或者內(nèi)容向量(content vectors),每個節(jié)點(diǎn)的會含有n個內(nèi)容向量T=t1,t2,…,tn.他們一起構(gòu)成了我們整個算法所需要的網(wǎng)絡(luò).我們需要在這個網(wǎng)絡(luò)中對內(nèi)容向量進(jìn)行處理,生成每個節(jié)點(diǎn)內(nèi)容最相近的鄰居節(jié)點(diǎn),將他們之間生成一條內(nèi)容邊后,與網(wǎng)絡(luò)中原有拓?fù)溥呥M(jìn)行結(jié)合,經(jīng)過采樣之后,進(jìn)行社團(tuán)發(fā)現(xiàn).

2.1 創(chuàng)建內(nèi)容邊

在本文中,我們將使用高斯混合模型(Gaussian mixture model),來擬合圖ζt=(V,εt,T)中每個點(diǎn)相對于每個聚類的關(guān)系.使用由數(shù)個不同的高斯模型混合組成的高斯混合模型來擬合的原因是通過高斯分布的線性組合,可以擬合相當(dāng)復(fù)雜的概率密度形式.如果使用的高斯分布足夠多,幾乎可以擬合所有的連續(xù)概率密度.

我們使用了R語言中的Flexmix軟件包來實(shí)現(xiàn)高斯混合模型算法(GMM).Flexmix包是R的擴(kuò)展包之一,它提供方法來使用EM算法和模型選擇來擬合有限混合模型[14].也就是說,不僅是我們目前使用的高斯模型之間可以進(jìn)行擬合,如伯努利模型,二次模型等模型之間都可以進(jìn)行互相擬合.有限混合模型是由K個不同的成分的凸組合(wiki)得出的.即權(quán)重非負(fù)且和為1.Flexmix包使用規(guī)則如下:

flexmix(formula,data=list(),k= NULL,cluster = NULL,

model = NULL,concomitant = NULL,

control = NULL,weights = NULL)

使用此軟件包得出的結(jié)果是經(jīng)GMM方法擬合出圖ζt=(V,εt,T)中每個點(diǎn)相對于每個聚類關(guān)系的N×K(N節(jié)點(diǎn),K類)概率矩陣A,我們通過向量之間的相似性計算方法,計算出每兩個節(jié)點(diǎn)之間的內(nèi)容相似度.一般來說,我們經(jīng)常使用的是余弦相似度(cosine similarity)方法,即:

(1)

通過余弦相似度方法所得出的每個節(jié)點(diǎn)vi相似度最大的k(k=50)個鄰居vj,我們將他們所構(gòu)成的一條邊(vi,vj),添加到內(nèi)容邊集合εc中.

此方法相對于TF-IDF方法能體現(xiàn)出兩個優(yōu)越性:

1)能使最后的聚類結(jié)果精度提高;因為GMM方法本身就是比較成熟且精度高的聚類算法,而TF-IDF不能夠準(zhǔn)確的描述每個節(jié)點(diǎn)內(nèi)容信息的特征情況;所以最后的結(jié)果的精度相應(yīng)的提高.

2)計算速度的提高;TF-IDF方法維度過高(N×N),計算量十分龐大,而GMM方法使得為N×K的矩陣A,K類的數(shù)量是遠(yuǎn)小于N節(jié)點(diǎn)的數(shù)量的,所以維度的大幅度降低,使得計算速度的提高.

2.2 對邊集合進(jìn)行采樣

我們在上一步創(chuàng)建內(nèi)容邊中,得到了每個節(jié)點(diǎn)與其內(nèi)容上最相似的k個節(jié)點(diǎn),并將他們之間創(chuàng)建一條內(nèi)容邊存在了邊集合εc中,而我們原有的數(shù)據(jù)中,存在有在連接關(guān)系上的拓?fù)渚W(wǎng)絡(luò)邊集合εt,所以我們的第一步是將這兩個集合合并為一個集合,目的是將一些內(nèi)容上十分相似,但是在拓?fù)浣Y(jié)構(gòu)上沒有聯(lián)系的節(jié)點(diǎn)互相聯(lián)系起來.最終得到一個總的邊集合εu=εc+εt.再將εc,εt分別與εu進(jìn)行相似度計算,一般我們會使用Jaccard算法:

1http://linqs.cs.umd.edu/projects/projects/lbc/

(2)

(3)

(4)

這樣,我們通過對集合εu中邊的采樣,得到了采樣后的邊集合εsample,我們可以將這些邊和沒有變動的節(jié)點(diǎn)結(jié)合一起,組成最后我們的采樣結(jié)果:一個圖結(jié)構(gòu)的網(wǎng)絡(luò)數(shù)據(jù)ζsample=(v,εsample).

2.3 聚類劃分采樣圖

得出一個簡化的圖ζsample后,這樣我們就完成了CODICIL算法的核心部分,我們接下來只需要使用EIG以及CNM聚類算法,對我們之前得到的采樣結(jié)果圖ζsample進(jìn)行聚類,就可以得到一個即考慮了節(jié)點(diǎn)之間的拓?fù)溥B接信息,也考慮了節(jié)點(diǎn)內(nèi)含有的內(nèi)容信息的聚類結(jié)果.

3 實(shí) 驗

本實(shí)驗是基于CODICIL算法在一個網(wǎng)絡(luò)數(shù)據(jù)中結(jié)合邊鏈接和內(nèi)容信息進(jìn)行社團(tuán)發(fā)現(xiàn)的;使用我們提出改進(jìn)后的高斯混合模型的CODICIL算法得出聚類結(jié)果數(shù)據(jù),再使用評價函數(shù)將這個結(jié)果與原TF-IDF的CODICIL算法和只使用拓?fù)滏溄訑?shù)據(jù)的聚類效果進(jìn)行評價.

實(shí)驗數(shù)據(jù)1采用的是Cornell,Texas,Washington,CiteSeer和Pubmed Diabetes 五個數(shù)據(jù)集,例如:CiteSeer數(shù)據(jù)集是關(guān)于學(xué)術(shù)論文數(shù)字圖書館的引文索引數(shù)據(jù),數(shù)據(jù)中的文章被歸納成六類領(lǐng)域,在我們的實(shí)驗結(jié)構(gòu)圖中,每個節(jié)點(diǎn)代表每篇文章,無向邊代表文章之間的引用關(guān)系,每個節(jié)點(diǎn)的內(nèi)容信息則用源于研究文章詞匯的二進(jìn)制向量表示.所有實(shí)驗均運(yùn)行于配置為3.70GHz CPU、8核處理器且內(nèi)存為32GB的windows7機(jī)器上,且所有算法均基于R語言和MATLAB實(shí)現(xiàn).

我們實(shí)驗使用的數(shù)據(jù)集分為兩部分(以CiteSeer為例),一部分為文章(節(jié)點(diǎn))之間的引用關(guān)系(鏈接邊)的數(shù)據(jù),另一部分為每篇文章對應(yīng)詞匯的二進(jìn)制特征向量表示的內(nèi)容特征信息及每篇文章的真實(shí)歸屬6個類領(lǐng)域的聚類.接下來,我們提交給算法處理的數(shù)據(jù)集,必須被歸納為兩個矩陣:一個是數(shù)據(jù)點(diǎn)之間的拓?fù)溥B接矩陣,代表著網(wǎng)絡(luò)中的拓?fù)湫畔?即為CiteSeer數(shù)據(jù)集的第一部分).另一個是每個數(shù)據(jù)點(diǎn)的內(nèi)容向量的集合所組成的矩陣,代表著網(wǎng)絡(luò)中每個節(jié)點(diǎn)的內(nèi)容信息(即為CiteSeer數(shù)據(jù)集的第二部分).如果我們的網(wǎng)絡(luò)中有n個節(jié)點(diǎn),每個節(jié)點(diǎn)的內(nèi)容向量有m項內(nèi)容特征,那么我們的拓?fù)溥B接矩陣就是一個n×n的矩陣,而內(nèi)容向量矩陣應(yīng)該是一個n×m的矩陣.所以我們需要將數(shù)據(jù)集中的每篇文章,即網(wǎng)絡(luò)中的節(jié)點(diǎn),以序號的方式命名后,用數(shù)字的形式替代拓?fù)湮募械囊藐P(guān)系文章名,而內(nèi)容向量部分?jǐn)?shù)據(jù)集本身不需要我們調(diào)整,每篇文章所屬的真實(shí)數(shù)據(jù)聚類歸屬和文章名一樣,替換成序號數(shù)字的形式.將CiteSeer數(shù)據(jù)集載入到flexmix軟件包的高斯混合模型算法中實(shí)現(xiàn)創(chuàng)建內(nèi)容邊:

表1 實(shí)驗數(shù)據(jù)集ζt=(v,εt,T)Table 1 Experimental data set ζt=(v,εt,T)

R> CiteSeer _mix<-flexmix(matrix～1,

+ data= CiteSeer _content,model=FLXMCmvcombi(),

+ control=list(minprior=0.005),k=6)

R>posterior(CiteSeer _mix)

得出每個節(jié)點(diǎn)對應(yīng)6個類的概率矩陣,對此矩陣進(jìn)行通過向量之間的相似性計算方法,計算出每兩個節(jié)點(diǎn)之間的內(nèi)容相似度.再按照本文第2節(jié)所述的方法進(jìn)行后續(xù)的對邊集合進(jìn)行采樣和聚類劃分采樣圖步驟得到聚類結(jié)果.

在此我們還采用了兩種不同的評價函數(shù)對拓?fù)湫畔⒑蛢?nèi)容結(jié)合最終得到的鄰接矩陣的聚類結(jié)果與我們事先得到的已知聚類歸屬數(shù)據(jù)進(jìn)行精確性比對.評價函數(shù)分別是NMI和F-score評價指標(biāo).

表2 EIG 函數(shù)聚類結(jié)果比較Table 2 EIG function clustering results compare

根據(jù)實(shí)驗數(shù)據(jù)對比,我們可以看出,在絕大多數(shù)情況下,無論是在使用EIG聚類函數(shù)(表2),或者是使用CNM聚類函數(shù)(表3)的情況下,我們改進(jìn)后的使用高斯混合模型的GMM_CODICIL都比使用TF-IDF的CODICIL算法的聚類效果會更好一些.

表3 CNM 函數(shù)聚類結(jié)果比較Table 3 EIG function clustering results compare

同時因為GMM在維度上相對于TF-IDF降低了,所以在計算速度上也明顯加快.

4 結(jié) 論

本文提出了使用高斯混合模型(GMM),來對原CODICIL算法中,對內(nèi)容向量中的內(nèi)容特征進(jìn)行權(quán)重調(diào)整的方法進(jìn)行改進(jìn).本文通過分析GMM方法與每個節(jié)點(diǎn)的內(nèi)容向量相對于數(shù)個內(nèi)容聚集中心的內(nèi)容相似性之間的相似性,得出可以使用EM算法來迭代產(chǎn)生GMM的隱變量期望,從而求得網(wǎng)絡(luò)中每個節(jié)點(diǎn)所帶有的內(nèi)容信息與設(shè)定的數(shù)個聚集之間的相似度,從而分析出節(jié)點(diǎn)的內(nèi)容信息的傾向.同時基于CODICIL算法,計算出與之前僅包含拓?fù)湫畔⒌木W(wǎng)絡(luò)不同的,兼顧拓?fù)湫畔⑴c內(nèi)容信息的網(wǎng)絡(luò)數(shù)據(jù)來進(jìn)行社團(tuán)發(fā)現(xiàn),有利于提高社團(tuán)發(fā)現(xiàn)的精確度.最后通過評估實(shí)驗,驗證了算法的準(zhǔn)確性和實(shí)用性.

我們以后的工作主要有兩方面:一方面,將加入語義信息,給打上語義標(biāo)簽,使得在聚類圖標(biāo)中能體現(xiàn)出社團(tuán)的語義比例信息,從而更直觀的表示出聚類社團(tuán)的信息.另一方面,由于本文方法的運(yùn)行計算速度快,將本文方法向動態(tài)性擴(kuò)展,應(yīng)用于動態(tài)網(wǎng)絡(luò)社團(tuán)挖掘研究領(lǐng)域,并試圖從中探測和揭示出具有重要意義的真實(shí)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu).

：

[1] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proc.Natl.Acad.Sci.USA,2002,99(12):7821-7826.

[2] Wang Li,Cheng Xue-qi.Dynamic community in online social networks[J].Chinese Journal of Computers,2015,38(2):219-237.

[3] Johnson N F,Zheng M,Vorobyeva Y,et al.New online ecology of adversarial aggregates:ISIS and beyond[J].Science,2016,352(6292):1459-1463.

[4] Ruan Y Y,Fuhry D,Parthasarathy S.Efficient community detection in large networks using content and links[C].Proceedings of the 22nd International World Wide Web Conference (WWW-13),Rio de Janeiro,Brazil:WWW,2013:1089-1098.

[5] Jia S W,Gao L,Gao Y,et al.Defining and identifying cograph communities in complex networks[J].New Journal of Physics,2015,17(1):013044.

[6] Zhang P,Moore C.Scalable detection of statistically significant communities and hierarchies,using message passing for modularity[J].Proc.Natl.Acad.Sci.USA,2014,111(51):18144-18149.

[7] Li Y X,He K,Bindel D,et al.Uncovering the small community structure in large networks:a local spectral approach[C].Proceedings of the 24th International World Wide Web Conference (WWW-15),Florence,Italy:WWW,2015:658-668.

[8] Rosvall M,Esquivel A V,Lancichinetti A,et al.Memory in network flows and its effects on spreading dynamics and community detection[J].Nature Communications,2014,5(1):4630-4637.

[9] Yang J,McAuley J,Leskovec J.Community detection in networks with node Attributes[C].Proceedings of the IEEE 13th International Conference on Data Mining (ICDM-13),Dallas,Texas:IEEE,2013:1151-1156.

[10] Wang C D,Lai J H,Yu P S.NEIWalk:community discovery in dynamic content-based networks[J].IEEE Trans.Knowl.Data Eng.,2014,26(7):1734-1748.

[11] Liu Da-you,Jin Di,He Dong-xiao,et al.Community mining in complex networks[J].Journal of Computer Research and Development,2013,50(10):2140-2154.

[12] Newman M E J,Clauset A.Structure and inference in annotated networks[J].Nature Communications,2016,7(1):11863-11873.

[13] Wang X,Jin D,Cao X C,et al.Semantic community identification in large attribute networks[C].Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI-16),Phoenix,Arizona:AAAI,2016:265-271.

[14] Gruen B,Leisch F,Sarkar D,et al.Flexmix:flexible mixture modeling[EB/OL].https://CRAN.R-project.org/package=flexmix,2015.

附中文參考文獻(xiàn)：

[2] 王 莉,程學(xué)旗.在線社會網(wǎng)絡(luò)的動態(tài)社區(qū)發(fā)現(xiàn)及演化[J].計算機(jī)學(xué)報,2015,38(2):219-237.

[11] 劉大有,金 弟,何東曉,等.復(fù)雜網(wǎng)絡(luò)社團(tuán)挖掘綜述[J].計算機(jī)研究與發(fā)展,2013,50(10):2140-2154.