基于BFS的局部社區(qū)發(fā)現(xiàn)算法研究.pdf

1、近年來隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，越來越多的數(shù)據(jù)以網(wǎng)狀的結(jié)構(gòu)呈現(xiàn)于人們面前，而社團(tuán)結(jié)構(gòu)正是研究網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的一個重要方面。發(fā)現(xiàn)網(wǎng)絡(luò)中存在的社區(qū)結(jié)構(gòu)也成了一個很熱門的話題，許多學(xué)者對此進(jìn)行了研究。傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法關(guān)注于整個全局網(wǎng)絡(luò)結(jié)構(gòu)，這樣會具有較高的時間復(fù)雜度。而有的時候我們也不需要獲得網(wǎng)絡(luò)的全局社區(qū)結(jié)構(gòu)。比如對于網(wǎng)絡(luò)中的一個核心節(jié)點，我們想知道的是這個核心節(jié)點的覆蓋范圍，也即找到它所在的社區(qū)就可以了。因此本文提出了一種新的局部社區(qū)發(fā)現(xiàn)

2、算法。
　　本文提出的局部社區(qū)發(fā)現(xiàn)算法以起始節(jié)點相對應(yīng)的最大結(jié)合性節(jié)點為出發(fā)點，以節(jié)點相似性（兩個節(jié)點的共同鄰居節(jié)點數(shù)目）為度量并基于圖的廣度優(yōu)先搜索來進(jìn)行社區(qū)發(fā)現(xiàn)。從起始節(jié)點相對應(yīng)的最大結(jié)合性節(jié)點出發(fā)進(jìn)行社區(qū)發(fā)現(xiàn)可以避免邊界節(jié)點找不到社區(qū)的情況，提高算法的魯棒性和普適性?；趫D的廣度優(yōu)先搜索可以得到與圖的邊數(shù)呈線性規(guī)模的時間復(fù)雜度。
　　將本文提出的算法運行在四個經(jīng)典數(shù)據(jù)集上，在不降低社區(qū)發(fā)現(xiàn)精度的情況下依然顯著降低了社區(qū)