基于模塊性的簇結(jié)構(gòu)檢測(cè)圖聚類算法研究.pdf

1、網(wǎng)絡(luò)簇結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)中重要的拓?fù)浣Y(jié)構(gòu)，通過(guò)檢測(cè)簇結(jié)構(gòu)可以分析復(fù)雜網(wǎng)絡(luò)的拓?fù)湫再|(zhì)，反映復(fù)雜網(wǎng)絡(luò)的功能特性。從大規(guī)模的復(fù)雜網(wǎng)絡(luò)中挖掘重要的簇結(jié)構(gòu)(Community structure)已經(jīng)成為當(dāng)今研究的熱點(diǎn)之一。近年來(lái)，圖聚類算法在檢測(cè)復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu)中扮演著極其重要的角色，如在社會(huì)網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、引文網(wǎng)絡(luò)等領(lǐng)域都得到了非常好的實(shí)際應(yīng)用。
　　本文對(duì)面向復(fù)雜網(wǎng)絡(luò)檢測(cè)簇結(jié)構(gòu)問(wèn)題進(jìn)行分析，研究發(fā)現(xiàn)相較于密度性，模塊性能夠更好地體現(xiàn)簇結(jié)構(gòu)的

2、拓?fù)浣Y(jié)構(gòu)，并對(duì)聚類算法的效能和聚類結(jié)果具有決定性作用。因此本文針對(duì)復(fù)雜網(wǎng)絡(luò)中基于模塊性的圖聚類算法，對(duì)算法過(guò)程中的邊權(quán)重定義、種子選擇與擴(kuò)展等問(wèn)題展開研究，提出一種檢測(cè)復(fù)雜網(wǎng)絡(luò)中稠密簇結(jié)構(gòu)的局部模塊性圖聚類算法LMC。主要工作如下：
　　(1)基于端點(diǎn)的相似性，定義了邊權(quán)重 w，在此基礎(chǔ)上給出了簇結(jié)構(gòu)的模塊性定義以及頂點(diǎn)對(duì)簇結(jié)構(gòu)的適應(yīng)度函數(shù)。其中模塊性度量了簇結(jié)構(gòu)的抱團(tuán)性，適應(yīng)度函數(shù)體現(xiàn)了一個(gè)頂點(diǎn)對(duì)簇結(jié)構(gòu)的影響程度。
　　(

3、2)提出了基于“種子邊-擴(kuò)展”策略的復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu)檢測(cè)算法LMC。首先，根據(jù)所給出的邊權(quán)重定義選取種子邊，形成初始簇；計(jì)算當(dāng)前簇的模塊性，并計(jì)算當(dāng)前簇的局部鄰域內(nèi)結(jié)點(diǎn)對(duì)簇的適應(yīng)度函數(shù)，對(duì)其進(jìn)行擴(kuò)展，直到簇的模塊性達(dá)到局部最大值；在此過(guò)程中，一個(gè)頂點(diǎn)可能同時(shí)屬于多個(gè)簇結(jié)構(gòu)。
　　(3)本文給出的 LMC算法是一個(gè)可以檢測(cè)復(fù)雜網(wǎng)絡(luò)中稠密簇結(jié)構(gòu)的軟聚類方法。最后，將聚類算法 LMC分別在人工模擬數(shù)據(jù)及真實(shí)蛋白質(zhì)網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn)比較，結(jié)果表