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

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

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

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