復(fù)雜網(wǎng)絡(luò)上的級聯(lián)失效及其與病毒傳播相互作用的研究.pdf

1、網(wǎng)絡(luò)結(jié)構(gòu)在我們身邊比比皆是。有時，網(wǎng)絡(luò)結(jié)構(gòu)是以實(shí)體形式存在的，如因特網(wǎng)等，有時并不存在實(shí)體的網(wǎng)絡(luò)，但網(wǎng)絡(luò)是用來描述個體之間相互關(guān)系的一種自然的方式，比如人際關(guān)系網(wǎng)等。這兩方面的結(jié)合使網(wǎng)絡(luò)成為復(fù)雜性研究中一種有力的建模工具，并由此形成了一門新的交叉學(xué)科，即復(fù)雜網(wǎng)絡(luò)科學(xué)或者網(wǎng)絡(luò)科學(xué)，其研究涉及數(shù)學(xué)、物理、生物、管理、社會科學(xué)以及信息科學(xué)等多個學(xué)科。
　　本文以通信網(wǎng)絡(luò)為背景，應(yīng)用復(fù)雜網(wǎng)絡(luò)中的相關(guān)理論和方法對網(wǎng)絡(luò)上的級聯(lián)失效與病毒傳播進(jìn)

2、行了若干研究，具體包括下面幾個方面:
　　1.節(jié)點(diǎn)移除對網(wǎng)絡(luò)負(fù)載的影響研究。在復(fù)雜網(wǎng)絡(luò)中，級聯(lián)效失效作為一種廣泛存在于多種不同網(wǎng)絡(luò)上的動態(tài)過程，已經(jīng)被研究了十?dāng)?shù)年，但由于該現(xiàn)象的高度非線性，對它的理論研究難以展開，其與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之間的相互關(guān)系也一直沒有得到系統(tǒng)的研究，目前這仍然是開放且備受關(guān)注的課題。我們并沒有對之進(jìn)行直接探討，而是從另外一個角度展開了努力:我們研究網(wǎng)絡(luò)拓?fù)涞淖兓唧w地，節(jié)點(diǎn)的刪除——對網(wǎng)絡(luò)上的負(fù)載會產(chǎn)生怎樣

3、的影響。我們考慮一個正進(jìn)行數(shù)據(jù)傳輸?shù)耐ㄐ啪W(wǎng)絡(luò)，在網(wǎng)絡(luò)優(yōu)化階段有一些節(jié)點(diǎn)可能被刻意移除，或者在網(wǎng)絡(luò)運(yùn)行階段有一些節(jié)點(diǎn)可能遭受攻擊或者發(fā)生失效，從拓?fù)浣嵌榷?，它們都相?dāng)于從網(wǎng)絡(luò)中被“刪除”了。我們用節(jié)點(diǎn)的介數(shù)來度量其負(fù)載，用所有節(jié)點(diǎn)的介數(shù)之和來度量網(wǎng)絡(luò)的總負(fù)載。我們得到了如下結(jié)論:1）在刪除一個節(jié)點(diǎn)的情況下，剩余網(wǎng)絡(luò)的總負(fù)載在刪除前后的變化量與所刪除節(jié)點(diǎn)的度數(shù)是正相關(guān)的。2）在刪除多個節(jié)點(diǎn)的情況下:若刪除網(wǎng)絡(luò)中度數(shù)/介數(shù)較小的那些節(jié)點(diǎn)，網(wǎng)

4、絡(luò)總負(fù)載減小;而若刪除網(wǎng)絡(luò)中度數(shù)/介數(shù)較大的那些節(jié)點(diǎn)，網(wǎng)絡(luò)總負(fù)載急劇增大。我們展示了這兩種方式下網(wǎng)絡(luò)的負(fù)載變化之懸殊。此外，當(dāng)刪除度數(shù)/介數(shù)小的節(jié)點(diǎn)時，不僅總負(fù)載是減小的，那些往往是網(wǎng)絡(luò)性能瓶頸的hub節(jié)點(diǎn)的負(fù)載也是減小的。這些結(jié)果能夠加深我們對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與其上負(fù)載乃至級聯(lián)失效之間關(guān)系的理解，對通信網(wǎng)絡(luò)拓?fù)鋬?yōu)化等問題的解決也可資借鑒。
　　2.病毒傳播與級聯(lián)失效相互作用的研究。近年來，人們認(rèn)識到，在復(fù)雜系統(tǒng)中，不僅存在個體之間的

