復(fù)雜網(wǎng)絡(luò)中關(guān)鍵節(jié)點的查找方法研究.pdf

1、復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點對整個網(wǎng)絡(luò)的結(jié)構(gòu)具有重要作用。對于真實網(wǎng)絡(luò)而言，能夠有效地定位到關(guān)鍵節(jié)點對網(wǎng)絡(luò)的維護(hù)與網(wǎng)絡(luò)性質(zhì)的研究等方面都具有重要意義。本文從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)出發(fā)，并結(jié)合PPI(Protein-Protein Interaction)網(wǎng)絡(luò)的生物信息特征，給出兩個關(guān)鍵節(jié)點查找算法。
　　直徑在各種類型的網(wǎng)絡(luò)中都是極其重要的拓?fù)浣Y(jié)構(gòu)參數(shù)。然而，直徑很少被用于關(guān)鍵節(jié)點的查找。本文定義直徑所在路徑的中點為整個網(wǎng)絡(luò)的中點，并給出搜索中點的

2、DCD算法。該算法被用在小世界網(wǎng)絡(luò)、無標(biāo)度網(wǎng)絡(luò)、星形長尾網(wǎng)絡(luò)和五個真實網(wǎng)絡(luò)中，實驗結(jié)果表明，通過DCD算法搜索到的中點在網(wǎng)絡(luò)中心性指標(biāo)如介數(shù)中心性(BC)、接近中心性(CC)、度中心性(DC)、k-核分解上比整個網(wǎng)絡(luò)的平均情況具有優(yōu)勢。此外，刪除中點后，網(wǎng)絡(luò)結(jié)構(gòu)如直徑和最大連通分支都發(fā)生很大變化。本文還基于DCD算法提出了有效的刪邊策略，該策略能夠?qū)崿F(xiàn)只刪除少量邊而使網(wǎng)絡(luò)節(jié)點對在很大程度上不連通。DCD算法不需要找到所有可能的直徑所在路

3、徑，而是基于廣度優(yōu)先和Bellman準(zhǔn)則，因此其時間復(fù)雜度對于稀疏網(wǎng)絡(luò)而言要優(yōu)于Floyd算法。
　　對于PPI網(wǎng)絡(luò)而言，結(jié)合生物信息的關(guān)節(jié)蛋白質(zhì)搜索方法被證明比單純從拓?fù)浣Y(jié)構(gòu)出發(fā)的方法準(zhǔn)確率更高。然而，現(xiàn)有的大多數(shù)搜索方法只包含一類生物學(xué)信息。PPI網(wǎng)絡(luò)固有的由假陽性及假陰性交互關(guān)系引起的噪音也對重要蛋白質(zhì)預(yù)測的準(zhǔn)確性有很大影響。本文對此提出了一個有效的重要蛋白質(zhì)搜索方法IDSSP，該方法首先結(jié)合STRING數(shù)據(jù)庫的多種生物學(xué)信