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

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

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

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