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

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

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

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

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

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

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

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

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