14618.基于生成模型和矩陣分解的社區(qū)發(fā)現(xiàn)算法研究

1、基于生成模型和矩陣分解的社區(qū)發(fā)現(xiàn)算法研究CommunityDetectionAlgithmsbasedonGenerativeModelMatrixFactization一級學(xué)科：計算機科學(xué)與技術(shù)學(xué)科專業(yè)：計算機應(yīng)用技術(shù)研究生：王嘯指導(dǎo)教師：操曉春研究員天津大學(xué)計算機科學(xué)與技術(shù)學(xué)院二零一五年十二月摘要真實世界不同領(lǐng)域的很多復(fù)雜系統(tǒng)都可以抽象為復(fù)雜網(wǎng)絡(luò)，復(fù)雜網(wǎng)絡(luò)的關(guān)鍵特征之一是社區(qū)結(jié)構(gòu)。它是指網(wǎng)絡(luò)中同一社區(qū)內(nèi)的節(jié)點連接緊密，不同社區(qū)的節(jié)點

2、連接稀疏。社區(qū)結(jié)構(gòu)對理解網(wǎng)絡(luò)的組織結(jié)構(gòu)和不同功能性模塊間的交互提供了有價值的信息，因此成為復(fù)雜網(wǎng)絡(luò)領(lǐng)域的重要研究內(nèi)容之一。本文主要基于生成模型和非負矩陣分解算法，對無監(jiān)督和半監(jiān)督社區(qū)發(fā)現(xiàn)問題進行研究，并提出相應(yīng)的社區(qū)發(fā)現(xiàn)算法。主要工作如下：（1）“橫向”視角看，社區(qū)結(jié)構(gòu)中的一個普遍結(jié)構(gòu)是重疊社區(qū)，同時網(wǎng)絡(luò)中也會有一些中心節(jié)點和異常節(jié)點。本文提出了一種新的生成模型，通過非負矩陣分解的優(yōu)化方法求解模型參數(shù)，能夠天然發(fā)現(xiàn)這三種結(jié)構(gòu)。實驗結(jié)果顯

3、示該模型能夠發(fā)現(xiàn)有更高質(zhì)量的重疊社區(qū)結(jié)構(gòu)，而且同時識別重疊社區(qū)、中心節(jié)點和異常節(jié)點能為分析網(wǎng)絡(luò)提供更多信息。（2）“縱向”視角看，不同的分辨率層次下有不同的社區(qū)規(guī)模，同時發(fā)現(xiàn)層次和重疊社區(qū)對理解網(wǎng)絡(luò)可以提供更豐富的信息。本文將對稱非負矩陣分解方法和l21范數(shù)正則項結(jié)合，來檢測層次和重疊社區(qū)結(jié)構(gòu)。l21范數(shù)可以懲罰無意義的社區(qū)，達到自動選擇社區(qū)的目的。進而通過引入分辨率參數(shù)，可以得到不同分辨率參數(shù)下的社區(qū)個數(shù)，達到同時檢測層次和重疊社區(qū)的

4、目的。（3）網(wǎng)絡(luò)中除了拓撲結(jié)構(gòu)信息，還有節(jié)點的標簽以及節(jié)點之間的mustlink約束信息。本文提出一種半監(jiān)督學(xué)習(xí)模型融合這兩種信息，保證了具有相同標簽或者相互之間有mustlink約束的節(jié)點被分到同一個社區(qū)。進而本文又提出了基于節(jié)點拓撲結(jié)構(gòu)線性表達的主動學(xué)習(xí)模型，該模型能夠選擇出最有代表性的節(jié)點，通過引入這些關(guān)鍵節(jié)點的非拓撲信息，能盡可能提高半監(jiān)督社區(qū)發(fā)現(xiàn)方法的有效性。本文提出的社區(qū)發(fā)現(xiàn)新方法，是對社區(qū)發(fā)現(xiàn)相關(guān)問題的有效探索，豐富了相關(guān)