本站小編為你精心準備了網絡拓撲結構的聚類方法比較參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

近幾年，在探索復雜網絡拓撲結構的過程中，研究者除發現小世界與無標度特性外，還發現復雜網絡還存在一個基本屬性:社團結構(communitystruc-ture)［1］。復雜網絡是由若干個社團組成，社團內部節點的連接非常緊密，社團之間節點的連接相對比較稀疏。結構決定功能，研究網絡的社團結構有助于分析復雜網絡的功能、探索復雜網絡的隱藏規律以及預測復雜網絡的發展趨勢。為了能夠精確界定網絡中的社團結構，必須選擇一種優秀的聚類方法?，F有的復雜網絡聚類方法主要分為兩大類，一類是基于圖論的算法，如Ker-nighan－Lin法、譜平分法、隨機游走法(Walk-trapalgorithm)和標簽傳播法(Labelpropagationalgorithm);另一類是層次聚類方法，層次聚類本身又分為凝聚與分裂算法，其中凝聚算法包括New-man快速算法和最大模塊度算法(BGllalgo-rithm)等，分裂算法中最為經典的是Girvan和Newman提出的邊介數算法(Girvan－Newmanalgo-rithm)。此外，近幾年又有許多從其他不同角度提出的劃分網絡社團結構的聚類算法，如基于電阻網絡性質的算法、基于信息論的算法等。在文獻領域，以語義相似性算法構造出的論文相似網絡能夠直接反映文獻內容的相似程度。因而以此網絡為基礎，分析該網絡的社團結構，可以清晰地描述出學科結構的動態變化與專業主題的研究熱點，并為文獻影響力的評價提供新的視角。為了找到最適合論文相似網絡的聚類算法，本文以語義相似算法構造論文相似網絡，并針對性地選擇了4種代表性聚類方法(基于圖論的隨機游走算法和標簽傳播算法，層次聚類中的最大模塊度法和邊介數法)對構建出的網絡進行聚類分析，并結合樣本數據的金標準和網絡社團劃分評價指標D函數［10］比較4種算法的準確性和穩定性。

1材料與方法

在OHSUMED試驗數據集中選擇6個查詢提問(queries)作為研究主題，收集與其明確相關(defi-nitelyrelated)的109篇文獻作為樣本數據。其中6號主題19篇，27號主題36篇，32號主題14篇，42號主題13篇，84號主題22篇，98號主題5篇。為了直接反映文獻內容的相關性，采用語義相似性算法［11］構造論文相似網絡，即用文獻的主題詞代表論文，通過計算主題詞間的相似性得出文獻間的相似程度。利用本地PubMed檢索系統中基于語義相似性的PANS(PaperNetworkonSimilarity)算法直接生成論文相似矩陣(表1)，矩陣中的元素代表相應兩篇文獻間內容上的相似性。為使聚類結果更準確，選擇0．08作為相似度閾值，移除相似度小于等于0．08的邊，得到簡化后的相似矩陣(表2)。在R語言的igraph程序包中，以上述兩個相似矩陣為鄰接矩陣構造論文網絡，得到原始的論文網絡(簡稱網絡1，圖1)和簡化的論文網絡(簡稱網絡2，圖2)，并進行可視化處理。網絡1和網絡2都是無向加權圖，每個節點代表1篇文獻，邊的權重代表文獻間的相似度值。其中網絡1共109個節點，5886條邊;網絡2含109個節點，1621條連接(圖中標簽代表金標準的主題號)。利用igraph程序包的復雜網絡處理算法功能，分別采用4種聚類算法對網絡1和網絡2進行聚類分析，探索論文相似網絡的社團結構，最后結合金標準的主題分類和網絡社團劃分評價指標D函數比較4種算法的準確性和穩定性。

2結果

