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

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

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

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

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