基于圖壓縮的重疊社區(qū)發(fā)現(xiàn)技術研究.pdf

1、近年來，尋找復雜網(wǎng)絡中的社區(qū)結構已經(jīng)成為復雜網(wǎng)絡中研究的熱點，社區(qū)發(fā)現(xiàn)問題也因此成為近年復雜網(wǎng)絡領域中的熱門問題。由于現(xiàn)實存在的網(wǎng)絡社區(qū)通常并不是絕對彼此獨立的，而是彼此重疊的，并且重疊社區(qū)可以反映更加真實的網(wǎng)絡結構，因此關于重疊社區(qū)發(fā)現(xiàn)問題的討論也成了復雜網(wǎng)絡中的研究重點。
　　本文先從社區(qū)發(fā)現(xiàn)的研究背景、意義出發(fā)，通過介紹基本理論知識，引出社區(qū)結構的概念，隨后綜述了近年來社會網(wǎng)絡中社區(qū)結構的研究成果，介紹了目前主要的重疊社區(qū)發(fā)

2、現(xiàn)算法，并對它們的優(yōu)缺點進行了對比與分析。針對大多數(shù)現(xiàn)有的重疊社區(qū)發(fā)現(xiàn)算法在應用大規(guī)模網(wǎng)絡時效率較低的問題，本文基于圖壓縮提出一個新的重疊社區(qū)發(fā)現(xiàn)算法，能在保證準確度的前提下，數(shù)量級地提高在單機上處理的網(wǎng)絡規(guī)模，進而發(fā)現(xiàn)重疊社區(qū)。首先，通過基于圖壓縮的社區(qū)結構表示模型——凝聚圖，來對網(wǎng)絡進行無損壓縮。然后，在凝聚圖上基于種子迭代的思想，通過不斷優(yōu)化社區(qū)適應度函數(shù)來對種子進行擴展。當種子的社區(qū)適應度達到最大時，便形成社區(qū)。最后，再將相似度