按照金標準的主題分類，論文相似網絡擁有6個社團(圖3)，其中社團1(第98號主題)5個節點，社團2(第27號主題)36個節點，社團3(第6號主題)19個節點，社團4(第84號主題)22個節點，社團5(第32號主題)14個節點，社團6(第42號主題)13個節點。采用4種算法對網絡1和網絡2聚類的結果如圖4－圖11所示。圖中節點標簽數字代表金標準的主題號，標簽顏色相同的節點屬于同一個社團，社團內連線為黑色，社團間連線為紅色。4種算法得出的聚類結果的具體數據如表3和表4所示。采用隨機游走算法分析論文相似網絡，并對網絡進行聚類分析，如圖4所示，準確率高達96．3%，社團數為6，但第6號主題的一個節點與98號主題的5個節點被錯誤歸為一類。簡化剪枝后，準確率為100%，聚類結果(圖5)與實際社團劃分情況完全相同。采用標簽傳播算法對網絡1進行聚類分析，如圖6所示，準確率高達81．3%。它將27號主題與98號主題歸為一類，因此社團數目只有5。但對網絡2的聚類結果跟隨機游走算法一樣(圖7)，也是與實際一致。采用最大模塊度算法對論文相似網絡聚類分析時，網絡處理前后的結果是一致的(圖8和圖9)，二者都是將42號主題與98號主題聚為一類，從而得到5個社團，但在處理兩個網絡時得到的Q值都是最大的。邊介數算法對于原始網絡的聚類效果較差，如圖10所示，模塊度Q僅為0．045，57個社團中僅1個社團的節點數超過1，其余社團均只含1個節點。網絡剪枝后，GN法得到6個社團(圖11)，準確率高于90%，僅98號主題有2個節點被錯誤歸為42號主題。

3討論

由于不同主題文獻之間的相似性大都較低(全部＜0．1)，導致同一主題內的任意兩篇文獻與其他主題文獻的相似性差異很小。這符合隨機游走算法的前提，即若兩個節點同屬于一個社團，那么分別從兩個頂點跳躍到整個網絡的其他節點的概率相近:如果頂點i和頂點j屬于同一社團，則對于任一頂點k有Ptik≈Ptjk。標簽傳播算法的兩次聚類結果差距較大，說明其穩定性較差。這是由于它的更新順序是隨機的、鄰接節點標簽數量相同時選擇標簽也是隨機的，算法的魯棒性遭到嚴重破壞，社區結構的穩定性也就受到嚴重損害。最大模塊度算法則更為穩定，具有以下優點:計算速度快，可用于大型網絡;整個過程自下而上，不會遺漏小規模的社團結構;適用于大規模的加權網絡。邊介數算法的前提是連接不同社團間的邊的介數值較大，而連接社團內部邊的介數值則較小。但由于原始論文相似網絡中任意兩點之間都存在連接，無法滿足此前提，因此聚類結果無意義。

4結語

在構建文獻相似網絡的基礎上，通過比較4種聚類算法的聚類精度和聚類穩定性，我們發現，隨機游走算法是一種優秀的論文相似網絡聚類算法，準確性高、穩定性好;標簽傳播算法的準確性次之，但穩定性不高;最大模塊度算法穩定性好，但聚類精度有待提高;邊介數算法對相似網絡的預處理要求很高，聚類結果不穩定。另外，我們還發現，選擇閾值處理相似網絡后聚類效果顯著提高，說明選擇不同的相似度閾值會對聚類結果產生影響，可見復雜網絡的預處理也是一個影響其聚類效果的重要因素。本研究為今后選擇更為準確和穩定的論文相似網絡聚類算法提供了依據。在今后的研究中，應選擇隨機游走算法對文獻相似性網絡進行聚類分析，并且可以嘗試通過閾值的選取來提高文獻相似網絡的聚類精度。文本聚類分析技術的進一步改進，一是有助于揭示學科結構及其動態變化，在精確計算論文相似性基礎上，形成準確的網絡并精確地聚類分析，隨時反映不同學科專業主題當前研究的熱點和結構;二是有助于成簇檢索相關文獻，可以將基于隨機游走算法鑲嵌在文獻檢索系統中，將用戶檢索到的文獻集合中相似論文按照類別提供給檢索用戶，提高信息咨詢服務的準確度和針對性。

作者：黃鵬 崔雷 單位：中國醫科大學醫學信息學院