復(fù)雜網(wǎng)絡(luò)理論研究狀況綜述

摘要:文章首先簡要介紹了復(fù)雜網(wǎng)絡(luò)理論;然后重點(diǎn)論述了小世界網(wǎng)絡(luò)模型的研究背景、基礎(chǔ)概念及模型的統(tǒng)計(jì)特性;最后對于小世界網(wǎng)絡(luò)在各個領(lǐng)域的研究進(jìn)行了簡單的概述。

關(guān)鍵詞:復(fù)雜網(wǎng)絡(luò);小世界網(wǎng)絡(luò);無標(biāo)度網(wǎng)絡(luò)

一、 復(fù)雜網(wǎng)絡(luò)概述

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

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

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

2. 復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)性質(zhì)。復(fù)雜網(wǎng)絡(luò)的不同的統(tǒng)計(jì)性質(zhì)決定了不同的網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)，而結(jié)構(gòu)又決定了系統(tǒng)的功能。所以，我們先了解一下復(fù)雜網(wǎng)絡(luò)的相關(guān)統(tǒng)計(jì)性質(zhì)。

(1)度及度分布。在網(wǎng)絡(luò)中，節(jié)點(diǎn)的度是與目標(biāo)節(jié)點(diǎn)相連的邊的條數(shù)。即與該節(jié)點(diǎn)相鄰的節(jié)點(diǎn)的數(shù)目，朋友的個數(shù)。而網(wǎng)絡(luò)的度指網(wǎng)絡(luò)中所有節(jié)點(diǎn)度的平均值。

度分布P(k)指網(wǎng)絡(luò)中一個任意選擇的節(jié)點(diǎn)，它的度恰好為k的概率。即，不同度數(shù)的節(jié)點(diǎn)個數(shù)占節(jié)點(diǎn)總數(shù)的比率。

在上面介紹的幾種網(wǎng)絡(luò)中，對于隨機(jī)網(wǎng)絡(luò)，當(dāng)N非常大時，隨機(jī)網(wǎng)絡(luò)的節(jié)點(diǎn)的度分布近似服從Poisson分布，表達(dá)式如下:

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

隨機(jī)網(wǎng)絡(luò)的平均路徑長度滿足如下表達(dá)式:

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

隨機(jī)網(wǎng)絡(luò)的聚集系數(shù)滿足如下表達(dá)式:

二、 小世界網(wǎng)絡(luò)概述

1. 小世界網(wǎng)絡(luò)理論。

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

這個玄妙理論表明“世界真小啊!”，“小世界”由此得名。它引來了數(shù)學(xué)家、物理學(xué)家和電腦科學(xué)家紛紛投入研究，結(jié)果發(fā)現(xiàn)，世界上許多其他的網(wǎng)絡(luò)也有極相似的結(jié)構(gòu)。比如，人際網(wǎng)絡(luò)和WWW的架構(gòu)幾乎完全一樣，通過超文本鏈接的網(wǎng)絡(luò)、經(jīng)濟(jì)活動中的商業(yè)聯(lián)系網(wǎng)絡(luò)、甚至人類腦神經(jīng)元、以及細(xì)胞內(nèi)的分子交互作用網(wǎng)絡(luò)，有著完全相同的組織結(jié)構(gòu)。科學(xué)家們把這種現(xiàn)象稱為小世界效應(yīng)。

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

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

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

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

如圖1所示，在規(guī)則網(wǎng)絡(luò)中，p=0，雖然具有很高的集團(tuán)化系數(shù)C，但由于網(wǎng)絡(luò)結(jié)點(diǎn)的增加會破壞原有的網(wǎng)絡(luò)結(jié)構(gòu)并導(dǎo)致平均特征路徑數(shù)的明顯增加，不符合“L～lnN”的小世界效應(yīng)條件;在隨機(jī)網(wǎng)絡(luò)中，p=1，集團(tuán)化系數(shù)C很小，也不符合小世界網(wǎng)絡(luò)的定義。因此，規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)都不是小世界網(wǎng)絡(luò)。

在W-S模型中，p很小，W-S模型中的集團(tuán)化系數(shù)C與規(guī)則網(wǎng)絡(luò)中的值很相近;另一方面，Watts Strogatz通過數(shù)字模擬得出在模型中加入捷徑使L下降很快，L與隨機(jī)網(wǎng)絡(luò)中的平均距離可比，實(shí)現(xiàn)了大世界向小世界的渡越。

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

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

