復雜網絡理論研究狀況綜述

摘要:文章首先簡要介紹了復雜網絡理論;然后重點論述了小世界網絡模型的研究背景、基礎概念及模型的統計特性;最后對于小世界網絡在各個領域的研究進行了簡單的概述。

關鍵詞:復雜網絡;小世界網絡;無標度網絡

一、 復雜網絡概述

1. 復雜網絡演化過程。用網絡的觀點描述客觀世界起源于1736年德國數學家歐拉Eular使用圖論解決哥尼斯堡七橋問題。數學家和物理學家在考慮網絡的時候，往往只關心節點之間有沒有邊相連，至于節點到底在什么位置，邊是長還是短，是彎曲還是平直，有沒有相交等等都是他們不在意的?？茖W家們認為真實系統各因素之間的關系可以用一些規則的結構表示，例如二維平面上的歐幾里德格網，它看起來像是格子體恤衫上的花紋;又如最近鄰環網，它總是會讓你想到一群手牽著手、圍著篝火跳圓圈舞的姑娘。也就是說網絡中任意兩個節點之間的聯系遵循既定的規則。用得最多的規則網絡是由N個節點組成的環狀網絡，網絡中每個節點只與它最近的K個節點連接。規則網絡的特點就是:每個節點的近鄰數目都相同。但是對于大規模網絡而言由于其復雜性并不能完全用規則網絡來表示。

到了20世紀50年代末，Erdos Renyi想出了一種新的構造網絡的方法，在這種方法下，兩個節點之間連邊與否不再是確定的事情，而是根據一個概率決定。這是一種完全隨機的網絡模型，數學家把這樣生成的網絡叫做隨機網絡。隨機網絡ER模型的描述如下:給定網絡節點總數N，網絡中任意兩個節點以概率P連接，生成的網絡全體記為G(N，P)，構成一個概率空間。由于網絡中連線數目是一個隨機變量X，取值可以從0到N(N-1)/2。隨機網絡在接下來的40年里一直被很多科學家認為是描述真實系統最適宜的網絡。

規則網絡和隨機網絡是兩種極端的情況，隨著信息技術的飛速發展，科學家們發現對于大量真實的網絡系統而言，他們既不是規則網絡，也不是隨機網絡，而是介于兩者之間，具有與前兩者皆不同的統計特征的一種復雜網絡。1998年，Watts Strogatz提出了W-S網絡模型，通過以概率p切斷規則網絡中原始的邊并隨機選擇新的端點重新連接，構造出一種介于規則網絡和隨機網絡之間的網絡——小世界網絡(Small-world Networks)。顯然，當p=0時，相當于各邊未動，還是規則網絡;當p=1時就成了隨機網絡。1999年，Barabasi Albert在Science上發表文章指出，許多實際的復雜網絡的連接度分布具有冪律函數形式，由于冪律分布沒有明顯的可度量特征，該類網絡又被稱為無標度網絡。

2. 復雜網絡的統計性質。復雜網絡的不同的統計性質決定了不同的網絡內部結構，而結構又決定了系統的功能。所以，我們先了解一下復雜網絡的相關統計性質。

(1)度及度分布。在網絡中，節點的度是與目標節點相連的邊的條數。即與該節點相鄰的節點的數目，朋友的個數。而網絡的度指網絡中所有節點度的平均值。

度分布P(k)指網絡中一個任意選擇的節點，它的度恰好為k的概率。即，不同度數的節點個數占節點總數的比率。

在上面介紹的幾種網絡中，對于隨機網絡，當N非常大時，隨機網絡的節點的度分布近似服從Poisson分布，表達式如下:

(2)平均路徑長度L。在網絡中，兩點之間的距離為連接兩點的最短路徑上所包含的邊的數目。網絡的平均路徑長度指網絡中所有節點對的平均距離，它表明網絡中節點間的分離程度，即網絡有多小，反映了網絡的全局特性。不同的網絡結構可賦予L不同的含義。如在疾病傳播模型中L可定義為疾病傳播時間，交通網絡模型中L為站點之間的距離，科學家合作網絡中L為交流頻率。

隨機網絡的平均路徑長度滿足如下表達式:

(3)聚集系數C。在網絡中，節點的聚集系數是指與該節點相鄰的所有節點之間連邊的數目占這些相鄰節點之間最大可能連邊數目的比例。而網絡的聚集系數則是指網絡中所有節點聚集系數的平均值，它表明網絡中節點的聚集情況即網絡的聚集性，也就是說同一個節點的兩個相鄰節點仍然是相鄰節點的概率有多大，它反映了網絡的局部特性。如在疾病傳播模型中C可定義為人與人之間的接觸密度，交通網絡模型中L可定義為站點之間的聚集度，科學家合作網絡中L定義為交流集中度等。

