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

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

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

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