復(fù)雜網(wǎng)絡(luò)調(diào)研報(bào)告范本報(bào)告大綱復(fù)雜網(wǎng)絡(luò)起源復(fù)雜網(wǎng)絡(luò)基本概念復(fù)雜網(wǎng)絡(luò)的幾種模型及其性質(zhì)復(fù)雜網(wǎng)絡(luò)文獻(xiàn)讀后感2復(fù)雜網(wǎng)絡(luò)起源七橋問題七橋問題描述的是東普魯士的一個(gè)城鎮(zhèn)，城中有一條橫貫城區(qū)的河流，河中有兩個(gè)小島，兩岸和兩島之間共架有七座橋，問能否在一次散步中走過所有的七座橋，而且每座橋只經(jīng)過一次，最后返回原地。3隨機(jī)圖理論

20世紀(jì)60年代，由兩位匈牙利數(shù)學(xué)家建立了ER隨機(jī)圖理論，被公認(rèn)為是在數(shù)學(xué)上開創(chuàng)了復(fù)雜網(wǎng)絡(luò)理論的系統(tǒng)性研究。

20世紀(jì)的后40年中，隨機(jī)圖理論一直是研究復(fù)雜網(wǎng)絡(luò)的基本理論。

在ER隨機(jī)圖模型中，任意兩個(gè)節(jié)點(diǎn)之間有一條邊相連接的概率都為p，幾乎每一個(gè)ER隨即圖都具有某種性質(zhì)Q，如果當(dāng)N趨于無窮大時(shí)產(chǎn)生具有這種性質(zhì)Q的ER隨機(jī)圖的概率為1。ER隨機(jī)圖的許多重要的性質(zhì)都是突然涌現(xiàn)的。也就是說，對于任一給定的概率P，要么幾乎每一個(gè)圖都具有某個(gè)性質(zhì)Q，要么幾乎每個(gè)圖都不具有該性質(zhì)。4Milgram的小世界實(shí)驗(yàn)首先，Milgram選定兩個(gè)目標(biāo)對象，然后他在遙遠(yuǎn)的堪薩斯州和內(nèi)布拉斯加州招募到了一批志愿者。Milgram要求這些志愿者通過自己所認(rèn)識(shí)的人，用自己認(rèn)為盡可能少的傳遞次數(shù)，設(shè)法把一封信最終轉(zhuǎn)交到一個(gè)給定的目標(biāo)對象手中。盡管并不是每個(gè)實(shí)驗(yàn)對象都很成功，但是根據(jù)最終到達(dá)目標(biāo)者手中的信件統(tǒng)計(jì)分析，從一個(gè)志愿者到其目標(biāo)對象的平均距離是6。Milgram推斷：地球上任意兩個(gè)人之間的平均距離是6。這就是著名的六度分離推斷。5復(fù)雜網(wǎng)絡(luò)的基本概念平均路徑長度網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)i和j之間的距離定義為連接這兩個(gè)節(jié)點(diǎn)的最短路徑上的邊數(shù)。網(wǎng)絡(luò)的平均路徑長度L定義為任意兩個(gè)節(jié)點(diǎn)之間的距離的平均值，即其中N為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)。網(wǎng)絡(luò)的平均路徑長度也稱為網(wǎng)絡(luò)的特征路徑長度。6聚類系數(shù)

網(wǎng)絡(luò)的聚類特性，簡單的說就是在你的朋友關(guān)系網(wǎng)絡(luò)中，你的兩個(gè)朋友很可能彼此也是朋友，這種屬性稱為網(wǎng)絡(luò)的聚類特性。假設(shè)網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)i有條邊將它和其他節(jié)點(diǎn)相連，這個(gè)節(jié)點(diǎn)就稱為節(jié)點(diǎn)i的鄰居。這個(gè)節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)和總的可能的邊數(shù)之比就定義為節(jié)點(diǎn)i的聚類系數(shù)。

整個(gè)網(wǎng)絡(luò)的聚類系數(shù)C就是所有節(jié)點(diǎn)i的聚類系數(shù)的平均值。

