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

1、基于生成模型和矩陣分解的社區(qū)發(fā)現(xiàn)算法研究CommunityDetectionAlgithmsbasedonGenerativeModelMatrixFactization一級(jí)學(xué)科：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科專業(yè)：計(jì)算機(jī)應(yīng)用技術(shù)研究生：王嘯指導(dǎo)教師：操曉春研究員天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院二零一五年十二月摘要真實(shí)世界不同領(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é)點(diǎn)連接緊密，不同社區(qū)的節(jié)點(diǎn)

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

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

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