基于泛化模塊密度的社團檢測算法研究與應用.pdf

1、近年來，復雜網絡逐漸成為描述與分析現(xiàn)實復雜系統(tǒng)的重要工具而備受關注。復雜網絡的大規(guī)模性、強耦合性、局部性等特點促使研究人員通過局部特性來刻畫與研究整體特性。其中，社團結構作為一種局部研究方法在計算機科學、生物信息學和社會學等多個領域都有重要的意義。
　　在社團檢測算法中如何有效量化社團劃分結果及如何設計出高效、準確的算法是兩大關鍵問題所在。為了解決社團量化的問題，Newman等在對比真實網絡與隨機網絡的基礎上提出了模塊度函數(shù)。盡管

2、最大化模塊度函數(shù)屬于NP-難問題，但絕大多數(shù)算法都是基于優(yōu)化模塊度函數(shù)。針對于模塊度函數(shù)存在的分辨極限問題，李等通過對比社團內部邊和外部邊密度提出了模塊密度函數(shù)，并證明了該測量標準可以在很大程度上克服分辨極限問題。但是模塊密度只能應用于無權圖。在真實網絡中，給每一個節(jié)點賦予相同的權重并不合理。為了克服該缺陷，本文提出了一種泛化的模塊密度。并設計出基于優(yōu)化加權模塊密度的模擬退火算法。實驗結果表明該測度更加有效的刻畫網絡社團結構。