王學(xué)軍，李有紅，李熾平

(廣東工業(yè)大學(xué)華立學(xué)院，廣東 廣州 511325)

0 引 言

社區(qū)結(jié)構(gòu)是現(xiàn)實(shí)復(fù)雜網(wǎng)絡(luò)中最普遍和最重要的中觀結(jié)構(gòu)。研究發(fā)現(xiàn)[1-2]，在社區(qū)結(jié)構(gòu)中,屬于同一社區(qū)內(nèi)的節(jié)點(diǎn)往往處于同一簇內(nèi),并且簇內(nèi)節(jié)點(diǎn)連接緊密，簇間節(jié)點(diǎn)連接稀疏，簇間的邊介數(shù)遠(yuǎn)遠(yuǎn)大于簇內(nèi)部的邊介數(shù)。自2002年Girvan M和Newman M E J[1]提出社區(qū)結(jié)構(gòu)概念以來(lái)，社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法就被廣泛應(yīng)用在蛋白網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、協(xié)作網(wǎng)絡(luò)、疾病傳播網(wǎng)絡(luò)、語(yǔ)義網(wǎng)絡(luò)、電網(wǎng)網(wǎng)絡(luò)、萬(wàn)維網(wǎng)絡(luò)等領(lǐng)域的結(jié)構(gòu)和動(dòng)力學(xué)分析中。經(jīng)過(guò)社區(qū)挖掘分析，可以揭示潛在的隱形規(guī)律，預(yù)測(cè)事物演化，控制意外發(fā)生等[1-3]。近年來(lái)，也涌現(xiàn)出了許多關(guān)于社區(qū)發(fā)現(xiàn)的方法，按數(shù)理方法分類主要有[2]：基于分裂的方法、基于合并的方法、基于模塊度的方法、基于譜二分的方法、基于網(wǎng)絡(luò)動(dòng)力學(xué)的方法、基于統(tǒng)計(jì)推理的方法。

尋找復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的最優(yōu)劃分是一個(gè)NP問(wèn)題[4-5]。提升劃分精度和計(jì)算復(fù)雜度仍然是各項(xiàng)研究的重點(diǎn)。譜聚類劃分方法最早應(yīng)用在模式識(shí)別中，主要用來(lái)實(shí)現(xiàn)圖像數(shù)字媒體的聚類，其在有限時(shí)空范圍內(nèi)的計(jì)算精度有目共睹。近年來(lái)，在復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)領(lǐng)域已有多項(xiàng)關(guān)于譜聚類方法的研究，基于譜聚類的社區(qū)發(fā)現(xiàn)算法在小規(guī)模情況下是一種有效的方法[2]。相比傳統(tǒng)單一的聚類算法，如k-均值聚類、減法聚類、峰值聚類等[5-7]，譜聚類方法[7]在遇到非凸邊樣本數(shù)據(jù)時(shí)不會(huì)陷入局部最優(yōu)和魯棒性相對(duì)較差的困局，在聚類精度、整體性上都有上佳表現(xiàn)。目前比較經(jīng)典的譜聚類社區(qū)發(fā)現(xiàn)方法，如NG算法[1]、NJW算法[8]、Nystr?m算法[9]等，都是通過(guò)樣本數(shù)據(jù)構(gòu)建相似矩陣后，對(duì)其進(jìn)行拉普拉斯矩陣分解，再對(duì)分解后得到的特征向量進(jìn)行經(jīng)典k值聚類，最終實(shí)現(xiàn)社區(qū)結(jié)劃分。但上述方法都依賴于預(yù)先設(shè)定的k值，而現(xiàn)實(shí)計(jì)算中，k值往往是未知的。

