復雜網(wǎng)絡中節(jié)點重要度評估算法的研究.pdf

1、近年來，復雜網(wǎng)絡系統(tǒng)已經(jīng)融入到人們生產(chǎn)生活的方方面面。作為一個新興且活躍的科學研究領域，復雜網(wǎng)絡早已引入到在現(xiàn)實世界網(wǎng)絡的實證研究。目前，在計算機科學、社會科學、生物科學、管理科學等眾多領域得到了越來越多的人的重視。一方面，伴隨著復雜網(wǎng)絡的不斷發(fā)展，人類的生產(chǎn)生活質(zhì)量有了大幅度的提高和升華，并且為之帶來了極大的便利。但是另一方面，復雜網(wǎng)絡系統(tǒng)的運行也對人類的生產(chǎn)生活帶來了一定的負面沖擊，比如疾病的快速傳播、大面積的停電事故、以及交通運輸

2、的癱瘓等等。因此，我們需要對各種復雜網(wǎng)絡系統(tǒng)有著更為深刻的認識和分析，以便對可能造成的負面影響進行預測、避免、控制等等。在眾多復雜網(wǎng)絡研究方向中，節(jié)點重要度評估已經(jīng)成為其研究發(fā)展中一個較為深遠的方向。
　　雖然目前已經(jīng)許多的中心性方法被提出來度量節(jié)點的重要度，但不同的中心性在各個方面或多或少都存在著一定的不足和局限性。由于不同的中心性的機制不同，而且有著不同的不足，因此，當對同一個網(wǎng)絡使用不同的中心性進行節(jié)點重要度評估時，往往會得

3、到不同的結(jié)果。為此，我們有必要對現(xiàn)有的中心性進行改進，從而能全面有效的對復雜網(wǎng)絡節(jié)點重要度進行評估。
　　本文主要提出了三種不同的中心性算法對節(jié)點進行重要度評估。首先將有效距離引入節(jié)點最短路徑的應用中，用其代替?zhèn)鹘y(tǒng)的測地線和地理距離來衡量網(wǎng)絡節(jié)點的距離，并利用改進后接近中心性對節(jié)點進行重要度評估。然后提出了一種基于TOPSIS算法的多屬性決策模型的中心性算法，該算法將多個中心性作為多屬性進行融合來評估節(jié)點重要度。最后，我們基于失效

4、模式及影響分析模型，將復雜網(wǎng)絡的節(jié)點信息進行建模來刻畫發(fā)生頻度、嚴重程度、檢測難易程度，并通過風險順序數(shù)來對節(jié)點進行重要度評估。為了體現(xiàn)出本文提出的算法的有效性和實用性，我們都將這些算法應用到真實的網(wǎng)絡中進行對比實驗。
　　本文的工作主要包括以下幾個方面:
　　(1)提出基于有效距離的接近中心性算法
　　在真實的網(wǎng)絡中，往往會有孤立節(jié)點和單向邊，這會導致部分節(jié)點對的距離是無窮大，在此情況下則利用傳統(tǒng)接近中心性來評估節(jié)點

5、重要度是無效的。針對此問題，我們引入有效距離，來代替?zhèn)鹘y(tǒng)的測地線和地理距離來度量網(wǎng)絡節(jié)點的距離。該模型不但解決了傳統(tǒng)接近中心性失效的問題，還能廣泛應用于加權網(wǎng)絡中，而且更加合理的表示了網(wǎng)絡節(jié)點信息流的傳輸過程。
　　(2)提出基于TOPSIS模型的中心性算法
　　TOPSIS算法是一種被廣泛應用的多屬性決策算法，它能有效地融合多個有差異的屬性，并得出一組接近理想最優(yōu)解的排序。由于各種中心性算法都存在著種種缺點，并且不同中心性

6、會產(chǎn)生不同的評估結(jié)果，因此我們認為有必要提出一種折衷的算法來融合這些差異以及克服單一中心性所存在的缺點。我們將度中心性、接近中心性和介數(shù)中心性這三個最為基礎的中心性作為多個屬性引入到TOPSIS多屬性決策模型中，將融合后的中心性作為網(wǎng)絡節(jié)點的重要度評估算法。該算法不僅解決了這三個中心性各自存在的缺陷，還有效地將它們的差異進行折衷融合。并且首次將工程評估中的TOPSIS算法引入到復雜網(wǎng)絡系統(tǒng)中，對跨學科領域研究有著積極的影響。
　　

7、(3)提出基于失效模式及影響分析模型的中心性算法
　　失效模式及影響分析是一種可靠性設計的重要方法，它通過由發(fā)生頻度、嚴重程度、檢測難易程度得出的風險順序數(shù)來對模式進行評估。我們利用網(wǎng)絡的結(jié)構和節(jié)點的信息進行建模來刻畫發(fā)生頻度、嚴重程度、檢測難易程度。我們認為如果一個節(jié)點的入度越大，則表明其他節(jié)點發(fā)生故障時影響到該節(jié)點的機會就越大，那么這個節(jié)點發(fā)生“失效”的概率就越高。同時，倘若一個節(jié)點到其他所有節(jié)點的有效距離越短，則表明該節(jié)點失