圖劃分和社區(qū)檢測研究.pdf

1、隨著信息時代的來臨,我們的生活已經(jīng)無形中被各種網(wǎng)絡(luò)包圍,比如萬維網(wǎng)和社交網(wǎng)絡(luò)。眾多學(xué)者都加入到復(fù)雜網(wǎng)絡(luò)的研究中來。現(xiàn)在網(wǎng)絡(luò)劃分,即社區(qū)檢測,已經(jīng)成為復(fù)雜網(wǎng)絡(luò)領(lǐng)域的熱點問題。很多學(xué)者已經(jīng)提出了很多優(yōu)秀的社區(qū)檢測算法。但是目前的算法或多或少的存在著一些問題。有的需要先驗知識,必須要知道社區(qū)的個數(shù),以及社區(qū)的大小。有的算法是雖然效果較好,但是因為復(fù)雜度過高,只能解決小型網(wǎng)絡(luò)。有的算法則要依賴于網(wǎng)絡(luò)節(jié)點輸入的排列順序。在這里本文在對于網(wǎng)絡(luò)社區(qū)劃

2、分以及圖劃分的研究的基礎(chǔ)上,分別提出了,基于閾值的社區(qū)檢測算法,基于相似度的符號網(wǎng)絡(luò)社區(qū)檢測算法?；?Memetic的加權(quán)無向圖劃分算法,并且都取得優(yōu)秀的實驗結(jié)果。
　　(1)提出基于閾值的社區(qū)檢測算法。該算法分為壓縮模塊,再優(yōu)化模塊以及局部搜索模塊。在壓縮模塊中,提出新的相似度函數(shù),同時在局部搜索模塊里把一個在圖分割領(lǐng)域非常高效的禁忌算法經(jīng)過改進來優(yōu)化社區(qū)劃分的結(jié)果,并且最終效果顯著。同時本算法的執(zhí)行效率較高,能夠處理十萬以內(nèi)

3、的大規(guī)模網(wǎng)絡(luò)。
　　(2)提出基于相似度的符號網(wǎng)絡(luò)社區(qū)檢測算法。在該算法中,我們提出一個全新的相似度函數(shù),并且該函數(shù)的設(shè)計特別考慮到符號網(wǎng)絡(luò)中的邊的權(quán)值有正有負的情況。同時,本算法還引用經(jīng)過修改以后的增量的模塊度函數(shù)來作為本聚類算法的終止條件。這樣,最終本算法在和符號網(wǎng)絡(luò)領(lǐng)域比較優(yōu)秀的FEC的算法對比實驗中,取得較好效果。并且本算法不需要任何先驗知識。
　　(3)基于 Memetic的節(jié)點加權(quán)圖劃分算法。在該算法中,我們吸收