在線社交網絡虛擬社區(qū)發(fā)現及演化技術研究.pdf

1、隨著信息技術的迅速發(fā)展，人類社會已經邁入了復雜網絡時代，各種超大規(guī)模網絡不斷涌現，例如智能電網、電話網絡、在線社交網絡、引文網絡等。大規(guī)模復雜網絡中的一些結構特征往往在整體范疇具有相對不變的統(tǒng)計規(guī)律，可用來理解人類社交關系的結構和行為。社區(qū)發(fā)現算法根據網絡的拓撲結構探索網絡關系的群組特征，識別出網絡中有意義的、自然的、相對穩(wěn)態(tài)的社區(qū)結構，對網絡信息的搜索與挖掘、輿論控制、信息推薦以及網絡演化預測具有重要價值。如何對大規(guī)模在線社交網絡進行

2、重疊社區(qū)發(fā)現及對動態(tài)網絡演化特征進行研究成為當前一個研究熱點。
　　由于傳統(tǒng)以節(jié)點為對象的社區(qū)發(fā)現算法不能很好地處理社區(qū)重疊部分，本文基于邊聚類思想，利用度分布符合冪律分布的性質，提出了一種快速邊聚類重疊社區(qū)發(fā)現算法HLink(Hierarchical Link)。在提高算法運行效率上，分別在連邊相似度計算和構建樹圖上進行加速。通過實驗證明該算法在處理百萬邊規(guī)模的復雜網絡上速度有明顯提升，并且劃分社區(qū)質量較高。隨著在線社交網絡規(guī)模

3、地增大，傳統(tǒng)串行算法在單機計算上遇到內存瓶頸問題，將社區(qū)發(fā)現算法與MapReduce計算框架結合，提出了一種適用于超大規(guī)模復雜網絡的并行重疊社區(qū)發(fā)現算法PHLink(Parallel Hierarchical Link)。該算法將網絡進行分割，避免了圖計算中的強耦合性，然后進行邊合并發(fā)現社區(qū)結構，解決了大規(guī)模復雜網絡的分布式存儲和計算問題。通過真實網絡測試，驗證了PHLink算法在并行環(huán)境下具有良好的加速性和伸縮性，可以處理邊規(guī)模達千萬