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

20世紀60年代，由兩位匈牙利數學家建立了ER隨機圖理論，被公認為是在數學上開創了復雜網絡理論的系統性研究。

20世紀的后40年中，隨機圖理論一直是研究復雜網絡的基本理論。

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

網絡的聚類特性，簡單的說就是在你的朋友關系網絡中，你的兩個朋友很可能彼此也是朋友，這種屬性稱為網絡的聚類特性。假設網絡中的一個節點i有條邊將它和其他節點相連，這個節點就稱為節點i的鄰居。這個節點之間實際存在的邊數和總的可能的邊數之比就定義為節點i的聚類系數。

整個網絡的聚類系數C就是所有節點i的聚類系數的平均值。

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

其中為一普適標度函數，滿足：11BA無標度網絡模型

BA無標度網絡模型基于網絡的增長和優先連接特性，增長特性是只網絡的規模的不斷擴大化，優先連接特性是指新的節點更傾向于與那些具有較高連接度的“大”的節點相連接。其構造算法如下：增長：從一個具有個節點的網絡開始，每次引入一個新的節點，并且連到m個已存在的節點上，這里m≤。優先連接：一個新節點與一個已經存在的節點i相連的概率與節點i的度、節點j的度之間滿足如下關系：

經過t步后，這種算法產生一個有N=t+個節點、mt條邊的網絡。12BA無標度網絡模型統計性質聚類系數：這表明與ER隨機圖類似，當網絡規模充分大時BA無標度網絡部具有明顯的聚類特性。平均路徑長度：

L∝

這表明該網絡業具有小世界特性。13復雜網絡文獻讀后感《復雜網絡理論在互聯網病毒傳播研究中的應用》《復雜網絡的可靠性研究》

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

當計算機病毒產生的網絡流量比正常通信流量大得多時，扼流法很適用。扼流法是一種控制策略，它通過限制給定時間段內一臺計算機與其他計算機之間的新連接的數目而限制病毒傳播速率。它能夠在不影響計算機正常工作的情況下大幅度降低病毒傳播速率，從而贏得更多的時間來打補丁或用其他的方法對付該病毒。17《復雜網絡的可靠性研究》復雜網絡可靠性的研究對于理解網絡的結構和行為至關重要。真實復雜網絡的拓撲特性和可靠性緊密相關，對于不同的網絡，其可靠性存在很大差異。已有研究表明不同的網絡拓撲有著不同的容錯性和抗攻擊性。特別是，當遇到節點的隨機移除時，無尺度網絡要比隨機網絡健壯的多，而當惡意攻擊時，前者比較脆弱。然而由于對復雜網絡的拓撲結構知之甚少，甚至有很大偏差，因此對復雜網絡的可靠性研究一直是個很棘手的問題。18目前復雜網絡的可靠性研究大都集中于研究攻擊模式對網絡拓撲結構的影響以及一些相繼故障模型，而度與介數在一定程度上都可以反映出節點重要性，因此基于度與介數的攻擊得到了廣泛的研究。然而，這些都是基于幾何量變化來研究網絡在受到攻擊后的結構動態行為，一直以來都沒有一個確定的宏觀的指標來衡量復雜系統可靠性。這也正是這篇文章的研究目標。19

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