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

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

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

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