7度和度分布度是單獨(dú)節(jié)點(diǎn)的屬性中簡單但是又很重要的概念。網(wǎng)絡(luò)中所有節(jié)點(diǎn)i的度的平均值稱為網(wǎng)絡(luò)的平均度，記為<k>。近幾年的研究表明，許多實(shí)際網(wǎng)絡(luò)的度分布明顯不同于泊松分布。許多網(wǎng)絡(luò)的度分布可以用冪律形式來更好地描述。冪律分布也成為無標(biāo)度分布，具有冪律度分布的網(wǎng)絡(luò)也稱為無標(biāo)度網(wǎng)絡(luò)。在一個(gè)度分布為具有適當(dāng)冪指數(shù)（通常為2≤γ≤3）的冪律形式的大規(guī)模無標(biāo)度網(wǎng)絡(luò)中，絕大部分的節(jié)點(diǎn)的度相對很低，但存在少量的度相對很高的節(jié)點(diǎn)，而這類網(wǎng)絡(luò)業(yè)稱為非均勻網(wǎng)絡(luò)，那些度相對很高的節(jié)點(diǎn)稱為網(wǎng)絡(luò)的“集線器”hub。例如高速公路網(wǎng)就可以近似看作是一個(gè)均勻網(wǎng)絡(luò)，因?yàn)椴豢赡苡猩习贄l高速公路都經(jīng)過同一個(gè)城市；而航空網(wǎng)則可以看作是一個(gè)無標(biāo)度網(wǎng)絡(luò)，大部分機(jī)場都是小機(jī)場，但存在少量連接眾多小機(jī)場的非常大的機(jī)場。8復(fù)雜網(wǎng)絡(luò)的幾種模型及其性質(zhì)WS小世界模型作為從完全規(guī)則網(wǎng)絡(luò)向完全隨機(jī)網(wǎng)絡(luò)的過渡，Watts和Strogtz于1998年引入了一個(gè)有趣的小世界網(wǎng)絡(luò)模型，稱為WS小世界模型。其構(gòu)造算法如下：①從規(guī)則圖開始：考慮一個(gè)含有N個(gè)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)，它們圍成一個(gè)環(huán)，其中每個(gè)節(jié)點(diǎn)都與它左右相鄰的各K/2節(jié)點(diǎn)相連，K是偶數(shù)。②隨機(jī)化重連：以概率P隨機(jī)地重新連接網(wǎng)絡(luò)中的每個(gè)邊，即將邊的一個(gè)端點(diǎn)保持不變，而另一個(gè)端點(diǎn)取為網(wǎng)絡(luò)中隨機(jī)選擇的一個(gè)節(jié)點(diǎn)。其中規(guī)定，任意兩個(gè)不同的節(jié)點(diǎn)之間至多只能有一條邊，并且每一個(gè)節(jié)點(diǎn)都不能有邊與自身相連。9WS小世界網(wǎng)絡(luò)不呈現(xiàn)冪律特性，但是平均路徑小，具有高聚類特性。10WS小世界網(wǎng)絡(luò)模型統(tǒng)計(jì)性質(zhì)聚類系數(shù)：平均路徑長度：迄今為止，人們還沒有關(guān)于WS小世界模型的平均路徑長度L的精確解析表達(dá)式，不過利用重正化群方法可以得到如下公式：

其中為一普適標(biāo)度函數(shù)，滿足：11BA無標(biāo)度網(wǎng)絡(luò)模型

BA無標(biāo)度網(wǎng)絡(luò)模型基于網(wǎng)絡(luò)的增長和優(yōu)先連接特性，增長特性是只網(wǎng)絡(luò)的規(guī)模的不斷擴(kuò)大化，優(yōu)先連接特性是指新的節(jié)點(diǎn)更傾向于與那些具有較高連接度的“大”的節(jié)點(diǎn)相連接。其構(gòu)造算法如下：增長：從一個(gè)具有個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)開始，每次引入一個(gè)新的節(jié)點(diǎn)，并且連到m個(gè)已存在的節(jié)點(diǎn)上，這里m≤。優(yōu)先連接：一個(gè)新節(jié)點(diǎn)與一個(gè)已經(jīng)存在的節(jié)點(diǎn)i相連的概率與節(jié)點(diǎn)i的度、節(jié)點(diǎn)j的度之間滿足如下關(guān)系：

經(jīng)過t步后，這種算法產(chǎn)生一個(gè)有N=t+個(gè)節(jié)點(diǎn)、mt條邊的網(wǎng)絡(luò)。12BA無標(biāo)度網(wǎng)絡(luò)模型統(tǒng)計(jì)性質(zhì)聚類系數(shù)：這表明與ER隨機(jī)圖類似，當(dāng)網(wǎng)絡(luò)規(guī)模充分大時(shí)BA無標(biāo)度網(wǎng)絡(luò)部具有明顯的聚類特性。平均路徑長度：

L∝

這表明該網(wǎng)絡(luò)業(yè)具有小世界特性。13復(fù)雜網(wǎng)絡(luò)文獻(xiàn)讀后感《復(fù)雜網(wǎng)絡(luò)理論在互聯(lián)網(wǎng)病毒傳播研究中的應(yīng)用》《復(fù)雜網(wǎng)絡(luò)的可靠性研究》