5、互作用，還廣泛存在不同子系統(tǒng)之間的相互作用。這使得耦合網(wǎng)絡(luò)稱為近年的研究熱點(diǎn)。該研究又進(jìn)一步啟發(fā)研究者去關(guān)注網(wǎng)絡(luò)上多動態(tài)過程的耦合，比如感染病的傳播和關(guān)于感染病的輿論傳播之間的相互耦合等。網(wǎng)絡(luò)本身的耦合體現(xiàn)的是復(fù)雜系統(tǒng)中子系統(tǒng)之間相互作用關(guān)系的復(fù)雜性，而動態(tài)過程的耦合體現(xiàn)的是復(fù)雜系統(tǒng)上的行為的復(fù)雜性。這種研究剛剛起步。在此背景下，我們率先開展了病毒傳播與級聯(lián)失效的相互作用研究。病毒傳播和級聯(lián)失效是復(fù)雜網(wǎng)絡(luò)中兩個吸引了廣泛關(guān)注的領(lǐng)域。一方

6、面，傳統(tǒng)研究中對它們探討是相互獨(dú)立的;但是另外一方面，在實(shí)際中有許多兩個過程同時存在、且一者發(fā)生時另一者的影響不能忽略的例子。比如在通信網(wǎng)絡(luò)中，當(dāng)有病毒傳播時，會影響數(shù)據(jù)傳輸，導(dǎo)致網(wǎng)絡(luò)中負(fù)載的變化，從而可能引發(fā)級聯(lián)失效。這個現(xiàn)象在實(shí)際中已經(jīng)被觀察到。我們對這個現(xiàn)象進(jìn)行了建模，提出了一個SIR病毒傳播和局域負(fù)載分擔(dān)的級聯(lián)失效相互作用的模型。該模型揭露了許多新的現(xiàn)象:當(dāng)節(jié)點(diǎn)容量非常小的時候，網(wǎng)絡(luò)中容易發(fā)生級聯(lián)失效，網(wǎng)絡(luò)的穩(wěn)健性較差，節(jié)點(diǎn)的容

7、量非常大的時候，病毒傳播容易進(jìn)行，網(wǎng)絡(luò)的性能同樣較差，只有節(jié)點(diǎn)容量落在某一范圍內(nèi)的時候，網(wǎng)絡(luò)中才會存在由未感染且未失效的節(jié)點(diǎn)形成的大規(guī)模連通子集。我們在隨機(jī)以及更一般的度不相關(guān)網(wǎng)絡(luò)中對一些現(xiàn)象進(jìn)行了理論分析，重點(diǎn)對網(wǎng)絡(luò)中存在大規(guī)模連通子集的容量的范圍進(jìn)行了理論推導(dǎo)，以深化對這兩個動態(tài)過程相互作用的理解。這一研究推進(jìn)了對網(wǎng)絡(luò)上多動態(tài)過程耦合的研究，同時在某些應(yīng)用場合下更符合實(shí)際，結(jié)果也更有效。
　　3.計(jì)入節(jié)點(diǎn)負(fù)載與容量時病毒爆發(fā)條

8、件的研究。近年來對網(wǎng)絡(luò)上病毒傳播的研究有一種趨勢，即研究更為接近于實(shí)際、也就更為復(fù)雜的病毒傳播過程。我們受此啟發(fā)，在上一部分的基礎(chǔ)上，進(jìn)一步研究了在計(jì)入節(jié)點(diǎn)的負(fù)載和容量時，病毒傳播會受到什么樣的影響。在通信網(wǎng)絡(luò)中，節(jié)點(diǎn)需要傳輸數(shù)據(jù)且容量有限，研究其上病毒傳播時應(yīng)當(dāng)把這些因素考慮在內(nèi)。傳統(tǒng)病毒傳播研究中的一個重要課題是病毒的爆發(fā)條件。在這一條件不滿足時，病毒會逐漸消逝而無法在網(wǎng)絡(luò)中擴(kuò)散開來。若計(jì)入節(jié)點(diǎn)的負(fù)載與容量，這一條件會發(fā)生變化，因?yàn)?/p>

9、病毒傳播可能引發(fā)節(jié)點(diǎn)過載，甚至大規(guī)模的級聯(lián)失效，這會阻礙病毒的傳播。我們對此時病毒爆發(fā)的條件進(jìn)行了理論分析:首先，我們分析了在病毒未擴(kuò)散開來的情況下，穩(wěn)態(tài)時網(wǎng)絡(luò)中失效節(jié)點(diǎn)和因感染病毒而被移除的節(jié)點(diǎn)的比例;在此基礎(chǔ)上，我們通過動力學(xué)分析，得到了在計(jì)入節(jié)點(diǎn)的負(fù)載和容量的情況下，病毒爆發(fā)的條件，這一條件是由是由描述病毒傳播速率的傳播概率與描述節(jié)點(diǎn)容量大小的冗余系數(shù)共同決定的;最后，我們通過探討表明，當(dāng)病毒傳播速率一定而冗余系數(shù)變化時，病毒恰好