隨機網絡的聚集系數滿足如下表達式:

二、 小世界網絡概述

1. 小世界網絡理論。

(1)小世界問題的提出。小世界理論最早提出來源于1967年，哈佛大學社會心理學家斯坦利·米爾格拉姆(Stanley Milgram)作了這樣的一個實驗，他要求300多人把他的一封信寄到某市一個“目標”人。于是形成了發信人的鏈條，鏈上的每個成員都力圖把這封信寄給他們的朋友、家庭成員、商業同事或偶然認識的人，以便盡快到達目標人。實驗結果是，一共60個鏈條最終到達目標人，鏈條中平均步驟大約為6。人們把這個結果說成“六度分離”并廣為傳播?，F代版本則是，2002年Watts和哥倫比亞大學社會學系合作用E-mail進行了同樣實驗。而且實驗規模也擴展到了全球范圍。166個國家6萬人，發email給18個目標人。有科學家甚至從這個現象推演出一個可以評估的數學模型。你也許不認識奧巴馬，但是在優化的情況下，你只需要通過六個人就可以結識他。“六度分隔”說明了社會中普遍存在一些“弱鏈接”關系，但是卻發揮著非常強大的作用。

這個玄妙理論表明“世界真小啊!”，“小世界”由此得名。它引來了數學家、物理學家和電腦科學家紛紛投入研究，結果發現，世界上許多其他的網絡也有極相似的結構。比如，人際網絡和WWW的架構幾乎完全一樣，通過超文本鏈接的網絡、經濟活動中的商業聯系網絡、甚至人類腦神經元、以及細胞內的分子交互作用網絡，有著完全相同的組織結構?？茖W家們把這種現象稱為小世界效應。

(2)小世界原理及網絡模型。小世界效應的精確定義還在討論中，目前有一個較為合理的解釋是:若網絡中任意兩者間的平均距離L隨網絡節點數N的增加呈對數增長，即L～lnN，當網絡中結點數增加很快時，L變化相對緩慢，則稱該網絡具有小世界效應。

1998年Watts Strogatz 提出了“小世界”網絡模型(W-S模型)，小世界網絡既具有與規則網絡類似的分簇特性，又具有與隨機網絡類似的較小的平均路徑長度，刻畫了真實網絡所有的大聚簇和短平均路徑長度的特性。小世界網絡的基本模型是W-S模型，算法描述如下:

(1)給定規則網:假如我們有一個節點總數為N，每個節點與它最近鄰的節點K=2k相連線的一維有限規則網，通常要求N>>K>>1。

(2)改寫舊連線:以概率p為規則網的每條舊連線重新布線，方法是將該連線的一個端點隨機地放到一個新位置上，但需要排除自身到自身的連線和重復連線。

如圖1所示，在規則網絡中，p=0，雖然具有很高的集團化系數C，但由于網絡結點的增加會破壞原有的網絡結構并導致平均特征路徑數的明顯增加，不符合“L～lnN”的小世界效應條件;在隨機網絡中，p=1，集團化系數C很小，也不符合小世界網絡的定義。因此，規則網絡和隨機網絡都不是小世界網絡。

在W-S模型中，p很小，W-S模型中的集團化系數C與規則網絡中的值很相近;另一方面，Watts Strogatz通過數字模擬得出在模型中加入捷徑使L下降很快，L與隨機網絡中的平均距離可比，實現了大世界向小世界的渡越。

W-S模型由于改寫連線，有可能出現孤立的集團，而且不便于理論分析。后來Newman和Watts提出了一個改進的模型。改進模型的算法描述如下:

(1)給定規則網:假如我們有一個節點總數為N，每個節點與它最近鄰的節點K=2k相連線的一維有限規則網，通常要求N>>K>>1;

(2)新增隨機網:對規則網的N個節點，以概率p在任意兩個節點之間連線，但不改動規則網的原有連線，也不允許自身到自身的連線和重復連線。

(3)BA網絡模型。W-S模型能夠反映現實網絡的小世界特征，然而現實世界中的網絡還被統計到極少節點擁有大量的連接，而眾多的節點僅具有少量連接的特征，這些也無法用隨機模型加以合理解釋。1999年Barabasi Albert從動態的、增長的觀點研究了復雜網絡具有冪律度分布的形成機理，提出了無尺度模型(BA模型)。BA模型的算法描述如下:

(1)初始:開始給定n0個節點;

(2)增長:在每個時間步重復增加一個新節點和m(m< =n0)條新連線;

(3)擇優:新節點按照擇優概率

選擇舊節點i與之連線，其中ki是舊節點i的度數。