針對(duì)上述問(wèn)題，提出一種基于密度自適應(yīng)聚類數(shù)的社區(qū)發(fā)現(xiàn)譜方法。基于局部節(jié)點(diǎn)密度構(gòu)圖，結(jié)合網(wǎng)絡(luò)圖的邊介數(shù)值構(gòu)造相似矩陣，規(guī)范化后進(jìn)行譜聚類,求得最大特征維度k,k值即為社區(qū)個(gè)數(shù)，最后采用k-means算法對(duì)特征向量空間進(jìn)行聚類，使得復(fù)雜網(wǎng)絡(luò)社區(qū)得以呈現(xiàn)。利用Newman提出的社區(qū)模塊度評(píng)價(jià)函數(shù)[10]和文獻(xiàn)[11]提出的重疊社區(qū)評(píng)價(jià)函數(shù),與經(jīng)典的社區(qū)發(fā)現(xiàn)算法(NG算法[1]、FN算法[11]、COPRA算法[12]、NJW算法[13])進(jìn)行實(shí)驗(yàn)對(duì)比發(fā)現(xiàn)，該算法能更精確地構(gòu)造相似矩陣,得到的仿真社區(qū)結(jié)構(gòu)更接近真實(shí)。對(duì)多類別屬性、多關(guān)系的數(shù)據(jù)集實(shí)驗(yàn)發(fā)現(xiàn)，該算法更適合多領(lǐng)域的聚類社區(qū)檢測(cè)。

1 相關(guān)背景

復(fù)雜網(wǎng)絡(luò)樣本數(shù)據(jù)可以用圖表示為G=(V,E),其中節(jié)點(diǎn)集V=v1,v2,…,vn，網(wǎng)絡(luò)所有節(jié)點(diǎn)的邊集E={eij|0

L=D-A

(1)

規(guī)范化拉普拉斯矩陣定義為:

(2)

νi∈NK

(3)

其中

(4)

2 基于領(lǐng)域的自適應(yīng)譜聚類社區(qū)發(fā)現(xiàn)

2.1 算法思想

傳統(tǒng)譜聚類算法[5-7,9]都是根據(jù)預(yù)先輸入聚類參數(shù)k，進(jìn)行譜分解后，再運(yùn)用k-means或FCM等經(jīng)典算法進(jìn)行聚類。而在實(shí)際應(yīng)用中聚類參數(shù)k是很難預(yù)先確定的。為此，丁世飛等[13]對(duì)樣本隨機(jī)抽樣后，利用矩陣低秩逼近方法求解相似的特征向量和特征空間得到近似k值的Nystr?m采樣算法，但是抽樣的隨機(jī)性會(huì)對(duì)最終的聚類效果產(chǎn)生影響[14]。在傳統(tǒng)NJW算法基礎(chǔ)上提出的基于k近鄰的自適應(yīng)譜聚類快速FA-S[14]算法，雖然對(duì)聚類運(yùn)算速度提高了不少，但依然需要事先給出樣本的聚類數(shù)目。蔣盛益等[15]針對(duì)動(dòng)態(tài)社區(qū)發(fā)現(xiàn)提出一種增量式的譜聚類自適應(yīng)算法，提出的LLC和ADCD模型在動(dòng)態(tài)社區(qū)發(fā)現(xiàn)中具有較好的效果，但該算法只是局限于無(wú)線同構(gòu)的網(wǎng)絡(luò)。

復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)相似特性包括[16]：局部高度相似，即樣本數(shù)據(jù)節(jié)點(diǎn)在鄰近節(jié)點(diǎn)上的數(shù)據(jù)是具有較高相似度的；全局相似，即樣本數(shù)據(jù)節(jié)點(diǎn)在同一網(wǎng)絡(luò)簇中或者同一流行上是高度相似的?；诖?，提出基于密度自適應(yīng)聚類數(shù)的重疊社區(qū)發(fā)現(xiàn)譜方法，思路如下:

Step1：對(duì)樣本數(shù)據(jù)節(jié)點(diǎn)進(jìn)行密度計(jì)算，根據(jù)節(jié)點(diǎn)鄰近局部密度的定義對(duì)樣本進(jìn)行排序，依次對(duì)節(jié)點(diǎn)進(jìn)行連接完成樣本的構(gòu)圖。

