復雜網絡上的若干動力學問題研究.pdf

1、網絡科學作為研究復雜系統(tǒng)與復雜性科學的一門新興學科,受到了國內外科研工作者的廣泛關注。自然界和人類社會中的許多復雜系統(tǒng)都可以提煉出由相互作用的個體組成的復雜網絡。當前研究較多的網絡實例包括生物網絡、社會網絡、交通網絡、文獻引用網絡等等。對復雜網絡結構以及動力學特性的研究,有助于理解自然界和社會生活中涌現出來的各種現象,有助于預測復雜系統(tǒng)發(fā)展的趨勢,從而能夠在一定程度上指導人類的生產實踐活動。本文從網絡拓撲結構如何影響網絡上的動力學過程這

2、一問題出發(fā),利用統(tǒng)計物理分析方法并結合數值模擬,對復雜網絡上的隨機行走、粒子搜索、信息傳輸以及網絡控制等方向進行了深入研究。具體研究內容和主要貢獻如下:
　　 研究了復雜網絡結構的統(tǒng)計特征、度量和拓撲建模問題。首先,介紹了常見的網絡分類,包括簡單網絡、有向網絡、加權網絡等網絡類型。其次,分析了最基礎的復雜網絡拓撲特征及其度量,包括度分布、特征路徑長度、節(jié)點介數、聚類系數、節(jié)點匹配等等。最后,給出了幾種典型的復雜網絡演化模型,包括

3、規(guī)則網絡模型、小世界網絡模型、無標度網絡模型、配置模型、加權網絡模型等等。這些復雜網絡基本理論為本文研究的內容提供了知識鋪墊。
　　 研究了復雜網絡上布朗粒子挖掘路徑問題。首先,基于單粒子隨機行走理論,利用概率論基本原理和生成函數方法,推導出多粒子隨機行走條件下挖掘到網絡未知路徑的概率、首次挖掘概率以及平均首次挖掘時間。其次,分析了挖掘時間、路徑長度、路徑結構、網絡拓撲結構等因素對路徑探索問題的影響。結果表明,網絡任意兩點之間的

4、所有路徑中,具有最小節(jié)點度連乘積的路徑的挖掘代價最低。這類路徑被稱之為隨機行走意義下的最佳路徑。最后,將該最佳路徑應用于大規(guī)模網絡上的信息傳輸,結果顯示網絡節(jié)點負載與節(jié)點處理能力實現了最佳匹配。
　　 研究了復雜網絡上的混合搜索模型。首先,基于多粒子隨機行走理論提出了一種應用于復雜網絡的單、多粒子混合搜索模型。該模型克服了單粒子搜索效率低的缺點,同時降低了多粒子搜索的硬件代價。尤其是將該模型與度大優(yōu)先的目標選擇策略相結合時,能進

5、一步提高復雜網絡搜索效率。其次,基于多起始點隨機行走理論提出了一種泛洪與多粒子相結合的混合搜索模型。該模型充分利用了無標度網絡的異質性,大幅提高了網絡搜索效率。最后,針對混合搜索模型給網絡帶來的負載開銷提出了一種負載吸收模型。該模型通過在網絡中若干核心節(jié)點上設置吸收機制有效減輕了混合搜索模型產生的網絡負載。
　　 研究了復雜網絡上的信息傳輸模型。首先,研究了節(jié)點隊列資源有限條件下無標度網絡上的信息流動力學過程,發(fā)現了網絡由自由流

6、通到擁塞的相變現象。提出了一種基于節(jié)點度的隊列資源分配模型。該模型的核心思想是設置節(jié)點的隊列資源數量與節(jié)點度的冪成正比關系,并通過實驗比較得到最佳的隊列資源分配方式。結果顯示當隊列資源分布與節(jié)點信息負載分布相同時網絡的容量最大。其次,提出了一種適用于大規(guī)模網絡的混合路由模型。該模型通過在網絡中嵌入若干能計算有效路由的智能節(jié)點,不但提高了網絡信息傳輸的效率,而且大幅提升了網絡的整體容量,有效緩解了網絡的擁塞。再次,對有效路由策略進行改進并

7、給出了一種機動路由策略。該策略在路由代價函數中對節(jié)點度取對數,使得網絡路徑的路由權重具有可比性,從而提高了網絡核心節(jié)點的利用率并且優(yōu)化了網絡信息負載分布。最后,提出了一種應用于含權無標度網絡的全局路由模型。該模型利用網絡路徑上的節(jié)點強度信息來構建全局路由代價函數,并選擇使該代價函數最小的路徑來傳輸信息,有效避開了網絡中易發(fā)生擁塞的核心節(jié)點。與最短路徑算法相比,該算法以較小的平均路徑長度的增加為代價將網絡容量提高了十多倍。
　　

8、研究了復雜網絡控制的魯棒性問題。首先,分別分析了復雜網絡魯棒性以及復雜網絡控制方面的研究。其次,針對復雜網絡結構的控制能力,在多種復雜網絡拓撲結構上進行各種不同的攻擊實驗。結果表明度大優(yōu)先攻擊比隨機攻擊的效率更高。相繼故障對復雜網絡控制能力的影響與網絡的容差參數密切相關。容差參數越大網絡魯棒性越強。此外節(jié)點平均度越大、拓撲結構越均勻的網絡對相繼故障的魯棒性也越強。最后,研究了美國西部電力網絡結構控制能力的魯棒性。當網絡容差參數很小時,相