復(fù)雜網(wǎng)絡(luò)中社團(tuán)發(fā)現(xiàn)算法的研究.pdf

1、復(fù)雜網(wǎng)絡(luò)的研究是現(xiàn)今科學(xué)研究中的一個(gè)重要研究方向。復(fù)雜網(wǎng)絡(luò)中存在著大量的社團(tuán)結(jié)構(gòu)。發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)是了解整個(gè)復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)和功能的重要途徑。隨著信息量的急劇增長，經(jīng)典的社團(tuán)發(fā)現(xiàn)算法由于時(shí)間復(fù)雜度高，已經(jīng)無法完成大規(guī)模復(fù)雜網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)，研究準(zhǔn)確度高且時(shí)間復(fù)雜度低的大規(guī)模復(fù)雜網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)算法迫在眉睫。由于社團(tuán)中的重要節(jié)點(diǎn)在社團(tuán)中具有很大的影響力，所以發(fā)現(xiàn)社團(tuán)中的重要節(jié)點(diǎn)對網(wǎng)絡(luò)的安全、控制和監(jiān)管具有重要意義。然而常見的重要節(jié)點(diǎn)發(fā)現(xiàn)算

2、法考慮因素片面單一，且是用于尋找全網(wǎng)中的重要節(jié)點(diǎn)，因此，就需要探索考慮因素周全的社團(tuán)中重要節(jié)點(diǎn)的發(fā)現(xiàn)算法。
　　經(jīng)典的社團(tuán)發(fā)現(xiàn)算法主要研究的是無權(quán)網(wǎng)。無權(quán)網(wǎng)無法體現(xiàn)出網(wǎng)絡(luò)中節(jié)點(diǎn)之間的連接強(qiáng)度，且大多真實(shí)的網(wǎng)絡(luò)是加權(quán)網(wǎng)。這些網(wǎng)絡(luò)用加權(quán)網(wǎng)絡(luò)模型描述更加合理，因此本文在對復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)發(fā)現(xiàn)前先對具有社團(tuán)結(jié)構(gòu)的加權(quán)網(wǎng)建模?？紤]到兩點(diǎn)間的連接次數(shù)、共同鄰點(diǎn)的個(gè)數(shù)和點(diǎn)權(quán)的影響，本文建立了基于共同鄰點(diǎn)的加權(quán)網(wǎng)模型。本文分別對3個(gè)標(biāo)準(zhǔn)測試網(wǎng)絡(luò)用

3、基于共同鄰點(diǎn)的加權(quán)網(wǎng)模型建模，驗(yàn)證了此模型中節(jié)點(diǎn)的度和點(diǎn)權(quán)都符合冪律分布。
　　目前大多數(shù)的社團(tuán)發(fā)現(xiàn)算法利用全局模塊度對節(jié)點(diǎn)進(jìn)行社團(tuán)劃分，時(shí)間復(fù)雜度高，本文提出了基于鄰邊的局部社團(tuán)發(fā)現(xiàn)算法。結(jié)合局部社團(tuán)的鄰邊特性，本文提出了局部社團(tuán)的判斷函數(shù)，并對加權(quán)網(wǎng)的邊進(jìn)行社團(tuán)劃分，發(fā)現(xiàn)重疊社團(tuán)。然后定義了重疊點(diǎn)的歸屬判斷函數(shù)對重疊點(diǎn)進(jìn)一步劃化，從而得到非重疊社團(tuán)。本文對3個(gè)標(biāo)準(zhǔn)測試網(wǎng)絡(luò)和2個(gè)大規(guī)模網(wǎng)絡(luò)用基于鄰邊的局部社團(tuán)發(fā)現(xiàn)算法劃分社團(tuán)，并

4、與經(jīng)典的社團(tuán)發(fā)現(xiàn)算法對比。仿真結(jié)果表明，本文算法不僅準(zhǔn)確度高且時(shí)間復(fù)雜度低，大大提高了算法的執(zhí)行效率，適合發(fā)現(xiàn)大規(guī)模復(fù)雜網(wǎng)絡(luò)中的社團(tuán)。
　　在劃分得到的社團(tuán)中，發(fā)現(xiàn)社團(tuán)中的重要節(jié)點(diǎn)。針對常見的重要節(jié)點(diǎn)發(fā)現(xiàn)算法考慮因素片面單一，本文結(jié)合節(jié)點(diǎn)的連接狀態(tài)、節(jié)點(diǎn)在社團(tuán)中的位置、節(jié)點(diǎn)的權(quán)重及其鄰居節(jié)點(diǎn)的影響，提出了社團(tuán)中重要節(jié)點(diǎn)的發(fā)現(xiàn)算法。本文定義了加權(quán)網(wǎng)中的接近度因子、度中心性因子和鄰點(diǎn)影響的附加因素，提出了社團(tuán)中節(jié)點(diǎn)的重要度函數(shù)，利用此