Step2：將構(gòu)圖中的邊介數(shù)作為節(jié)點(diǎn)間的權(quán)值，構(gòu)造相似矩陣，并找出第一個(gè)極大特征間隙的位置來(lái)確定類的個(gè)數(shù)。

Step3：利用k-means經(jīng)典聚類算法對(duì)特征向量空間進(jìn)行聚類。

定義：若樣本數(shù)據(jù)中某節(jié)點(diǎn)νi與其所有的鄰近節(jié)點(diǎn)的距離之和比其他節(jié)點(diǎn)都小,則該節(jié)點(diǎn)處于節(jié)點(diǎn)密集區(qū)。記節(jié)點(diǎn)νi與其鄰近節(jié)點(diǎn)距離之和為Di。

Di=di1+di2+…+dij+…+dik

(5)

其中，k為節(jié)點(diǎn)νi的鄰近節(jié)點(diǎn)總數(shù)；dij為節(jié)點(diǎn)νi與節(jié)點(diǎn)νj的距離，按照距離的大小來(lái)排序?yàn)?di1≤di2≤…≤dik。

由定義可知Di的大小表示節(jié)點(diǎn)局部的稀疏層度,即Di越大，其周圍分布的節(jié)點(diǎn)越多。

2.2 基于節(jié)點(diǎn)局部密度的構(gòu)圖

根據(jù)上述節(jié)點(diǎn)局部鄰近密度的定義設(shè)計(jì)建模步驟如下:

Step1：計(jì)算每個(gè)節(jié)點(diǎn)νi所有的鄰近節(jié)點(diǎn)歐氏距離之和Di。

Step2：節(jié)點(diǎn)νi與k鄰近節(jié)點(diǎn)連接所對(duì)應(yīng)的鄰接矩陣用P表示，如果節(jié)點(diǎn)νi與節(jié)點(diǎn)νj連接則Pij=Pji=1，否則為0，初始的值即頂點(diǎn)自身值設(shè)為-1，則鄰接矩陣P可表示為:

(6)

Step3：求出最小的Di，即D(n)=min{Di,i=1,2,…,n},記num=1。

Step4：找到剩下的D(n-num)。

D(n-num)=min{Di,i=1,2,…,n-num}

(7)

D(n-num)對(duì)應(yīng)的節(jié)點(diǎn)記為νx,統(tǒng)計(jì)其鄰接矩陣中對(duì)應(yīng)行中1的總個(gè)數(shù)m,然后將其與k-m個(gè)鄰近節(jié)點(diǎn)相連,νx的鄰近節(jié)點(diǎn)集合為{νxl,l=1,2,…,k},νxl為距離節(jié)點(diǎn)νx第l近的節(jié)點(diǎn),記l=1,count=0。

Step5：若l≤k,做如下選擇:

(1)若νxl與已知νx連接,則l=l+1,循環(huán)執(zhí)行Step5直到度值達(dá)到k為止，νxl與已知νx不連接,即對(duì)應(yīng)鄰接矩陣置0,否則對(duì)應(yīng)鄰接矩陣置1,且count=count+1,l=l+1。

(2)若count>k-m,則進(jìn)入Step6,否則繼續(xù)Step5。

Step6：如果num

2.3 基于邊介數(shù)的相似矩陣構(gòu)造

上述樣本構(gòu)建的只是無(wú)向圖，這里仍需對(duì)圖的邊賦予權(quán)值，使之變?yōu)榧訖?quán)網(wǎng)絡(luò)。由于各領(lǐng)域樣本數(shù)據(jù)的多樣性，可能會(huì)出構(gòu)建出多個(gè)聯(lián)通子圖，子圖間的邊介數(shù)較少就容易求解，但是難以求解子圖內(nèi)部的邊介數(shù)。研究表明兩個(gè)節(jié)點(diǎn)或子圖之間的相似性具有傳遞性，即若Va?Vb,Vb?Vc→Va?Vc，否則節(jié)點(diǎn)或子圖不相似。為此給出定義：