(2)新增隨機(jī)網(wǎng):對規(guī)則網(wǎng)的N個節(jié)點(diǎn)，以概率p在任意兩個節(jié)點(diǎn)之間連線，但不改動規(guī)則網(wǎng)的原有連線，也不允許自身到自身的連線和重復(fù)連線。

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

(1)初始:開始給定n0個節(jié)點(diǎn);

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

(3)擇優(yōu):新節(jié)點(diǎn)按照擇優(yōu)概率

選擇舊節(jié)點(diǎn)i與之連線，其中ki是舊節(jié)點(diǎn)i的度數(shù)。

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

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

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

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

小世界網(wǎng)絡(luò)理論為經(jīng)濟(jì)管理領(lǐng)域帶來了全新的思路，人們試圖用小世界理論去分析、解釋日益繁雜的市場經(jīng)濟(jì)問題。該理論為經(jīng)管問題提供了一種有效的技術(shù)工具，大大豐富了企業(yè)網(wǎng)絡(luò)理論的內(nèi)容和方法。具體表現(xiàn)在，人們用小世界理論研究了NPD(新產(chǎn)品開發(fā))團(tuán)隊(duì)交流網(wǎng)絡(luò)、企業(yè)創(chuàng)新網(wǎng)絡(luò)、產(chǎn)學(xué)研合作創(chuàng)新、產(chǎn)業(yè)集群內(nèi)的知識轉(zhuǎn)移等問題。這些研究的共同點(diǎn)在于:使用平均路徑長度模擬分析各節(jié)點(diǎn)之間的交流頻率;使用集團(tuán)化系數(shù)模擬分析各節(jié)點(diǎn)之間集聚程度。從而極大的提高各集團(tuán)的功能，實(shí)現(xiàn)資源共享和技術(shù)互補(bǔ)。

另外，小世界網(wǎng)絡(luò)在生物學(xué)、物理學(xué)及交通管理等方面都有很好的應(yīng)用，學(xué)者們?nèi)〉昧艘欢ǖ难芯砍晒眠@些成果可以去更好的規(guī)劃分析我們的實(shí)際生活。

三、 總結(jié)

網(wǎng)絡(luò)化是今后若干年許多研究領(lǐng)域發(fā)展的一個主流方向，因此對復(fù)雜網(wǎng)絡(luò)的研究具有重大的科學(xué)意義和應(yīng)用價(jià)值。復(fù)雜網(wǎng)絡(luò)理論為應(yīng)用提供堅(jiān)實(shí)的理論與技術(shù)基礎(chǔ)。2003年8月18日令人震驚的是，北美突然大停電，就是復(fù)雜電力網(wǎng)絡(luò)的一系列級聯(lián)反應(yīng)，導(dǎo)致整個電力系統(tǒng)土崩瓦解，美國和加拿大北部部分地區(qū)一夜間陷入一片黑暗之中，經(jīng)濟(jì)損失和社會影響十分嚴(yán)重。這類網(wǎng)絡(luò)災(zāi)變迫使人們深入研究這種災(zāi)變與網(wǎng)絡(luò)的結(jié)構(gòu)、功能及動力學(xué)性質(zhì)的內(nèi)在關(guān)系。這也是今后我們研究復(fù)雜網(wǎng)絡(luò)的重點(diǎn)所在。

在網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展以及各種智能化工具和方法紛紛涌現(xiàn)的今天，相信復(fù)雜網(wǎng)絡(luò)理論會得到更充分的運(yùn)用和更廣泛的發(fā)展。

參考文獻(xiàn):

1. 郭雷，許曉鳴.復(fù)雜網(wǎng)絡(luò).上海:上海科技教育出版社，2006.

2. 黃萍，張?jiān)S杰，劉剛.小世界網(wǎng)絡(luò)的研究現(xiàn)狀與展望.情報(bào)雜志，2007，(4):65-68.

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

作者簡介:劉曉慶，暨南大學(xué)管理學(xué)院博士生，廣東金融學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系講師;陳仕鴻，廣東外語外貿(mào)大學(xué)思科信息學(xué)院講師。

收稿日期:2009-11-15。