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

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

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

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