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

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

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

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

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