14《復(fù)雜網(wǎng)絡(luò)理論在互聯(lián)網(wǎng)病毒傳播研究中的應(yīng)用》這篇文章綜述了近幾年復(fù)雜網(wǎng)絡(luò)理論在互聯(lián)網(wǎng)病毒傳播研究中的應(yīng)用。首先介紹了互聯(lián)網(wǎng)的結(jié)構(gòu)特征,然后從臨界值的角度介紹了計(jì)算機(jī)病毒在不同拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)中的傳播性質(zhì)，討論了相應(yīng)的免疫機(jī)制,并對電子郵件病毒的傳播行為進(jìn)行了系統(tǒng)分析。研究表明,互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對計(jì)算機(jī)病毒的傳播行為有著重要的影響，在不同的拓?fù)浣Y(jié)構(gòu)下，傳播行為會(huì)呈現(xiàn)不同的特性。復(fù)雜網(wǎng)絡(luò)理論為互聯(lián)網(wǎng)上計(jì)算機(jī)病毒傳播的研究提供了新的思路和方法。15無標(biāo)度網(wǎng)絡(luò)很容易受到病毒攻擊而導(dǎo)致病毒的流行，因此選擇合適的免疫策略顯得更加重要。無標(biāo)度網(wǎng)絡(luò)有三種免疫策略：①隨機(jī)免疫，也稱均勻免疫，它是完全隨機(jī)地選取網(wǎng)絡(luò)中的一部分節(jié)點(diǎn)進(jìn)行免疫，它對度大的節(jié)點(diǎn)和度小的節(jié)點(diǎn)是平等對待的。無標(biāo)度網(wǎng)絡(luò)中隨著<>→∞時(shí)，免疫臨界值趨于1，如果對無標(biāo)度網(wǎng)絡(luò)采取隨機(jī)免疫策略，需要對網(wǎng)絡(luò)中幾乎所有節(jié)點(diǎn)都實(shí)施免疫才能保證最終消滅病毒傳染。②目標(biāo)免疫，根據(jù)無標(biāo)度網(wǎng)絡(luò)的不均勻特性，可以進(jìn)行有選擇的目標(biāo)免疫，即選取少量度最大的節(jié)點(diǎn)進(jìn)行免疫，一旦這些節(jié)點(diǎn)被免疫后，就意味著他們所連的邊可以從網(wǎng)絡(luò)中除去，使得病毒傳播的可能的連接途徑大大減少。③熟人免疫，該策略的基本思想是，從N個(gè)節(jié)點(diǎn)中隨機(jī)選出比例為p的節(jié)點(diǎn)，再從每一個(gè)被選出的節(jié)點(diǎn)中隨機(jī)選擇一個(gè)鄰居節(jié)點(diǎn)進(jìn)行免疫。這種策略只需要知道被隨機(jī)選擇出來的節(jié)點(diǎn)以及他們直接相連的鄰居節(jié)點(diǎn)，從而巧妙地回避了目標(biāo)免疫中需要知道全局信息的問題。16不同的病毒復(fù)制和傳播策略有可能導(dǎo)致不同的網(wǎng)絡(luò)拓?fù)?，因此需要有一種不受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化影響，并且不需在病毒爆發(fā)之前知道傳染機(jī)制的控制策略。扼流就是這樣一種策略，它通過限制給定時(shí)間段內(nèi)一臺(tái)計(jì)算機(jī)與其他計(jì)算機(jī)之間的心連接的數(shù)目而限制病毒傳播速率。

當(dāng)計(jì)算機(jī)病毒產(chǎn)生的網(wǎng)絡(luò)流量比正常通信流量大得多時(shí)，扼流法很適用。扼流法是一種控制策略，它通過限制給定時(shí)間段內(nèi)一臺(tái)計(jì)算機(jī)與其他計(jì)算機(jī)之間的新連接的數(shù)目而限制病毒傳播速率。它能夠在不影響計(jì)算機(jī)正常工作的情況下大幅度降低病毒傳播速率，從而贏得更多的時(shí)間來打補(bǔ)丁或用其他的方法對付該病毒。17《復(fù)雜網(wǎng)絡(luò)的可靠性研究》復(fù)雜網(wǎng)絡(luò)可靠性的研究對于理解網(wǎng)絡(luò)的結(jié)構(gòu)和行為至關(guān)重要。真實(shí)復(fù)雜網(wǎng)絡(luò)的拓?fù)涮匦院涂煽啃跃o密相關(guān)，對于不同的網(wǎng)絡(luò)，其可靠性存在很大差異。已有研究表明不同的網(wǎng)絡(luò)拓?fù)溆兄煌娜蒎e(cuò)性和抗攻擊性。特別是，當(dāng)遇到節(jié)點(diǎn)的隨機(jī)移除時(shí)，無尺度網(wǎng)絡(luò)要比隨機(jī)網(wǎng)絡(luò)健壯的多，而當(dāng)惡意攻擊時(shí)，前者比較脆弱。然而由于對復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)知之甚少，甚至有很大偏差，因此對復(fù)雜網(wǎng)絡(luò)的可靠性研究一直是個(gè)很棘手的問題。18目前復(fù)雜網(wǎng)絡(luò)的可靠性研究大都集中于研究攻擊模式對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響以及一些相繼故障模型，而度與介數(shù)在一定程度上都可以反映出節(jié)點(diǎn)重要性，因此基于度與介數(shù)的攻擊得到了廣泛的研究。然而，這些都是基于幾何量變化來研究網(wǎng)絡(luò)在受到攻擊后的結(jié)構(gòu)動(dòng)態(tài)行為，一直以來都沒有一個(gè)確定的宏觀的指標(biāo)來衡量復(fù)雜系統(tǒng)可靠性。這也正是這篇文章的研究目標(biāo)。19

