復(fù)雜網(wǎng)絡(luò)上的若干動力學(xué)問題研究.pdf

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

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

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

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

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

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

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

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