基于地理位置的網(wǎng)絡(luò)加權(quán)化社團(tuán)發(fā)現(xiàn)算法.pdf

1、自然界中存在的大量復(fù)雜系統(tǒng)都可以通過復(fù)雜網(wǎng)絡(luò)加以描述，而社團(tuán)結(jié)構(gòu)是繼小世界特性和無標(biāo)度特性之后發(fā)現(xiàn)的最為重要的復(fù)雜網(wǎng)絡(luò)特性。社團(tuán)是網(wǎng)絡(luò)中關(guān)聯(lián)緊密的一群節(jié)點(diǎn)，往往具有某些共同特征，具有一定的實(shí)際物理意義?；ヂ?lián)網(wǎng)是典型的復(fù)雜網(wǎng)絡(luò)，深入研究互聯(lián)網(wǎng)的社團(tuán)結(jié)構(gòu)可以幫助我們以分而治之的方式研究網(wǎng)絡(luò)的功能及演化過程，更加準(zhǔn)確的理解互聯(lián)網(wǎng)的組織原則、拓?fù)浣Y(jié)構(gòu)等。目前針對(duì)互聯(lián)網(wǎng)網(wǎng)絡(luò)特性的社團(tuán)發(fā)現(xiàn)研究還不足，傳統(tǒng)社團(tuán)發(fā)現(xiàn)算法并不能很好的反映互聯(lián)網(wǎng)獨(dú)有的特性

2、。同時(shí)傳統(tǒng)的社團(tuán)發(fā)現(xiàn)算法大多數(shù)不能同時(shí)發(fā)現(xiàn)社團(tuán)的重疊性和層次性。
　　本文在局部適應(yīng)度值最優(yōu)化算法(LFM)思想的基礎(chǔ)上，提出了基于共同鄰居加權(quán)的社團(tuán)發(fā)現(xiàn)算法（稱之為CNW-LFM算法）。算法中通過共同鄰居信息對(duì)邊進(jìn)行加權(quán)，其權(quán)值大小表示節(jié)點(diǎn)之間的緊密程度，并將適應(yīng)度函數(shù)以網(wǎng)絡(luò)中邊的權(quán)值重新定義。然后在多個(gè)不同類型和不同規(guī)模的真實(shí)網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，發(fā)現(xiàn)CNW-LFM算法的重疊模塊度高于原LFM算法，說明CNW-LFM算法優(yōu)于原算法，使

3、得社團(tuán)劃分結(jié)果更加合理，而且該算法可以同時(shí)發(fā)現(xiàn)社團(tuán)的重疊性以及層次性。從而證明了結(jié)合網(wǎng)絡(luò)特性進(jìn)行加權(quán)的方法是可以提高社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)的準(zhǔn)確度以及合理性，為本文重點(diǎn)研究互聯(lián)網(wǎng)社團(tuán)結(jié)構(gòu)打下了堅(jiān)實(shí)的基礎(chǔ)。
　　針對(duì)互聯(lián)網(wǎng)的宏觀拓?fù)浣Y(jié)構(gòu)下的社團(tuán)研究，在CNW-LFM算法的基礎(chǔ)上，本文提出了基于地理位置加權(quán)的社團(tuán)發(fā)現(xiàn)算法（稱之為BGW-LFM算法）。針對(duì)互聯(lián)網(wǎng)數(shù)據(jù)量龐大的問題，算法中提出了網(wǎng)絡(luò)規(guī)模的縮減方法，從而明顯地提高了時(shí)間效率。同時(shí)該算法

4、充分考慮了互聯(lián)網(wǎng)的地理特性，將地理位置信息和共同鄰居信息相結(jié)合對(duì)邊進(jìn)行加權(quán)，邊的權(quán)值依然表示節(jié)點(diǎn)之間聯(lián)系的緊密程度。然后在多個(gè)不同規(guī)模的互聯(lián)網(wǎng)網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，總結(jié)了算法中參數(shù)對(duì)社團(tuán)劃分結(jié)果的影響規(guī)律。對(duì)比實(shí)驗(yàn)中發(fā)現(xiàn)BGW-LFM算法的重疊模塊度最高，其次是CNW-LFM算法，說明BGW-LFM算法使得社團(tuán)劃分結(jié)果更加合理。最后對(duì)比分析了社團(tuán)結(jié)構(gòu)的地理分布情況，發(fā)現(xiàn)BGW-LFM算法使得社團(tuán)結(jié)構(gòu)的地理分布更為緊湊。通過兩方面的對(duì)比說明BGW