在線社會(huì)網(wǎng)絡(luò)社區(qū)劃分算法研究.pdf

1、在線社會(huì)網(wǎng)絡(luò)作為復(fù)雜網(wǎng)絡(luò)的一種,具備復(fù)雜網(wǎng)絡(luò)的一些拓?fù)涮匦?比如小世界性、無(wú)標(biāo)度性和社區(qū)結(jié)構(gòu)。近年來(lái)隨著在線社會(huì)網(wǎng)絡(luò)的快速發(fā)展,越來(lái)越多的研究者開(kāi)始對(duì)在線社會(huì)網(wǎng)絡(luò)進(jìn)行社區(qū)劃分的研究。但由于在線社會(huì)網(wǎng)絡(luò)的特性,傳統(tǒng)的社區(qū)劃分算法并不能很好的滿足需求。本文嘗試尋找一種劃分算法來(lái)對(duì)社區(qū)進(jìn)行劃分,并對(duì)重疊社區(qū)進(jìn)行社區(qū)間的優(yōu)化合并。
　　首先,通過(guò)分析國(guó)內(nèi)外研究現(xiàn)狀,對(duì)相關(guān)的基礎(chǔ)理論進(jìn)行研究學(xué)習(xí),并對(duì)經(jīng)典社區(qū)劃分算法進(jìn)行分析。然后提出一種基

2、于局部思想的社區(qū)劃分算法。該算法充分考慮在線社會(huì)網(wǎng)絡(luò)中局部社區(qū)形成的情況,任選一個(gè)節(jié)點(diǎn)利用一定的規(guī)則和算法來(lái)劃分出該節(jié)點(diǎn)所屬的社區(qū);隨后選擇簡(jiǎn)單網(wǎng)絡(luò)、Zachary空手道俱樂(lè)部網(wǎng)絡(luò)對(duì)該算法進(jìn)行驗(yàn)證,并將實(shí)驗(yàn)結(jié)果與三種經(jīng)典社區(qū)劃分算法進(jìn)行對(duì)比,證明本算法具有明顯的優(yōu)勢(shì);最后通過(guò)對(duì)一個(gè)人人網(wǎng)朋友關(guān)系數(shù)據(jù)進(jìn)行實(shí)驗(yàn),實(shí)現(xiàn)了對(duì)網(wǎng)絡(luò)的社區(qū)劃分。
　　針對(duì)在線社會(huì)網(wǎng)絡(luò)中存在大量重疊節(jié)點(diǎn)和重疊社區(qū)的情況,對(duì)現(xiàn)存的重疊社區(qū)劃分算法進(jìn)行研究分析,提出

3、適用于在線社會(huì)網(wǎng)絡(luò)的重疊社區(qū)劃分算法。該算法通過(guò)計(jì)算社區(qū)間的重疊度,并考慮重疊節(jié)點(diǎn)共享鄰居數(shù)對(duì)重疊度的影響,完善了已有的重疊度計(jì)算方法。在目前的算法中,又由于社區(qū)間存在二次合并的問(wèn)題,提出合并比來(lái)控制社區(qū)間的合并,很好的解決了這個(gè)問(wèn)題。
　　根據(jù)以上的研究成果,在對(duì)社區(qū)進(jìn)行劃分之前,我們先將社區(qū)間存在的可能的重疊節(jié)點(diǎn)進(jìn)行分裂,將重疊社區(qū)轉(zhuǎn)化為非重疊社區(qū)進(jìn)行社區(qū)劃分。然后再將劃分后的社區(qū)進(jìn)行優(yōu)化合并。選擇具有明顯重疊結(jié)構(gòu)的網(wǎng)絡(luò)進(jìn)行社