基于高斯混合模型和非負(fù)矩陣分解的復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè).pdf

1、復(fù)雜網(wǎng)絡(luò)可能是復(fù)雜系統(tǒng)中的新的跨學(xué)科的科學(xué)中最活躍的領(lǐng)域，許多復(fù)雜系統(tǒng)可以用網(wǎng)絡(luò)來(lái)表示，系統(tǒng)的基本部件和它們的相互交流分別表示節(jié)點(diǎn)和邊。近年來(lái)，復(fù)雜網(wǎng)絡(luò)的社區(qū)檢測(cè)已經(jīng)吸引了許多相關(guān)領(lǐng)域?qū)W者的關(guān)注，許多復(fù)雜網(wǎng)絡(luò)，包括因特網(wǎng)，引用網(wǎng)絡(luò)，運(yùn)輸網(wǎng)，電子郵件網(wǎng)絡(luò)，社交網(wǎng)絡(luò)和生化網(wǎng)絡(luò)，都存在一定的社區(qū)結(jié)構(gòu)。不嚴(yán)格地講，社區(qū)結(jié)構(gòu)是指社區(qū)內(nèi)部的節(jié)點(diǎn)連接較緊密，而社區(qū)之間的連接相對(duì)稀疏。社區(qū)結(jié)構(gòu)能加深我們對(duì)一些現(xiàn)象的理解，復(fù)雜網(wǎng)絡(luò)的社區(qū)檢測(cè)有許多應(yīng)用，從

2、社交網(wǎng)絡(luò)分析到圖像分割，從分析蛋白質(zhì)相互作用網(wǎng)絡(luò)到電路布置問(wèn)題。社區(qū)檢測(cè)算法就是用來(lái)支持在線社交網(wǎng)絡(luò)的核心服務(wù)。其最普遍的功能，比如朋友推薦、個(gè)性化商品推薦等，都要求在大規(guī)模圖中快速的發(fā)現(xiàn)社區(qū)結(jié)構(gòu)。近年來(lái)，很多社區(qū)檢測(cè)方法相繼被提了出來(lái)，有基于圖分割的方法，基于模塊度優(yōu)化的方法，基于統(tǒng)計(jì)推斷和數(shù)學(xué)建模的方法，還有基于層次聚類(lèi)的方法。
　　復(fù)雜網(wǎng)絡(luò)的社區(qū)檢測(cè)與數(shù)據(jù)聚類(lèi)分析很相似，本文在對(duì)已有的復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)算法進(jìn)行深入研究的基礎(chǔ)上

3、，將高斯混合模型（Gaussian Mixture Model，GMM）應(yīng)用在了復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)問(wèn)題研究中。還將非負(fù)矩陣分解（Non-Negative Matrix Factorization，NMF）思想應(yīng)用到社區(qū)檢測(cè)算法中，由于該算法具有簡(jiǎn)便性以及占用存儲(chǔ)空間少等優(yōu)點(diǎn)，從而為處理大規(guī)模數(shù)據(jù)提供了一種新的途徑。本文所做的工作如下：
　　1.研究了蟻群優(yōu)化算法（Ant Colony Optimization，ACO）的基本理論，A

4、CO作為單目標(biāo)優(yōu)化問(wèn)題，由于只有一個(gè)目標(biāo)函數(shù)，通常會(huì)將解限制到特定的范圍內(nèi)。當(dāng)優(yōu)化的目標(biāo)不恰當(dāng)時(shí)，算法可能失效，比如分辨率限制問(wèn)題。該算法引入了多目標(biāo)策略，提出了多目標(biāo)ACO算法，該算法在一次運(yùn)行過(guò)程中會(huì)產(chǎn)生一組Pareto最優(yōu)解。在三個(gè)真實(shí)世界網(wǎng)絡(luò)證明該算法的有效性和準(zhǔn)確性。
　　2.研究了基于高斯混合模型的復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)方法，將（Gaussian Mixture Model，GMM）模型用于社區(qū)檢測(cè)領(lǐng)域，傳統(tǒng)的GMM采用最大

5、似然估計(jì)（Maximum Likelihood，ML）估計(jì)對(duì)模型參數(shù)進(jìn)行優(yōu)化，ML估計(jì)是一種局部搜索算法，對(duì)初始值十分敏感，容易陷入極小值而得不到最優(yōu)解。針對(duì)這一缺點(diǎn)，我們提出了使用遺傳算法對(duì)參數(shù)進(jìn)行優(yōu)化，并且在初始化參數(shù)時(shí)使用 K-means算法，得到一個(gè)粗略的聚類(lèi)中心來(lái)初始化參數(shù)。實(shí)驗(yàn)表明，該算法較傳統(tǒng)的參數(shù)估計(jì)方法能夠得到更優(yōu)的參數(shù)。
　　3.研究了復(fù)雜網(wǎng)絡(luò)中的社區(qū)交疊現(xiàn)象，將 NMF算法用于社區(qū)檢測(cè)問(wèn)題。傳統(tǒng)的用于社區(qū)檢測(cè)