局部社區(qū)發(fā)現(xiàn)方法研究.pdf

1、社會網絡是指社會個體成員之間因為互動而形成的相對穩(wěn)定的關系體系[1]。經過研究發(fā)現(xiàn)社會網絡具有高度的社區(qū)特性,社區(qū)內部成員間聯(lián)系相對緊密,不同社區(qū)間的成員聯(lián)系相對稀疏[2]。社區(qū)發(fā)現(xiàn)技術就是要對社會網絡中的社區(qū)進行挖掘。近些年,隨著信息技術的發(fā)展尤其是萬維網的發(fā)展社會網絡呈現(xiàn)出了新的特點,比如:規(guī)模龐大、社區(qū)成員間具有多重聯(lián)系、網絡更新演變等等?，F(xiàn)在主要的社區(qū)發(fā)現(xiàn)技術多半已經不能適應這些新的特性。
　　針對當前算法的不足,本課題將

2、大規(guī)模社會網絡中的快速局部社區(qū)發(fā)現(xiàn)技術作為研究的重點方向。局部社區(qū)發(fā)現(xiàn)是指:從一個點或者一些點出發(fā),找到它們所在的局部社區(qū)。本課題的主要工作包括:
　　(1)本課題通過研究發(fā)現(xiàn)社區(qū)具有局部性特點。社區(qū)具有局部特性,一個人由于其交際范圍所限,其社區(qū)會呈現(xiàn)局部性特點。小的社區(qū)會凝結成大的社區(qū),而社區(qū)間具有相對的獨立性。因此在社區(qū)發(fā)現(xiàn)的過程中可以利用局部性的特點減少算法的時空開銷。
　　(2)本課題提出了一種新的局部社區(qū)發(fā)現(xiàn)框架。

3、根據社區(qū)局部性的特點,可以發(fā)現(xiàn):如果能夠找到目標局部社區(qū)所在的子圖,就可以在該子圖內進行社區(qū)發(fā)現(xiàn),進而找到目標局部社區(qū)。該框架算法首先利用隨機漫游(random walk)找到一個包含目標社區(qū)的局部子圖,然后在該子圖上進行社區(qū)發(fā)現(xiàn),進而找到目標局部社區(qū)。通過大量的實驗證明,該框架算法具有很好的社區(qū)發(fā)現(xiàn)效果,并且具有較小的時空開銷。
　　(3)本課題提出了一種利用局部社區(qū)發(fā)現(xiàn)結果組合出全局社區(qū)劃分的算法框架。局部社區(qū)發(fā)現(xiàn)算法有較小的