他們在網絡的構造中引入了兩個重要的網絡演化機理:增長性和擇優連接性。這是從WWW網實際形成過程中抽象出來的，WWW網時刻都有新網頁增加，并且新網頁總是喜歡與有名的網頁相鏈接。為了論證這兩條網絡演化機理不可或缺，他們構造了兩個模型:模型A將擇優改為隨機，則產生增長的隨機網絡;模型B取消增長，由于網絡中節點數保持不變而連線不斷增加，最終網絡中節點全都相互連線，即演化為完全圖。可見兩條機理缺任一條都不能生成無標度網絡。

由于BA網絡本質上屬于小世界網絡，所以它具有小世界網絡的短平均路徑長度以及高集聚系數的特性。在1999年，Barabasi Albert用數量模擬表明具有k條邊的節點的概率服從指數為r=3的冪律分布，表達式為:p(k)∝k-y如圖2所示。

2. 小世界網絡應用研究概述。最早運用小世界理論，以及目前運用小世界理論最多、最具成效的研究就是疾病傳播問題。Watts Strogatz證明疾病全球傳播所需的時間和特征路徑長度非常相似，只要在傳播網絡中加入一些捷徑就可以使傳播速度明顯加快。運用病毒在小世界網絡中的傳播性質可推出信息在一個平均路徑長度為6的網絡中傳播要比在平均路徑長度為一百或一百萬的網絡中快得多。艾滋病、非典、禽流感等各種傳染病等對人類造成巨大的威脅，2003年的“非典”對于宏觀經濟和人類的生命安全都產生了巨大的負面影響;目前，禽流感也已成為世界關注的一個焦點。于是問題是:在特定的社會網絡中傳染病如何通過接觸關系傳播而導致流行呢?決策者如何控制這些疾病將損失降到最低限度呢?從復雜網絡的規律有望尋找到這些問題的合理的答案和解決途徑。

研究者運用小世界網絡的基本特征分析研究了Internet上信息傳播的特點，發現Internet中的網絡平均距離L是隨網絡大小N對數增長的，它明顯具有小世界效應。從結構上看，Internet的實際結構介乎于規則網絡和隨機網絡，表明其具有小世界效應。同時校園網以及超鏈接的存在和特性，也表明Internet具有集團化、聚類的特征。其中超鏈接是“斷鍵重連”也是捷徑。于是，人們利用小世界的特性有效地改善了網絡信息交流的效率。表現為，利用小世界網絡原理減少特征路徑長度提高可靠性;重視關鍵結點的建設來保證網絡的魯棒性和脆弱性并存;利用小世界統計特性控制網絡計算機病毒的傳播。

小世界網絡理論為經濟管理領域帶來了全新的思路，人們試圖用小世界理論去分析、解釋日益繁雜的市場經濟問題。該理論為經管問題提供了一種有效的技術工具，大大豐富了企業網絡理論的內容和方法。具體表現在，人們用小世界理論研究了NPD(新產品開發)團隊交流網絡、企業創新網絡、產學研合作創新、產業集群內的知識轉移等問題。這些研究的共同點在于:使用平均路徑長度模擬分析各節點之間的交流頻率;使用集團化系數模擬分析各節點之間集聚程度。從而極大的提高各集團的功能，實現資源共享和技術互補。

另外，小世界網絡在生物學、物理學及交通管理等方面都有很好的應用，學者們取得了一定的研究成果，利用這些成果可以去更好的規劃分析我們的實際生活。

三、 總結

網絡化是今后若干年許多研究領域發展的一個主流方向，因此對復雜網絡的研究具有重大的科學意義和應用價值。復雜網絡理論為應用提供堅實的理論與技術基礎。2003年8月18日令人震驚的是，北美突然大停電，就是復雜電力網絡的一系列級聯反應，導致整個電力系統土崩瓦解，美國和加拿大北部部分地區一夜間陷入一片黑暗之中，經濟損失和社會影響十分嚴重。這類網絡災變迫使人們深入研究這種災變與網絡的結構、功能及動力學性質的內在關系。這也是今后我們研究復雜網絡的重點所在。

在網絡技術的迅猛發展以及各種智能化工具和方法紛紛涌現的今天，相信復雜網絡理論會得到更充分的運用和更廣泛的發展。

參考文獻:

1. 郭雷，許曉鳴.復雜網絡.上海:上?？萍冀逃霭嫔?，2006.

2. 黃萍，張許杰，劉剛.小世界網絡的研究現狀與展望.情報雜志，2007，(4):65-68.

3. 周濤，柏文潔，汪秉宏.復雜網絡研究概述.物理，2005，34(1):31-36.

作者簡介:劉曉慶，暨南大學管理學院博士生，廣東金融學院計算機科學與技術系講師;陳仕鴻，廣東外語外貿大學思科信息學院講師。

收稿日期:2009-11-15。