首先，為了宏觀的研究復(fù)雜網(wǎng)絡(luò)拓?fù)涞目煽啃?，針對?fù)雜網(wǎng)絡(luò)的特點(diǎn)，這篇引入了可靠性指標(biāo)一網(wǎng)絡(luò)連通可靠度來衡量網(wǎng)絡(luò)的可靠性，為增強(qiáng)網(wǎng)絡(luò)的安全性提供堅(jiān)實(shí)的理論基礎(chǔ)。其次，它給出了可靠性度量網(wǎng)絡(luò)連通可靠度的相關(guān)算法。通過對不同網(wǎng)絡(luò)模型受到攻擊后的可靠性指標(biāo)變化及分布進(jìn)行模擬分析，結(jié)果發(fā)現(xiàn):1、隨著網(wǎng)絡(luò)規(guī)模的增大，可靠度呈線性增長趨勢；2、在對網(wǎng)絡(luò)進(jìn)行隨機(jī)攻擊時(shí)，網(wǎng)絡(luò)連通可靠度大小排序?yàn)椋築A>E>R規(guī)則、WS，而在惡意攻擊時(shí)，ER>規(guī)則、WS>BA。理論和實(shí)踐都證明，網(wǎng)絡(luò)連通可靠度不僅僅刻畫了復(fù)雜網(wǎng)絡(luò)的可靠性，而且將復(fù)雜網(wǎng)絡(luò)可靠性用確切的量來表示，這為復(fù)雜網(wǎng)絡(luò)的保護(hù)提供了一定的理論基礎(chǔ)。另外，在文章的最后，給出了一個(gè)衡量網(wǎng)絡(luò)脆弱性的靜態(tài)參數(shù)韌性度，和研究的網(wǎng)絡(luò)連通可靠度兩個(gè)參數(shù)互為結(jié)合，可以很好的衡量網(wǎng)絡(luò)的可靠性及脆弱性。20復(fù)雜網(wǎng)絡(luò)可靠性研究中有兩個(gè)最核心的問題，一是如何計(jì)算保持連通的概率，即可靠性的計(jì)算問題，另一個(gè)是可靠性優(yōu)化問題。網(wǎng)絡(luò)連通概率的計(jì)算是NP難問題，目前只應(yīng)用于為數(shù)不多節(jié)點(diǎn)數(shù)很少的一些特殊網(wǎng)絡(luò)，這嚴(yán)重影響了相關(guān)成果的應(yīng)用。彌補(bǔ)這一缺陷的主要途徑有二：一是利用近似分析的方法給出系統(tǒng)可靠性的上界與下界；二是利用概率統(tǒng)計(jì)技術(shù)對系統(tǒng)的可靠性作出估計(jì)。21復(fù)雜網(wǎng)絡(luò)可靠性研究的目的，是為了保護(hù)網(wǎng)絡(luò)。我認(rèn)為復(fù)雜網(wǎng)絡(luò)的保護(hù)應(yīng)從以下幾個(gè)方面來考慮：抵抗惡意攻擊的能力，抵抗擁塞的能力及抵抗相繼故障的能力。Scale-free網(wǎng)絡(luò)由于其結(jié)構(gòu)上的特征，使其具有魯棒性和脆弱性，因而對這種結(jié)構(gòu)進(jìn)行自然防范的有效措施是有目的的接種疫苗，給網(wǎng)絡(luò)中的關(guān)鍵結(jié)點(diǎn)賦予免疫性。又由于無尺度網(wǎng)絡(luò)對隨機(jī)故