(8)

其中,Wuv表示任意兩個(gè)節(jié)點(diǎn)u和v之間的值；min(eu→v)表示兩點(diǎn)間最短路徑的邊數(shù)；∑Bu→v表示節(jié)點(diǎn)u和v之間最短路徑上邊介數(shù)之和。規(guī)定,兩點(diǎn)間無(wú)連接,則權(quán)值為±∞,用來(lái)表示孤立節(jié)點(diǎn)或子圖,若兩個(gè)節(jié)點(diǎn)間的權(quán)值無(wú)窮大,則在接下來(lái)的相似矩陣中賦值為0,因?yàn)闄?quán)值矩陣的對(duì)角線值為0,所以在相似矩陣中對(duì)角線的值為1。

根據(jù)式8得到權(quán)值矩陣后,再利用倒數(shù)的方式構(gòu)建樣本數(shù)據(jù)圖的相似矩陣,公式為:

(9)

從中可以看出,兩個(gè)節(jié)點(diǎn)越是屬于同一社區(qū)越相似,則相似矩陣中值越大。

2.4 算法步驟

Input:領(lǐng)域樣本數(shù)據(jù)點(diǎn)V={v1,v2,…,vi,…,vn}和相關(guān)參數(shù)。

Output:社區(qū)劃分結(jié)果C1,C2,…,Ck。

Step1：利用上述領(lǐng)域樣本數(shù)據(jù)圖的建模方法構(gòu)建領(lǐng)域的相似圖G。

Step2：對(duì)圖G基于邊介數(shù)先求出權(quán)值矩陣W,并利用式9構(gòu)造出相似矩陣S。

Step5：將k個(gè)最大特征值所對(duì)應(yīng)的特征向量構(gòu)造矩陣V∈N×N,對(duì)每一行進(jìn)行單位化處理,處理公式如下:

(10)

Step6：把R上每一特征行看成k維空間上的節(jié)點(diǎn),利用k-means經(jīng)典聚類算法對(duì)特征向量空間進(jìn)行聚類，最后得到逼近真實(shí)的社區(qū)劃分C1,C2,…,Ck。

3 實(shí)驗(yàn)分析

為了能直觀地檢測(cè)文中算法，分別從聚類算法的精度和社區(qū)模塊度以及真實(shí)仿真三個(gè)方面設(shè)計(jì)實(shí)驗(yàn)。數(shù)據(jù)集采用UCI數(shù)據(jù)集(加州大學(xué)歐文分校提出的用于機(jī)器學(xué)習(xí)的數(shù)據(jù)庫(kù))中的Iris、Wine、Image樣本，多關(guān)系網(wǎng)絡(luò)Southern Women Data數(shù)據(jù)集[17]。對(duì)比算法包括典型的NG算法[1]、FN算法[11]、COPRA[12]算法，以及經(jīng)典譜方法，如NJW算法[8]、Nystr?m采樣算法[9]。評(píng)價(jià)指標(biāo)為模塊度Q函數(shù)[10]、重疊社區(qū)的評(píng)價(jià)模型EQ函數(shù)[11]、聚類評(píng)價(jià)的FM(Fowlkes-mallows)指數(shù)[17]。仿真對(duì)象為Southern Women Data數(shù)據(jù)集。

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

Newman等[10]提出的模塊度函數(shù)是評(píng)價(jià)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)效果常用的指標(biāo)，評(píng)價(jià)函數(shù)也叫Q函數(shù)，公式如下:

(11)

其中,Aij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的邊權(quán)值；κi表示節(jié)點(diǎn)i的度；κj表示節(jié)點(diǎn)j的度；Ci表示節(jié)點(diǎn)i歸屬的社區(qū)；m表示整個(gè)網(wǎng)絡(luò)的邊權(quán)值之和。當(dāng)Ci≠Cj時(shí),δ(Ci,Cj)=0,否則δ(Ci,Cj)=1。

