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

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

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