一種改進(jìn)的加權(quán)復(fù)雜網(wǎng)絡(luò)聚類方法

一種改進(jìn)的加權(quán)復(fù)雜網(wǎng)絡(luò)聚類方法

1聚類算法在復(fù)雜生物網(wǎng)絡(luò)中的應(yīng)用復(fù)雜網(wǎng)絡(luò)聚類法的研究不僅對(duì)分析復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)、理解復(fù)雜網(wǎng)絡(luò)的功能、發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)的隱藏規(guī)律以及預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)的行為具有重要的理論意義，而且具有廣闊的應(yīng)用前景。目前聚類算法在復(fù)雜生物網(wǎng)絡(luò)中的應(yīng)用主要集中在蛋白質(zhì)交互網(wǎng)絡(luò)分析預(yù)測(cè)未知蛋白質(zhì)功能、新陳代謝網(wǎng)絡(luò)分析、蛋白質(zhì)相似性網(wǎng)絡(luò)分析和基因調(diào)控網(wǎng)絡(luò)分析等領(lǐng)域。復(fù)雜網(wǎng)絡(luò)自20世紀(jì)末逐漸興起以來(lái),正迅速地在深度和廣度上與其它學(xué)科進(jìn)行交叉。一方面,從現(xiàn)實(shí)世界存在的網(wǎng)絡(luò)中不斷地發(fā)現(xiàn)新結(jié)構(gòu)與新現(xiàn)象,大量重要的應(yīng)用問(wèn)題涌現(xiàn)出來(lái);另一方面,以研究復(fù)雜網(wǎng)絡(luò)一般規(guī)律為目標(biāo)的理論研究工作也迅速發(fā)展,不斷提出新的理論模型和新的分析方法。2預(yù)備知識(shí)2.1基于優(yōu)化的方法近年來(lái),關(guān)于復(fù)雜網(wǎng)絡(luò)的研究正方興未艾,成為國(guó)際上的一個(gè)研究熱點(diǎn)。網(wǎng)絡(luò)簇結(jié)構(gòu)(networkclusterstructure)是復(fù)雜網(wǎng)絡(luò)最普遍和最重要的拓?fù)浣Y(jié)構(gòu)屬性之一。復(fù)雜網(wǎng)絡(luò)具有同簇節(jié)點(diǎn)相互連接密集、異簇節(jié)點(diǎn)相互連接稀疏的特點(diǎn)。復(fù)雜網(wǎng)絡(luò)聚類方法旨在揭示復(fù)雜網(wǎng)絡(luò)中真實(shí)存在的網(wǎng)絡(luò)簇結(jié)構(gòu)。目前已存在多種復(fù)雜網(wǎng)絡(luò)聚類算法,可以將它們中的大多數(shù)歸納為兩大類:基于優(yōu)化的方法(optimizationbasedmethod)和啟發(fā)式方法(heuristicmethod)。前者將復(fù)雜網(wǎng)絡(luò)聚類問(wèn)題轉(zhuǎn)化為優(yōu)化問(wèn)題,通過(guò)最優(yōu)化預(yù)定義的目標(biāo)函數(shù)來(lái)計(jì)算復(fù)雜網(wǎng)絡(luò)的簇結(jié)構(gòu)。后者將復(fù)雜網(wǎng)絡(luò)聚類問(wèn)題轉(zhuǎn)化為預(yù)定義啟發(fā)式規(guī)則的設(shè)計(jì)問(wèn)題。在基于優(yōu)化的方法中,譜方法采用二次型優(yōu)化技術(shù)最小化預(yù)定義的“截”函數(shù)。當(dāng)一個(gè)網(wǎng)絡(luò)被劃分為兩個(gè)子網(wǎng)絡(luò)時(shí),“截”即指子網(wǎng)間的連接密度。具有最小“截”的劃分被認(rèn)為是最優(yōu)的網(wǎng)絡(luò)劃分。采用矩陣分析技術(shù),譜方法將求解最小“截”問(wèn)題轉(zhuǎn)化為求解帶約束的二次型優(yōu)化問(wèn)題:min{(XTMX)/(XTX)}式中,向量X表示網(wǎng)絡(luò)劃分,M表示對(duì)稱半正定矩陣。對(duì)于平均“截”,M=D-A表示網(wǎng)絡(luò)的拉普拉斯矩陣(Laplacianmatrix),其中D表示由節(jié)點(diǎn)度構(gòu)成的對(duì)角矩陣,A為網(wǎng)絡(luò)的鄰接矩陣;對(duì)于其他截函數(shù),M是拉普拉斯矩陣的不同變體。由拉格朗日方法,上述約束二次型的近似最優(yōu)解(即網(wǎng)絡(luò)的近似最優(yōu)劃分)可以通過(guò)計(jì)算M的第2小特征向量求得。譜方法本質(zhì)上是一種二分法,在每次二分過(guò)程中,網(wǎng)絡(luò)被分割成兩個(gè)近似平衡的子網(wǎng)絡(luò)。當(dāng)網(wǎng)絡(luò)中含有多個(gè)簇時(shí),譜方法遞歸地分割現(xiàn)存的子網(wǎng)絡(luò),直到滿足預(yù)先定義的停止條件為止。與其他方法相比,譜方法具有明顯的優(yōu)勢(shì),該方法不僅思想簡(jiǎn)單、易于實(shí)現(xiàn)、不易陷入局部最優(yōu)解,而且具有識(shí)別非凸分布的聚類能力,非常適用于解決許多實(shí)際應(yīng)用問(wèn)題。目前將譜方法應(yīng)用于復(fù)雜網(wǎng)絡(luò)聚類的成果中,有學(xué)者利用傳統(tǒng)的K-means算法對(duì)譜方法產(chǎn)生的特征向量進(jìn)行聚類,而傳統(tǒng)的K-means算法對(duì)初始聚類中心敏感、易于陷于局部?jī)?yōu)化;有學(xué)者采用的復(fù)雜網(wǎng)絡(luò)聚類方法未將譜方法產(chǎn)生的特征向量進(jìn)行必要的處理,導(dǎo)致其方法的使用范圍具有一定的局限性。在此客觀現(xiàn)實(shí)下,本文利用譜方法具有的優(yōu)勢(shì),結(jié)合現(xiàn)有學(xué)者的研究成果,以現(xiàn)在最常用、最經(jīng)典的譜聚類算法——NJW算法為基礎(chǔ),使用魯棒性較強(qiáng)的基本PSO聚類算法,設(shè)計(jì)實(shí)現(xiàn)了一種改進(jìn)的加權(quán)復(fù)雜網(wǎng)絡(luò)聚類方法——ICMWCN方法。該方法主要是對(duì)加權(quán)網(wǎng)絡(luò)進(jìn)行聚類,其優(yōu)點(diǎn)在于譜聚類算法是一種配對(duì)聚類方法,僅與數(shù)據(jù)點(diǎn)的數(shù)目有關(guān),而與維數(shù)無(wú)關(guān),因此可以避免由于特征向量的過(guò)高維數(shù)所造成的奇異性問(wèn)題,而后選取基本PSO聚類算法對(duì)數(shù)據(jù)進(jìn)行聚類,這是因?yàn)榛谏鐣?huì)生態(tài)學(xué)的PSO算法主要是在群體的集群行為和自組織原則指導(dǎo)下的隨機(jī)搜索和優(yōu)化技術(shù),它強(qiáng)調(diào)分布式、相對(duì)簡(jiǎn)單主體之間直接或間接的交互作用,具有很強(qiáng)的適應(yīng)性和魯棒性。2.2模塊度的計(jì)算為定量分析算法的性能,本文引用社團(tuán)模塊度的概念來(lái)衡量網(wǎng)絡(luò)劃分質(zhì)量。社團(tuán)模塊度是Newman等人引進(jìn)的一個(gè)衡量網(wǎng)絡(luò)劃分質(zhì)量的度量標(biāo)準(zhǔn)。假設(shè)有某種劃分形式,將網(wǎng)絡(luò)劃分為k個(gè)社團(tuán)。定義一個(gè)k×k維的對(duì)稱矩陣E=(eij),其中eij表示網(wǎng)絡(luò)中連接兩個(gè)不同社團(tuán)的節(jié)點(diǎn)的邊在網(wǎng)絡(luò)所有邊中所占的比例,這兩個(gè)節(jié)點(diǎn)分別位于第i和第j個(gè)社團(tuán)。模塊度衡量標(biāo)準(zhǔn)是利用完整的網(wǎng)絡(luò)來(lái)計(jì)算的。模塊度Q表示為:Q=∑i(eii-a2i)=Τre-∥e2∥(1)Q=∑i(eii?a2i)=Tre?∥e2∥(1)式中,Τre=∑ieiiTre=∑ieii為矩陣E對(duì)角線上各元素之和,它表示網(wǎng)絡(luò)中連接某一個(gè)社團(tuán)內(nèi)部各節(jié)點(diǎn)的邊在所有邊的數(shù)目中所占比例;ai=∑jeijai=∑jeij為每行中各元素之和,它表示與第i個(gè)社團(tuán)中的節(jié)點(diǎn)相連的邊在所有邊中所占的比例;Q值越大說(shuō)明社團(tuán)結(jié)構(gòu)越明顯。實(shí)際網(wǎng)絡(luò)中,該值通常位于0.3～0.7之間。3基于pso算法的聚類分析對(duì)于某加權(quán)復(fù)雜網(wǎng)絡(luò)G(V,E,W),該網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)為n,給定一個(gè)簇的數(shù)目k,本文的ICMWCN方法的基本步驟如下:a)由連接權(quán)矩陣W=[wij]n×n得出網(wǎng)絡(luò)節(jié)點(diǎn)間的相似度矩陣A=[aij]n×n。若節(jié)點(diǎn)i和節(jié)點(diǎn)j之間沒(méi)有連接或者i=j,則aij=0,否則aij=1/wij。相似度矩陣A的度矩陣D=[di]n×n。其中D為對(duì)角矩陣,di=∑jaijdi=∑jaij。注意,這里考慮的均為無(wú)向網(wǎng)絡(luò)。b)用譜方法將尋找復(fù)雜網(wǎng)絡(luò)的簇結(jié)構(gòu)問(wèn)題轉(zhuǎn)換為數(shù)據(jù)的聚類問(wèn)題,即NJW算法的第1步。本文采用的是平均截,使用非規(guī)范拉普拉斯矩陣,即M=D-A。具體就是計(jì)算M=D-A的前k-1個(gè)最小特征值對(duì)應(yīng)的非平凡特征向量e1,e2,…,ek-1(el∈Rn×1,l=1,…,k-1)并組成矩陣E=[e1,…,ek-1]∈Rn×(k-1)。這里選取前k-1個(gè)最小特征值對(duì)應(yīng)的非平凡特征向量。這里的拉普拉斯矩陣是對(duì)稱半正定矩陣,它的特征值是實(shí)非負(fù)的,并且只存在一個(gè)特征值為0的特征向量,但存在k-1個(gè)特征值接近0,相應(yīng)的特征向量可以近似構(gòu)造NJW算法第1步中的矩陣。c)將E的行向量轉(zhuǎn)變?yōu)閱挝幌蛄?得到矩陣F,即:fij=eij√∑jeij2fij=eij∑jeij2√得到n個(gè)數(shù)據(jù)向量形式的待聚類數(shù)據(jù)樣本集。d)將矩陣F的每一行看作是Rk-1空間中的一個(gè)點(diǎn),用基本PSO聚類算法,對(duì)上面得到的數(shù)據(jù)樣本集F進(jìn)行聚類。e)將數(shù)據(jù)點(diǎn)fi劃分到聚類j中,當(dāng)且僅當(dāng)F的第i行被劃分到聚類j中。該算法的流程圖如圖1所示。4實(shí)驗(yàn)結(jié)果及分析本文方法采用VC++6.0實(shí)現(xiàn),在仿真實(shí)驗(yàn)平臺(tái)上對(duì)大量結(jié)構(gòu)復(fù)雜程度不同的網(wǎng)絡(luò)進(jìn)行測(cè)試后發(fā)現(xiàn),ICMWCN方法與作為對(duì)比的基于K-means聚類算法的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)新方法都具有較高的運(yùn)行效率和精確度?；贙-means聚類算法的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)新方法是將分簇后模塊度最大的簇劃分結(jié)果輸出,適用于網(wǎng)絡(luò)結(jié)構(gòu)較為復(fù)雜的網(wǎng)絡(luò),且能執(zhí)行出較好的結(jié)果。但是在一些連接緊密、結(jié)構(gòu)較復(fù)雜的網(wǎng)絡(luò)中,本文的ICMWCN方法具有更好的執(zhí)行效果和更高的執(zhí)行效率。下面選取一個(gè)節(jié)點(diǎn)數(shù)為53的加權(quán)復(fù)雜網(wǎng)絡(luò),對(duì)本文的方法進(jìn)行對(duì)比分析。如圖2所示為運(yùn)行基于K-means聚類算法的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)新方法和本文的ICMWCN方法的聚類效果圖,圖中圓形頂點(diǎn)表示被劃分到簇1中,方形頂點(diǎn)表示被劃分到簇2中,三角形頂點(diǎn)表示被劃分到簇3中。基于K-means聚類算法的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)新方法對(duì)該網(wǎng)絡(luò)分簇后,其社團(tuán)模塊度大小為0.590,整個(gè)方法執(zhí)行時(shí)間為2.129s,分簇結(jié)果如表1(a)所列。本文的ICMWCN方法對(duì)該網(wǎng)絡(luò)分簇后,其社團(tuán)模塊度大小為0.599,整個(gè)方法執(zhí)行時(shí)間為0.602s,分簇結(jié)果如表1(b)所列。結(jié)果顯示,兩方法對(duì)該網(wǎng)絡(luò)的22號(hào)節(jié)點(diǎn)的劃分產(chǎn)生了差異,其余節(jié)點(diǎn)的劃分結(jié)果完全一致。本文的ICMWCN方法執(zhí)行后,其模塊度要高出前者的1.4%,但執(zhí)行時(shí)間僅為前者的28.3%。該網(wǎng)絡(luò)節(jié)點(diǎn)間連接緊密、簇結(jié)構(gòu)較為復(fù)雜,根據(jù)實(shí)驗(yàn)結(jié)果,與對(duì)比的算法相比,本文的方法具有較好的執(zhí)行效果和更高的執(zhí)行效率。再次選取一個(gè)節(jié)點(diǎn)數(shù)為41的加權(quán)復(fù)雜網(wǎng)絡(luò),對(duì)本文的方法進(jìn)行對(duì)比分析。如圖3所示為運(yùn)行基于K-means聚類算法的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)新方法和本文的ICMWCN方法的聚類效果圖,圖中圓形頂點(diǎn)表示被劃分到簇1中,方形頂點(diǎn)表示被劃分到簇2中,三角形頂點(diǎn)表示被劃分到簇3中。基于K-means聚類算法的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)新方法對(duì)該網(wǎng)絡(luò)分簇后,其社團(tuán)模塊度大小為0.576,整個(gè)方法執(zhí)行時(shí)間為0.468s,分簇結(jié)果如表2(a)所列。本文的ICMWCN方法對(duì)該網(wǎng)絡(luò)分簇后,其社團(tuán)模塊度大小為0.598,整個(gè)方法執(zhí)行時(shí)間為0.421s,分簇結(jié)果如表2(b)所列。結(jié)果顯示,對(duì)比方法將11號(hào)節(jié)點(diǎn)劃分到簇3中,而本文的ICMWCN方法將11號(hào)節(jié)點(diǎn)劃分到簇1中。觀察11號(hào)節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置,它與8號(hào)、24號(hào)、32號(hào)節(jié)點(diǎn)是鄰居,8號(hào)和32號(hào)節(jié)點(diǎn)相連且它們的度都很大,而24號(hào)節(jié)點(diǎn)度為2,與周圍節(jié)點(diǎn)連接稀疏,因此將11號(hào)節(jié)點(diǎn)劃分到包含8號(hào)和32號(hào)節(jié)點(diǎn)的簇1中明顯要比將其劃分到只包含24號(hào)節(jié)點(diǎn)的簇3中更加合理,更加滿足簇內(nèi)節(jié)點(diǎn)間連接緊密、簇間節(jié)點(diǎn)間連接稀疏的定義。經(jīng)過(guò)計(jì)算,本文的ICMWCN方法執(zhí)行后的模塊度要高出前者的3.8%,執(zhí)行時(shí)間為前者的90.0%,顯示出ICMWCN方法對(duì)該網(wǎng)絡(luò)分簇有較好的執(zhí)行效果和較高的運(yùn)行效率。對(duì)另外3個(gè)加權(quán)網(wǎng)絡(luò)進(jìn)行聚類,對(duì)比算法和ICMWCN方法的執(zhí)行效果如表3所列。根據(jù)表3所列的實(shí)驗(yàn)結(jié)果發(fā)現(xiàn),相比基于K-means聚類算法的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)新方法,本文的ICMWCN方法在執(zhí)行時(shí)間和聚類精確度上都具有一定的優(yōu)勢(shì),這種優(yōu)勢(shì)尤其表現(xiàn)在算法的執(zhí)行時(shí)間和效率上。本文的ICMWCN方法是將PSO聚類算法和譜方法中的平均截方法相結(jié)合的加權(quán)復(fù)雜網(wǎng)絡(luò)聚類方法。該方法的算法復(fù)雜度為O(max{n2,p×t×n})(其中n為復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù),p為基本PSO聚類算法中初始設(shè)置的粒子數(shù),t為基本PSO聚類算法的迭代次數(shù)),相比基于K-means聚類算法的復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)新方法的算法復(fù)雜度O(m×n3)(其中m為復(fù)雜網(wǎng)絡(luò)的邊數(shù),n為復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)),其算法復(fù)雜度低,實(shí)現(xiàn)步驟簡(jiǎn)單。該方法使用基本PSO聚類算法克服了傳統(tǒng)K-means聚類算法對(duì)初始聚類中心敏感以及易于陷于局部?jī)?yōu)化等缺點(diǎn),在結(jié)構(gòu)復(fù)雜、連接緊密的網(wǎng)絡(luò)中有更快的執(zhí)行速度、更好的聚類效果和精準(zhǔn)度。結(jié)束語(yǔ)首先對(duì)現(xiàn)有的復(fù)雜網(wǎng)絡(luò)聚類算法進(jìn)行了簡(jiǎn)單的分析,然后結(jié)合現(xiàn)有的知識(shí)設(shè)計(jì)和實(shí)現(xiàn)了基于NJW算法的改進(jìn)加權(quán)