基于模塊性的簇結構檢測圖聚類算法研究.pdf

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

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

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