研究表明[5]，模塊度Q函數(shù)在重疊社區(qū)網(wǎng)絡(luò)社區(qū)劃分時(shí)，會(huì)存在重疊問(wèn)題和極端退化現(xiàn)象。為使在重疊社區(qū)檢測(cè)效果不失真,采用文獻(xiàn)[11]提供的EQ函數(shù):

其中，ki和kj分別表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的度；X為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)；Aij表示網(wǎng)絡(luò)鄰接矩陣；Oi為節(jié)點(diǎn)i所屬社區(qū)數(shù)；Ct表示第t個(gè)子社區(qū)。

3.2 UCI數(shù)據(jù)集實(shí)驗(yàn)

UCI中的Iris、Wine、Image真實(shí)數(shù)據(jù)集的數(shù)據(jù)屬性如表1所示。將文中算法和幾種經(jīng)典算法的聚類結(jié)果利用一致性的FM(Fowlkes-mallows)評(píng)價(jià)指標(biāo)[18]進(jìn)行比較。FM取值[0,1],其值越逼近1，表明聚類結(jié)果越接近真實(shí)網(wǎng)絡(luò)。

表1 實(shí)驗(yàn)真實(shí)數(shù)據(jù)集的數(shù)據(jù)屬性

由表2可以看出，在上述3個(gè)數(shù)據(jù)集上，文中算法除了在Image數(shù)據(jù)中比Nystr?m算法FM指標(biāo)略低外，其他均高于其他算法。Nystr?m算法在大規(guī)模模糊數(shù)據(jù)上會(huì)略具優(yōu)勢(shì)，在層次結(jié)構(gòu)比較清晰的Iris和Wine數(shù)據(jù)上，文中算法還是更逼近真實(shí)值。

表2 UCI中算法的FM值

3.3 模塊度實(shí)驗(yàn)

與另一種自適應(yīng)譜聚類算法Nystr?m以及經(jīng)典的NG算法、FN算法、COPRA算法、NJW算法在QLSP數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，各算法的Q和EQ值如表3所示?？梢钥闯?，文中算法在重疊社區(qū)的領(lǐng)域檢測(cè)時(shí)，EQ指標(biāo)明顯高于其他算法。

表3 算法的Q和EQ值

3.4 仿真實(shí)驗(yàn)

Southern Women Data數(shù)據(jù)集中,如果某位婦女參與某項(xiàng)活動(dòng),婦女與活動(dòng)間就會(huì)有邊連接。將文中算法應(yīng)用在多關(guān)系網(wǎng)絡(luò)Southern Women Data數(shù)據(jù)集上，可以明顯劃分為4個(gè)社區(qū)，如圖1所示，其中方框表示活動(dòng)節(jié)點(diǎn)，圓點(diǎn)表示婦女。

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

社區(qū)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)研究中重要的課題，多數(shù)譜聚類社區(qū)發(fā)現(xiàn)算法都存在著需要提前預(yù)知聚類個(gè)數(shù)k值的問(wèn)題，基于樣本采樣近似計(jì)算k值或基于k鄰近的近似求解相似矩陣的部分改進(jìn)算法雖然能夠得到逼近的k值，但仍局限于給出的特定樣本數(shù)據(jù)。文中提出的基于密度自適應(yīng)聚類數(shù)的社區(qū)發(fā)現(xiàn)譜方法，能對(duì)樣本數(shù)據(jù)構(gòu)圖后的局部節(jié)點(diǎn)密度和邊介數(shù)進(jìn)行相似計(jì)算，自動(dòng)識(shí)別聚類個(gè)數(shù)的k值。能更精確構(gòu)造相似矩陣，得到的仿真社區(qū)結(jié)構(gòu)更逼近真實(shí)，能更適應(yīng)各種領(lǐng)域樣本數(shù)據(jù)。雖然該算法的聚類精度和仿真效果較好，但算法復(fù)雜度與傳統(tǒng)的聚類算法一樣為O(n3)，這方面尚需進(jìn)一步的研究改進(jìn)。