復雜網絡中關鍵節(jié)點的查找方法研究.pdf

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

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

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