動(dòng)態(tài)社交網(wǎng)絡(luò)中社區(qū)劃分算法研究.pdf

1、社交網(wǎng)絡(luò)是近年來(lái)隨著網(wǎng)絡(luò)發(fā)展和普及誕生的一個(gè)新興研究領(lǐng)域。大量的研究表明在社交網(wǎng)絡(luò)中存在幾個(gè)典型的特征,如小世界性質(zhì)、無(wú)標(biāo)度性和社區(qū)結(jié)構(gòu)等。而其中對(duì)于社區(qū)結(jié)構(gòu)這一性質(zhì)的研究得到了各個(gè)研究領(lǐng)域的關(guān)注,并且提出了很多優(yōu)秀的社區(qū)探測(cè)和劃分算法。
　　針對(duì)現(xiàn)實(shí)社交網(wǎng)絡(luò)大規(guī)模的特性,很多傳統(tǒng)的社區(qū)劃分算法都具有一定的局限性,如時(shí)間開(kāi)銷較大,社區(qū)結(jié)構(gòu)劃分質(zhì)量不夠高,沒(méi)有考慮社交網(wǎng)絡(luò)結(jié)構(gòu)的特有屬性以及沒(méi)有充分考慮節(jié)點(diǎn)在網(wǎng)絡(luò)中的行為表現(xiàn)。本課題首

2、先列舉了幾個(gè)經(jīng)典的社區(qū)劃分算法,剖析了他們存在的不足以及對(duì)后面社區(qū)劃分算法的指導(dǎo)意義。然后給出了社交網(wǎng)絡(luò)靜態(tài)社區(qū)劃分算法,一個(gè)適用于大型加權(quán)網(wǎng)絡(luò)的快速社區(qū)劃分算法,該算法基于模塊度結(jié)合貪心思想來(lái)進(jìn)行節(jié)點(diǎn)的聚類,充分考慮了網(wǎng)絡(luò)結(jié)構(gòu)的特性和節(jié)點(diǎn)在網(wǎng)絡(luò)中的行為,最后算法能在較短的時(shí)間開(kāi)銷下得到一個(gè)模塊度值較高的社區(qū)劃分結(jié)果。
　　然而針對(duì)實(shí)際的網(wǎng)絡(luò)情況,網(wǎng)絡(luò)結(jié)構(gòu)不是一成不變的,通常隨著時(shí)間的變化,網(wǎng)絡(luò)中節(jié)點(diǎn)或者是節(jié)點(diǎn)之間的連接是千變?nèi)f化

3、的,因此利用傳統(tǒng)的針對(duì)靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)的社區(qū)劃分算法不再能快速有效地得到最新的社區(qū)結(jié)構(gòu)。因此本課題提出了一種基于網(wǎng)絡(luò)增量的動(dòng)態(tài)社區(qū)衍變算法,該算法將網(wǎng)絡(luò)變化行為歸為四類,提出了六種社區(qū)的衍變方向,然后針對(duì)不同的網(wǎng)絡(luò)變化行為對(duì)社區(qū)結(jié)構(gòu)進(jìn)行局部調(diào)整,最后仍然得到一個(gè)模塊度值較高的社區(qū)劃分結(jié)果。
　　最后利用了幾個(gè)經(jīng)典的真實(shí)數(shù)據(jù)集對(duì)本課題中提出的兩個(gè)算法進(jìn)行驗(yàn)證。通過(guò)實(shí)驗(yàn)表明,社交網(wǎng)絡(luò)靜態(tài)社區(qū)劃分算法能得到一個(gè)較好的社區(qū)劃分結(jié)果,是一個(gè)有效