復雜網(wǎng)絡上的若干動力學問題研究.pdf

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

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

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

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

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

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

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

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