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

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

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

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