吳今培

（五邑大學(xué) 智能技術(shù)與系統(tǒng)研究所，廣東 江門 529020）

復(fù)雜網(wǎng)絡(luò)初探

吳今培

（五邑大學(xué) 智能技術(shù)與系統(tǒng)研究所，廣東 江門 529020）

討論了復(fù)雜網(wǎng)絡(luò)的基本概念，重點(diǎn)介紹了小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)，提出了一些值得進(jìn)一步研究的復(fù)雜網(wǎng)絡(luò)問題.

復(fù)雜網(wǎng)絡(luò)；小世界網(wǎng)絡(luò)；無標(biāo)度網(wǎng)絡(luò)

人類從遠(yuǎn)古走來，很早就構(gòu)造出林中路，并且把路構(gòu)造成網(wǎng)絡(luò)；在農(nóng)業(yè)社會(huì)，人又構(gòu)造出各種水利網(wǎng)絡(luò)，通過航海網(wǎng)絡(luò)，資本主義才遍布全世界；在工業(yè)社會(huì)，普通的小路被公路、鐵路所替代，休閑散步的路被高速公路所淹沒，公路和鐵路之網(wǎng)覆蓋大地；在今天的信息時(shí)代，各個(gè)國(guó)家致力于建設(shè)自己的信息高速公路，即新型的信息網(wǎng)路，如今，Internet/www網(wǎng)絡(luò)已經(jīng)基本覆蓋整個(gè)世界. 與人們生活息息相關(guān)的還有通信網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、航空網(wǎng)絡(luò)、銀行網(wǎng)絡(luò)、商業(yè)網(wǎng)絡(luò)等等. 人類把自己生存的世界變成了網(wǎng)絡(luò)世界，網(wǎng)絡(luò)越發(fā)達(dá)、越有效，世界就越小，人的社會(huì)性就越得到強(qiáng)化.

網(wǎng)絡(luò)如此廣泛、如此重要，人類處在網(wǎng)絡(luò)的叢林中. 如何開辟出一條林中路，揭示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的形成機(jī)制，探索網(wǎng)絡(luò)的演化規(guī)律和整體行為，認(rèn)識(shí)網(wǎng)絡(luò)內(nèi)部深?yuàn)W的動(dòng)力學(xué)特性，挖掘網(wǎng)絡(luò)展現(xiàn)出的廣泛、潛在的應(yīng)用價(jià)值等問題，正引起國(guó)內(nèi)外學(xué)術(shù)界的高度重視，掀起了復(fù)雜網(wǎng)絡(luò)的研究熱潮.

1 復(fù)雜網(wǎng)絡(luò)的表述方式和主要特征度量

復(fù)雜網(wǎng)絡(luò)是指由一個(gè)節(jié)點(diǎn)集V和一個(gè)邊集E組成的元組(V,E)，V中元素稱為節(jié)點(diǎn)或頂點(diǎn)（node或 vertex），E中元素稱為邊或連線（edge或 link），且E中的每條邊li有V的一對(duì)節(jié)點(diǎn)(u,v)與之對(duì)應(yīng)，如果E中任意的節(jié)點(diǎn)對(duì)(u,v)和(v,u)對(duì)應(yīng)同一條邊，則該網(wǎng)絡(luò)稱為無向網(wǎng)絡(luò)，否則為有向網(wǎng)絡(luò)；如果E中所有邊的長(zhǎng)度均為1，即li=1，則稱網(wǎng)絡(luò)為無權(quán)網(wǎng)絡(luò)，否則為加權(quán)網(wǎng)絡(luò).V中元素個(gè)數(shù)和E中元素個(gè)數(shù)分別稱網(wǎng)絡(luò)的階（order）和邊數(shù)（size）. 階和邊數(shù)都有限的網(wǎng)絡(luò)稱為有限網(wǎng)絡(luò)或有限圖（finite graph）. 邊所連接的節(jié)點(diǎn)稱為端點(diǎn)（end-vertices），兩端點(diǎn)相同的邊稱為環(huán)（loop）. 有公共起點(diǎn)并且有公共終點(diǎn)的兩條邊稱為平行邊（parallel edges）或重邊（multi-edge）.

復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的宏觀特性通常由給定網(wǎng)絡(luò)G= (V,E)微觀量的統(tǒng)計(jì)分布或統(tǒng)計(jì)平均值來刻畫，其主要特征量為度分布、集聚系數(shù)和平均路徑長(zhǎng)度[1].

1）度分布（Degree Distribution）

網(wǎng)絡(luò)節(jié)點(diǎn)i的度k為與該節(jié)點(diǎn)連接的邊的總數(shù)目. 在不同的網(wǎng)絡(luò)中度代表不同的含義. 如在朋友關(guān)系網(wǎng)中，每一個(gè)人都是一個(gè)節(jié)點(diǎn)，兩個(gè)人若是朋友則他們之間就連一條邊，一個(gè)節(jié)點(diǎn)的度也就是一個(gè)人的朋友數(shù). 網(wǎng)絡(luò)中節(jié)點(diǎn)的度分布用概率分布函數(shù)P(k)表示，其含義為一個(gè)任意選擇的節(jié)點(diǎn)恰好有k條邊連接的概率. 在目前的網(wǎng)絡(luò)研究中，2種度分布較為常見：一種是指數(shù)度分布P(k)~e?k，即P(k)隨著k的增大以指數(shù)形式衰減；另一種是冪律分布，即P(k)~k?γ，其中γ稱為度指數(shù)，不同γ的網(wǎng)絡(luò)其動(dòng)力學(xué)性質(zhì)也不同.

2）集聚系數(shù)（Clustering Coefficient）

3）平均路徑長(zhǎng)度（Average Path Length）

基于復(fù)雜網(wǎng)絡(luò)宏觀特征量的知識(shí)，以下2個(gè)概念[2]在當(dāng)代復(fù)雜網(wǎng)絡(luò)的思考中占有重要地位：

第一、小世界（Small-World）的概念

它以簡(jiǎn)單的措辭描述了現(xiàn)實(shí)中的大多數(shù)網(wǎng)絡(luò)盡管規(guī)模很大，但是任意2個(gè)節(jié)點(diǎn)間卻有一條相當(dāng)短的路徑的事實(shí). 從日常生活看，偶爾碰到一個(gè)陌生人，同他簡(jiǎn)單交談之后，竟然發(fā)現(xiàn)他們同時(shí)與第 3個(gè)人相識(shí)，于是他們不約而同地發(fā)出這個(gè)世界真小的感嘆. 正如麥克盧漢所說，地球變得越來越小，變成一個(gè)地球村，也就是說，變成一個(gè)小世界.

小世界概念是著名的Miligram“六度分離”（six degrees of separation）原則的一種拓廣，其基本思想是：如果你現(xiàn)在想與世界上任何一個(gè)人聯(lián)系交朋友的話，應(yīng)該怎么辦？你可以這樣做：找一個(gè)最有可能和他有聯(lián)系的親友，把問候轉(zhuǎn)達(dá)給他，然后他也照樣去找下一位親友，這樣你最多通過6個(gè)人就能夠認(rèn)識(shí)任何一個(gè)陌生人. 也就是說，你和地球上任何一個(gè)陌生人之間所間隔的人不會(huì)超過6個(gè)（平均6個(gè)）.

第二、標(biāo)度不變性（Scale-Free）的概念

任何事物都有其特征尺度（簡(jiǎn)稱標(biāo)度），知道這些特征尺度（如特征長(zhǎng)度、特征容積、特征統(tǒng)計(jì)量等），我們就能夠區(qū)分和描述事物. 近年來，科學(xué)家發(fā)現(xiàn)在很多不同的網(wǎng)絡(luò)中，它的度分布都遵循冪次定律，即P(k) =ck?γ，其圖形沒有峰值且隨k衰減，如圖 1所示. 從圖 1還可以看出，大多數(shù)節(jié)點(diǎn)僅有少量連線，而少數(shù)節(jié)點(diǎn)擁有大量連線. 因?yàn)楣?jié)點(diǎn)的異質(zhì)性，于是特征標(biāo)度消失了. 如果對(duì)冪律度分布式兩邊都取對(duì)數(shù)會(huì)得到

顯然，logP(k)與logk之間的關(guān)系是一種線性關(guān)系，如圖 2所示. 標(biāo)度不變性可以從直線處看出來，在某個(gè)標(biāo)度上并沒有什么特征使這個(gè)標(biāo)度顯得很特別.

圖1 冪律度分布

圖2 雙對(duì)數(shù)坐標(biāo)下冪律度分布

2 復(fù)雜網(wǎng)絡(luò)的發(fā)展歷程

網(wǎng)絡(luò)作為一門科學(xué)，其發(fā)展大致經(jīng)歷了 3個(gè)階段：1）一百多年前歐拉（Euler）開創(chuàng)了圖論學(xué)科，科學(xué)家們認(rèn)為實(shí)際系統(tǒng)元素之間的關(guān)系可以用一些規(guī)則加以描述，這就是規(guī)則網(wǎng)絡(luò). 2）四十多年前，Erdo和Rényi引入隨機(jī)圖論，認(rèn)為大規(guī)模網(wǎng)絡(luò)的形成過程中，是沒有明確設(shè)計(jì)原則的、節(jié)點(diǎn)間的連接是完全隨機(jī)的，這就是隨機(jī)網(wǎng)絡(luò). 規(guī)則網(wǎng)絡(luò)是秩序的象征，隨機(jī)網(wǎng)絡(luò)是混亂的代表，現(xiàn)實(shí)網(wǎng)絡(luò)不太可能是這兩個(gè)極端之一. 3）近十年來，科學(xué)家發(fā)現(xiàn)大量的實(shí)際網(wǎng)絡(luò)既非規(guī)則網(wǎng)絡(luò)，也非隨機(jī)網(wǎng)絡(luò)，而是具有統(tǒng)計(jì)特性的網(wǎng)絡(luò). 20世紀(jì)末，兩項(xiàng)開創(chuàng)性的工作揭開了復(fù)雜網(wǎng)絡(luò)研究的新紀(jì)元：一項(xiàng)是Cornell大學(xué)的Watts和Strogatz于1998年6月發(fā)表在《自然》的《小世界網(wǎng)絡(luò)的集體動(dòng)力學(xué)》[3]；另外一項(xiàng)是Notre Dame大學(xué)的Barabási和Alber于1999年10月發(fā)表在《科學(xué)》的《隨機(jī)網(wǎng)絡(luò)中標(biāo)度的涌現(xiàn)》[4]. 這兩項(xiàng)工作分別揭示了復(fù)雜網(wǎng)絡(luò)的小世界效應(yīng)（small-world effect）和無標(biāo)度特性（small-free effect），并建立了相應(yīng)模型以解釋上述特性的產(chǎn)生機(jī)理.

2.1 規(guī)則網(wǎng)絡(luò)

在很長(zhǎng)一段時(shí)間里，人們認(rèn)為實(shí)際系統(tǒng)各元素之間的關(guān)系可以用一些規(guī)則網(wǎng)絡(luò)表示. 規(guī)則網(wǎng)絡(luò)一般是由N個(gè)節(jié)點(diǎn)構(gòu)成的環(huán)狀網(wǎng)絡(luò)，其中每個(gè)節(jié)點(diǎn)只與它最近的k個(gè)節(jié)點(diǎn)連接. 在規(guī)則網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)的度和集聚系數(shù)是相同的. 節(jié)點(diǎn)的度分布函數(shù)為P(k)=δ(k?K)，節(jié)點(diǎn)的集聚系數(shù)C=3(k?2d)4(k?d)（d為網(wǎng)絡(luò)維數(shù)）. 規(guī)則網(wǎng)絡(luò)的集聚程度高，平均路徑長(zhǎng).

2.2 隨機(jī)網(wǎng)絡(luò)

構(gòu)成的圖，可以存在條邊，我們從中隨機(jī)連接M條邊所構(gòu)成的網(wǎng)絡(luò)就叫做隨機(jī)網(wǎng)絡(luò). ER網(wǎng)絡(luò)的節(jié)點(diǎn)服從泊松分布，即

它是一條鐘形曲線，如圖3所示. 該圖形在網(wǎng)絡(luò)平均度數(shù)處有一個(gè)峰值，大多數(shù)節(jié)點(diǎn)的度都集中在峰值附近，而遠(yuǎn)離它的節(jié)點(diǎn)所占比例很快衰減，說明節(jié)點(diǎn)有同質(zhì)性.

在ER網(wǎng)絡(luò)中，2個(gè)節(jié)點(diǎn)之間是否連邊不再是確定的事情，而是根據(jù)概率而決定. 但在過去長(zhǎng)達(dá)40年的時(shí)間里，科學(xué)家一直認(rèn)為隨機(jī)網(wǎng)絡(luò)是描述真實(shí)系統(tǒng)最適宜的網(wǎng)絡(luò).

需要指出，因?yàn)镋R模型的節(jié)點(diǎn)數(shù)是預(yù)先給定的，所以它是靜態(tài)的、固定的、平衡的網(wǎng)絡(luò). 與此相對(duì)應(yīng)，若網(wǎng)絡(luò)模型的節(jié)點(diǎn)數(shù)不是預(yù)先給定的，而是逐步增減的，則是動(dòng)態(tài)的、增長(zhǎng)的、非平衡的網(wǎng)絡(luò)，或者稱為演化網(wǎng)絡(luò)（evolving network）.

圖3 泊松度分布

2.3 小世界網(wǎng)絡(luò)（Small-World Networks）

Watts和 Strogatz巧妙地結(jié)合規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)的特點(diǎn)給出了小世界網(wǎng)絡(luò)的生成機(jī)制模型（WS模型）. 該模型由一個(gè)具有N個(gè)節(jié)點(diǎn)的環(huán)開始，環(huán)上每一個(gè)節(jié)點(diǎn)與兩側(cè)各有m條邊相連，然后對(duì)每條邊以概率p隨機(jī)進(jìn)行重新連接（自我連接和重復(fù)連接除外），這些重新連接的邊叫“長(zhǎng)程連接”，長(zhǎng)程連接大大縮短了網(wǎng)絡(luò)的平均路徑長(zhǎng)度，從而提高了網(wǎng)絡(luò)的集聚系數(shù). WS模型的生成方法如圖4所示，4-a圖為規(guī)則網(wǎng)絡(luò)，網(wǎng)絡(luò)的邊較少，平均路徑較長(zhǎng)；4-c圖為隨機(jī)網(wǎng)絡(luò)，它的邊很多，平均路輕短，4-b是一個(gè)典型的小世界網(wǎng)絡(luò). 當(dāng)p=0時(shí)是規(guī)則網(wǎng)絡(luò)，p=1時(shí)為隨機(jī)網(wǎng)絡(luò)，對(duì)于 0

圖4 網(wǎng)絡(luò)結(jié)構(gòu)的3種類型

科學(xué)家通過大量的實(shí)例研究指出：全世界所有的人造網(wǎng)絡(luò)包括互聯(lián)網(wǎng)、人際關(guān)系網(wǎng)等都是小世界網(wǎng)絡(luò). 幾年前，美國(guó)科學(xué)家們把好萊塢所有的老電影演員請(qǐng)來做實(shí)驗(yàn)，每一個(gè)演員是一個(gè)節(jié)點(diǎn)，兩個(gè)演員合作演出同一部電影，劃一個(gè)邊，就構(gòu)成了一個(gè)電影演員合作網(wǎng). 通過統(tǒng)計(jì)數(shù)據(jù)分析表明：2個(gè)演員的平均“距離”比 6還小. 以上現(xiàn)象說明：盡管復(fù)雜網(wǎng)絡(luò)的規(guī)模很大，擁有成千上萬甚至更多的網(wǎng)絡(luò)節(jié)點(diǎn)，但是 2個(gè)節(jié)點(diǎn)之間的平均路徑距離卻比人們想象得要短很多. 再以朋友關(guān)系網(wǎng)絡(luò)為例，如果在我的朋友圈當(dāng)中，任意地找2個(gè)朋友，那么他們兩個(gè)人也互為朋友的概率有多大呢？根據(jù)人們的日常經(jīng)驗(yàn)來看，大多數(shù)人直接和同事、同學(xué)、鄰居相識(shí)而成為朋友，所以在我的朋友圈中任意兩個(gè)人互為朋友的概率事實(shí)上也是不小的. 而一個(gè)網(wǎng)絡(luò)如果它是完全隨機(jī)的話，那么我的朋友當(dāng)中兩個(gè)人互為朋友的概率應(yīng)該是很小的. 這說明與傳統(tǒng)的隨機(jī)網(wǎng)絡(luò)不同，小世界網(wǎng)絡(luò)的聚類效應(yīng)非常明顯，它具有“物以類聚，人以群分”的特性. 實(shí)證研究表明：許多現(xiàn)實(shí)網(wǎng)絡(luò)都表現(xiàn)出聚類現(xiàn)象，這一點(diǎn)引起了人們的廣泛關(guān)注.

2.4 無標(biāo)度網(wǎng)絡(luò)（Scale-Free Networks）[5-8]

1999年，由Barabási和Albert提出的無標(biāo)度網(wǎng)絡(luò)（簡(jiǎn)稱BA網(wǎng)絡(luò)）建立在2個(gè)基本假設(shè)之上：增長(zhǎng)性與擇優(yōu)選擇. 小世界網(wǎng)絡(luò)考慮了網(wǎng)絡(luò)邊的變動(dòng)，但認(rèn)為節(jié)點(diǎn)在網(wǎng)絡(luò)的整個(gè)形成過程中的數(shù)目是固定不變的；BA網(wǎng)絡(luò)則進(jìn)一步假定網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)目是不斷增長(zhǎng)的，也就是說，現(xiàn)實(shí)網(wǎng)絡(luò)因持續(xù)不斷地向網(wǎng)絡(luò)中加入新的節(jié)點(diǎn)演化而成. 這顯然更符合互聯(lián)網(wǎng)或其他具有社會(huì)屬性的網(wǎng)絡(luò)的實(shí)際情況. 更重要的是第 2個(gè)假設(shè)：在新增加進(jìn)來的節(jié)點(diǎn)與已有節(jié)點(diǎn)建立連接的時(shí)候，具有一定“選優(yōu)”傾向. 例如，互聯(lián)網(wǎng)中每時(shí)每刻都有新的網(wǎng)站增加，并且新建立的網(wǎng)站顯然傾向于與已經(jīng)有相當(dāng)知名度的網(wǎng)站鏈接，如新浪、搜狐等. 又如，在演員合作關(guān)系網(wǎng)中，新演員當(dāng)然更愿意與明星合作拍電影.

Barabási和Albert根據(jù)以上的觀察和分析，建立了無標(biāo)度網(wǎng)絡(luò)的BA模型，其生成算法如下：

1）初始：t=0時(shí)給定m0個(gè)節(jié)點(diǎn).

2）增長(zhǎng)：從m0個(gè)節(jié)點(diǎn)開始，在每一個(gè)時(shí)間間隔，一個(gè)新節(jié)點(diǎn)被引入并和m≤m0個(gè)已存在的節(jié)點(diǎn)相連接.

3）擇優(yōu)：新節(jié)點(diǎn)連接到老節(jié)點(diǎn)i的概率，正比于節(jié)點(diǎn)i的連接數(shù)（度）ki大小，即

式中，分母求和為取遍網(wǎng)絡(luò)已有各節(jié)點(diǎn)的連接. 根據(jù)上述步驟重復(fù)t次后，得到一個(gè)有N=t+m0個(gè)節(jié)點(diǎn)和mt條邊的網(wǎng)絡(luò)，其標(biāo)度不隨時(shí)間變化，相對(duì)應(yīng)的度分布可用冪律函數(shù)P(k)~k?3來描述.

在過去幾年中，科學(xué)家發(fā)現(xiàn)在很多不同的系統(tǒng)中都具有無標(biāo)度結(jié)構(gòu)，包括因特網(wǎng)、通信網(wǎng)、社會(huì)關(guān)系網(wǎng)和人體的細(xì)胞代謝網(wǎng)等. 這些網(wǎng)絡(luò)最重要的特性是其標(biāo)度不變性：大部分節(jié)點(diǎn)只有少數(shù)幾個(gè)連接而某些節(jié)點(diǎn)卻擁有與其他節(jié)點(diǎn)的大量連接. 這些具有大量連接的節(jié)點(diǎn)稱為“集散節(jié)點(diǎn)”（或稱中樞節(jié)點(diǎn)），其所擁有的連接可能高達(dá)數(shù)百、數(shù)千甚至數(shù)百萬. 由于無標(biāo)度網(wǎng)絡(luò)具有增長(zhǎng)性和擇優(yōu)連接這兩種機(jī)制，有助于形成集散節(jié)點(diǎn)；當(dāng)新的節(jié)點(diǎn)出現(xiàn)時(shí)，它們更傾向于連接到已經(jīng)有較多連接的節(jié)點(diǎn)，隨著時(shí)間的推進(jìn)，這些節(jié)點(diǎn)就擁有比其他節(jié)點(diǎn)更多的連接數(shù)目. 這種“富者愈富”的過程，有利于集散節(jié)點(diǎn)形成. 這一特性決定了無標(biāo)度網(wǎng)絡(luò)可以承受意外的故障（或攻擊），具有很強(qiáng)的穩(wěn)定性或魯棒性，但面對(duì)有意的協(xié)同式攻擊卻很脆弱. 了解這一些特性，可能導(dǎo)致許多領(lǐng)域出現(xiàn)新的應(yīng)用：例如對(duì)天花等嚴(yán)重疾病的疫苗接種，如果能針對(duì)集散節(jié)點(diǎn)（即那些與很多人具有連接關(guān)系的人）進(jìn)行，也許可以達(dá)到最大的效果；此外，若能識(shí)別出那些與特定疾病有關(guān)的集散點(diǎn)分子就可開發(fā)只針對(duì)這些集散節(jié)點(diǎn)作用的新藥物，以便殺死它們而又不會(huì)影響健康的組織.

大家知道：信息社會(huì)人們不僅生活在各種網(wǎng)絡(luò)環(huán)境中，而且對(duì)諸如互聯(lián)網(wǎng)、通信網(wǎng)等的依賴程度日益增高；因此，這些網(wǎng)絡(luò)的可靠性、安全性問題就顯得格外重要. 研究表明無標(biāo)度網(wǎng)絡(luò)對(duì)意外故障具有很強(qiáng)的承受能力. 例如，互聯(lián)網(wǎng)雖然每時(shí)每刻都有數(shù)百個(gè)路由器失效，但網(wǎng)絡(luò)卻很少因此受到大的影響. 生命系統(tǒng)同樣也具有這種強(qiáng)韌性：雖然細(xì)胞內(nèi)存在諸如突變和蛋白質(zhì)出錯(cuò)等數(shù)以千計(jì)的錯(cuò)誤，但人體卻很少因此發(fā)生嚴(yán)重的后果. 這種強(qiáng)韌性的來源是什么呢？直覺告訴我們，如果大部分節(jié)點(diǎn)出現(xiàn)癱瘓，將不可避免地導(dǎo)致網(wǎng)絡(luò)的分裂. 這對(duì)于隨機(jī)網(wǎng)絡(luò)來說絕對(duì)如此，因?yàn)殡S機(jī)網(wǎng)絡(luò)中若有較大部分的節(jié)點(diǎn)被去除，網(wǎng)絡(luò)必然潰散成彼此無法通信的小型孤島. 但是對(duì)無標(biāo)度網(wǎng)絡(luò)的模擬測(cè)試結(jié)果則展現(xiàn)了全然不同的情況：即使互聯(lián)網(wǎng)路由器中隨機(jī)選擇的失效節(jié)點(diǎn)比例高達(dá)80%，剩余的路由器還是能組成一個(gè)完整的集群并保證任意兩個(gè)節(jié)點(diǎn)間存在通路. 同樣，要擾亂細(xì)胞內(nèi)蛋白質(zhì)的交互網(wǎng)絡(luò)也很困難：測(cè)試顯示，即使在細(xì)胞內(nèi)隨機(jī)制造較高比例的突變，那些沒有改變的蛋白質(zhì)還是會(huì)正常地繼續(xù)合作.

總之，無標(biāo)度網(wǎng)絡(luò)在隨機(jī)攻擊面前具有很強(qiáng)的穩(wěn)定性或魯棒性，其本質(zhì)源于網(wǎng)絡(luò)中的連接服從冪律分布，它是一個(gè)由少數(shù)集散節(jié)點(diǎn)所主控的系統(tǒng). 隨機(jī)干擾方式所破壞的主要是那些數(shù)目遠(yuǎn)大于集散節(jié)點(diǎn)的不重要的節(jié)點(diǎn)，與那些幾乎連接所有節(jié)點(diǎn)的集散節(jié)點(diǎn)相比，那些不重要的節(jié)點(diǎn)只擁有少量的連接，因而去除它們不會(huì)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)產(chǎn)生重大的影響. 對(duì)于隨機(jī)網(wǎng)絡(luò)而言，盡管連接是隨機(jī)安置的，但網(wǎng)絡(luò)節(jié)點(diǎn)連接的分布遵循鐘形曲線分布. 按照這種分布，大部分節(jié)點(diǎn)擁有的連接數(shù)目都差不多，絕對(duì)不可能出現(xiàn)集散節(jié)點(diǎn)，因此面對(duì)一般的隨機(jī)破壞，網(wǎng)絡(luò)就可能不堪一擊.

無標(biāo)度網(wǎng)絡(luò)對(duì)于集散節(jié)點(diǎn)的依賴，也帶來了一個(gè)嚴(yán)重問題，即網(wǎng)絡(luò)對(duì)于蓄意的、針對(duì)集散節(jié)點(diǎn)的攻擊顯得非常脆弱. 這時(shí)被刻意去除的那一小部分節(jié)點(diǎn)都會(huì)是連接度數(shù)很高的節(jié)點(diǎn)，因此整個(gè)網(wǎng)絡(luò)的連通性就會(huì)發(fā)生劇烈的變化甚至被分成若干不連通的子網(wǎng)，網(wǎng)絡(luò)的魯棒性大大降低甚至完全喪失. 這在互聯(lián)網(wǎng)的安全問題上表現(xiàn)尤其突出，因此，在建立互聯(lián)網(wǎng)的安全模型時(shí)，必須考慮冪律分布的特征. 近年來，大型電力網(wǎng)絡(luò)的事故也表現(xiàn)出類似的規(guī)律. 如何采取有效措施保護(hù)集散節(jié)點(diǎn)，以避免小規(guī)模的毀壞造成的大面積的崩潰，這還有待進(jìn)一步研究. 從圖5可見，隨機(jī)網(wǎng)絡(luò)若有大量節(jié)點(diǎn)發(fā)生意外故障，可能導(dǎo)致系統(tǒng)潰散成彼此無法通信的孤島. 相比之下，無標(biāo)度網(wǎng)絡(luò)承受這類故障的能力較強(qiáng)，如圖6所示. 但是從圖7可以看出，如果遭到協(xié)同式攻擊，它也會(huì)變得非常脆弱.

圖5 隨機(jī)網(wǎng)絡(luò)意外故障

圖6 無標(biāo)度網(wǎng)絡(luò)意外故障

圖7 無標(biāo)度網(wǎng)絡(luò)受協(xié)同式攻擊

綜上所述，無標(biāo)度網(wǎng)絡(luò)的提出極大地改變了人們對(duì)復(fù)雜外部世界的認(rèn)識(shí)，集散節(jié)點(diǎn)的存在，讓我們認(rèn)識(shí)到了以前的網(wǎng)絡(luò)理論尚未涉及的問題：各種復(fù)雜系統(tǒng)具有相同的嚴(yán)格結(jié)構(gòu)，都受制于某些基本的法則，這些法則似乎可同等地適用于細(xì)胞、計(jì)算機(jī)、語言和社會(huì). 更進(jìn)一步認(rèn)識(shí)這些法則會(huì)幫助我們解決一系列重要問題，包括防備黑客的攻擊、阻止流行病的傳播、開發(fā)更好的藥物等.

3 復(fù)雜網(wǎng)絡(luò)研究中的若干問題

3.1 網(wǎng)絡(luò)演化[9-10]

WS模型和 BA模型對(duì)于網(wǎng)絡(luò)科學(xué)的發(fā)展起著極其重要的作用，但由于現(xiàn)實(shí)網(wǎng)絡(luò)的多樣性和復(fù)雜性，需要從不同角度深入研究不同復(fù)雜網(wǎng)絡(luò)的生成方法、建立更加符合實(shí)際網(wǎng)絡(luò)的理論模型.

1）從網(wǎng)絡(luò)的實(shí)際情況看，現(xiàn)實(shí)世界的許多網(wǎng)絡(luò)具有公認(rèn)的3個(gè)共同特性：節(jié)點(diǎn)服從度指數(shù)γ介于 2~3之間的冪律分布、網(wǎng)絡(luò)簇系數(shù)大、節(jié)點(diǎn)的平均路徑距離短. 而 BA網(wǎng)絡(luò)的簇系數(shù)很小，并且度分布指數(shù)γ=3，這與實(shí)際網(wǎng)絡(luò)比較起來存在明顯差別. 例如，互聯(lián)網(wǎng)的γ=2.1，電話網(wǎng)的γ=2.5，電影演員合作網(wǎng)的γ=2.3，細(xì)胞代謝網(wǎng)的γ=2.2等等.

以WS模型為代表的小世界網(wǎng)絡(luò)模型很好地展示了小世界效應(yīng)，但現(xiàn)實(shí)系統(tǒng)中的小世界特性異常豐富，存在多樣性，遠(yuǎn)非幾個(gè)模型就可以全面地描述出來；因此，研究小世界網(wǎng)絡(luò)新的演化機(jī)制，揭示產(chǎn)生小世界效應(yīng)的多樣性和新途徑是十分有意義的.

2）從網(wǎng)絡(luò)生成的機(jī)制看，首先，復(fù)雜網(wǎng)絡(luò)的小世界效應(yīng)和冪律分布的形成是由隨機(jī)性所致，也就是新節(jié)點(diǎn)以不同的概率與系統(tǒng)中已經(jīng)存在的節(jié)點(diǎn)進(jìn)行連接. 但是隨機(jī)性并非唯一的生成機(jī)制，隨機(jī)連接對(duì)于具有固定節(jié)點(diǎn)連通度的通信網(wǎng)絡(luò)和計(jì)算機(jī)網(wǎng)絡(luò)等是不適合的；因此，研究以確定性的生成方式構(gòu)造小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)具有重要的實(shí)際應(yīng)用價(jià)值.

其次，擇優(yōu)連接機(jī)制是目前公認(rèn)的形成冪律分布的一個(gè)主要機(jī)制，但是，近年來人們提出了多種新的替代擇優(yōu)連接的機(jī)制來生成無標(biāo)度網(wǎng)絡(luò). BA模型假設(shè)擇優(yōu)連接是線性的，即連接概率與節(jié)點(diǎn)度成正比，但現(xiàn)實(shí)網(wǎng)絡(luò)也并非如此，更合理的是采用

文獻(xiàn)[11]通過對(duì)實(shí)際網(wǎng)絡(luò)的測(cè)量，發(fā)現(xiàn)有些網(wǎng)絡(luò)如因特網(wǎng)和引文網(wǎng)α≈1，基本上呈線性關(guān)系；但有些網(wǎng)絡(luò)如科學(xué)家合作網(wǎng)α≈ 0.8<1，呈亞線性關(guān)系；也有的網(wǎng)絡(luò)α>1，稱為超線性關(guān)系.

綜上所述，由于現(xiàn)實(shí)網(wǎng)絡(luò)的多樣性和復(fù)雜性，因此，對(duì)于不同的現(xiàn)實(shí)網(wǎng)絡(luò)建立具體的網(wǎng)絡(luò)模型很有必要，于是網(wǎng)絡(luò)演化一直是復(fù)雜網(wǎng)絡(luò)科學(xué)研究的一個(gè)極其重要的方向.

如何實(shí)現(xiàn)網(wǎng)絡(luò)的演化呢？人們除了通過改變擇優(yōu)連接概率公式來改進(jìn)模型之外，還可以通過網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的一些細(xì)微變化，例如加點(diǎn)、加邊、去點(diǎn)、去邊、重連邊等來形成網(wǎng)絡(luò)的演化. 研究表明：基本的細(xì)微拓?fù)浣Y(jié)構(gòu)變化都會(huì)對(duì)網(wǎng)絡(luò)的度分布等性質(zhì)產(chǎn)生一定影響，使網(wǎng)絡(luò)調(diào)整得更切合實(shí)際.近年來，國(guó)內(nèi)外學(xué)者們從不同角度出發(fā)，通過調(diào)節(jié)上述基本事件來改進(jìn)BA模型，從而形成了許多更加貼近實(shí)際的演化模型.

目前，在網(wǎng)絡(luò)的演化機(jī)理和模型建立方面仍有許多問題值得深入研究.

3.2 網(wǎng)絡(luò)加權(quán)[12-13]

目前大多數(shù)研究都是假定網(wǎng)絡(luò)模型的每條邊是完全相同的，屬于無權(quán)網(wǎng)絡(luò)，它只能給出節(jié)點(diǎn)之間相互作用存在與否的定性描述. 這種定性描述反映了節(jié)點(diǎn)之間簡(jiǎn)單連接方式和相互作用的基本信息，不能描述實(shí)際網(wǎng)絡(luò)的節(jié)點(diǎn)之間相互作用強(qiáng)度的差異，而在許多情況下，節(jié)點(diǎn)之間相互作用強(qiáng)度的差異起著至關(guān)重要的作用. 例如，互聯(lián)網(wǎng)上的帶寬、航空網(wǎng)中2個(gè)機(jī)場(chǎng)間航班的數(shù)量或者座位數(shù)，科學(xué)家合作網(wǎng)中的合作次數(shù)等都是影響系統(tǒng)性質(zhì)的重要因素. 此時(shí)，無權(quán)網(wǎng)絡(luò)的描述就有局限性了，僅用一條邊表示連接的存在與否不能準(zhǔn)確反映實(shí)際網(wǎng)絡(luò)的細(xì)致結(jié)構(gòu)及其功能，這就需要引入邊權(quán)（link weight）來刻畫相應(yīng)作用強(qiáng)度的差異性，從而形成加權(quán)網(wǎng)絡(luò)（weighted networks）.

加（含）權(quán)網(wǎng)絡(luò)定義了點(diǎn)權(quán)和邊權(quán)2個(gè)超越純拓?fù)浣Y(jié)構(gòu)的概念，分別用來表示節(jié)點(diǎn)的重要程度和節(jié)點(diǎn)之間的作用強(qiáng)度. 邊權(quán)表示的節(jié)點(diǎn)或個(gè)體之間的相互作用可以是多種多樣的，例如科學(xué)家合作網(wǎng)，邊權(quán)可以表示2個(gè)科學(xué)家合作發(fā)表了多少篇文章，在互聯(lián)網(wǎng)中可以表示2個(gè)路由器之間的信息流量等.

Yook S H等人建立了一個(gè)開創(chuàng)性的加權(quán)網(wǎng)絡(luò)模型[14]，通過簡(jiǎn)單的演化機(jī)制，該模型能夠重現(xiàn)許多真實(shí)網(wǎng)絡(luò)同時(shí)具有的點(diǎn)度、點(diǎn)權(quán)和邊權(quán)分布的冪律分布特性，并且能夠給出模型的解析理論，證明冪律指數(shù)在 2~3之間可調(diào)，這一結(jié)果與絕大部分真實(shí)網(wǎng)絡(luò)符合得很好. 但另一方面，這個(gè)模型也存在很多不足之處，不能夠顯示真實(shí)網(wǎng)絡(luò)的許多其他特性，如大的簇系數(shù)等. 為了更貼近實(shí)際，近年來，國(guó)內(nèi)外學(xué)者提出了多種加權(quán)網(wǎng)絡(luò)的演化模型，掀起了加權(quán)網(wǎng)絡(luò)的研究熱潮. 研究表明：加權(quán)網(wǎng)絡(luò)所具有的物理內(nèi)涵遠(yuǎn)遠(yuǎn)超過了無權(quán)網(wǎng)絡(luò). 把一個(gè)實(shí)際系統(tǒng)抽象為加權(quán)網(wǎng)絡(luò)的工作大致包括以下幾個(gè)方面：

1）研究邊權(quán)的賦予方式

加權(quán)網(wǎng)絡(luò)研究面對(duì)的第 1個(gè)問題就是邊權(quán)的賦予方式. 邊權(quán)代表個(gè)體間相互作用的強(qiáng)度，既有現(xiàn)實(shí)存在的物理權(quán)重，也有抽象權(quán)重. 當(dāng)實(shí)際問題中存在物理權(quán)重時(shí)，如電路網(wǎng)絡(luò)的電阻值、互網(wǎng)絡(luò)的帶寬、航空網(wǎng)絡(luò)的里程和座位數(shù)以及化學(xué)反應(yīng)網(wǎng)絡(luò)中的反應(yīng)速率等等，問題相對(duì)容易處理，直接把相關(guān)物理量看作邊權(quán)即可. 但是對(duì)于其他包含相似關(guān)系、親密程度等社會(huì)關(guān)系的網(wǎng)絡(luò)，就需要把兩點(diǎn)相互作用的某種屬性轉(zhuǎn)化為權(quán)重，尤其是當(dāng)系統(tǒng)中包含多個(gè)層次的相互作用關(guān)系的時(shí)候，就必須仔細(xì)研究其加權(quán)方式了.

2）研究加權(quán)網(wǎng)絡(luò)的演化模型

如何構(gòu)造加權(quán)網(wǎng)絡(luò)模型以再現(xiàn)無權(quán)網(wǎng)絡(luò)中所沒有的豐富的統(tǒng)計(jì)性質(zhì)，已成為加權(quán)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)演化研究的重要問題. 根據(jù)賦權(quán)方式，演化模型大致可以分為 2種類型：一種是在引入邊時(shí)就按照一定的規(guī)則為邊賦權(quán)，在以后網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的演化中邊權(quán)不再改變，將其稱為邊權(quán)固定模型；另一種是權(quán)重本身也具有演化行為，網(wǎng)絡(luò)中每一條邊的邊權(quán)都會(huì)隨著網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的演化而不斷變化，稱其為邊權(quán)演化模型.

3）研究權(quán)重對(duì)網(wǎng)絡(luò)結(jié)構(gòu)性質(zhì)的影響

無權(quán)網(wǎng)絡(luò)主要研究拓?fù)浣Y(jié)構(gòu)的變化對(duì)統(tǒng)計(jì)特性的影響. 在加權(quán)網(wǎng)絡(luò)中，我們可以通過調(diào)整權(quán)重來改變網(wǎng)絡(luò)的基本結(jié)構(gòu)性質(zhì)，包括點(diǎn)強(qiáng)度、集聚系數(shù)、平均最短路徑等統(tǒng)計(jì)特性.

4）研究加權(quán)網(wǎng)絡(luò)的動(dòng)力學(xué)行為

網(wǎng)絡(luò)動(dòng)力學(xué)研究包括網(wǎng)絡(luò)的傳播行為、網(wǎng)絡(luò)的同步現(xiàn)象等. 在加權(quán)網(wǎng)絡(luò)上，權(quán)重是制約動(dòng)力學(xué)行為的重要因素，不同的權(quán)重、不同的權(quán)分布、不同的邊—權(quán)對(duì)應(yīng)關(guān)系都會(huì)對(duì)動(dòng)力學(xué)行為的特征產(chǎn)生重要影響. 目前加權(quán)網(wǎng)絡(luò)動(dòng)力學(xué)的研究還處于萌芽階段.

3.3 網(wǎng)絡(luò)同步[15-16]

同步現(xiàn)象廣泛存在于自然、社會(huì)以及日常生活中. 關(guān)于 2個(gè)物理振子的同步現(xiàn)象的研究可以追溯到1665年荷蘭物理學(xué)家惠更斯（Huygens）對(duì)于2個(gè)掛鐘同步擺動(dòng)的有趣現(xiàn)象的觀察：兩個(gè)鐘擺不管從什么不同的初始位置出發(fā)，經(jīng)過一段時(shí)間以后它們總會(huì)趨于同步擺動(dòng). 無獨(dú)有偶，1680年荷蘭的旅行家 Kemfer在泰國(guó)湄南河上順流而下時(shí)，看到了成千上萬只螢火蟲同步閃光的一種奇特的生物現(xiàn)象：這些成群成群的螢火蟲，開始時(shí)雜亂紛紜地各自閃光，后來卻會(huì)變得時(shí)而同時(shí)閃光，時(shí)而又同時(shí)不閃光，非常有規(guī)律而且在時(shí)間上很準(zhǔn)確. 在人們的日常生活中，同步現(xiàn)象亦比比皆是. 例如，當(dāng)一場(chǎng)精彩的演出結(jié)束時(shí)，剛開始能夠聽見幾個(gè)觀眾零星的掌聲，隨后是整個(gè)劇場(chǎng)里的觀眾都一齊鼓起掌來. 整個(gè)過程中，最初的掌聲是稀疏的、零亂的、節(jié)奏不同的，但隨后經(jīng)過幾秒鐘的調(diào)整，所有的觀眾都會(huì)以一致的節(jié)奏鼓起掌來.

今天，人們?cè)谖锢?、化學(xué)、生物、工程技術(shù)以及社會(huì)經(jīng)濟(jì)等領(lǐng)域內(nèi)實(shí)現(xiàn)了同步的廣泛應(yīng)用. 例如，同步在磁共振、半導(dǎo)體激光、保密通信、組織管理的協(xié)調(diào)及高效運(yùn)行等方面都起著非常重要的作用.

然而，同步現(xiàn)象有時(shí)也會(huì)有害. 2000年6月10日當(dāng)倫敦千年橋落成時(shí)，成千上萬的市民和游客開始涌上大橋慶祝. 但是，他們雜亂無章的步伐逐漸地引起這座近700 t鋼鑄大橋開始發(fā)生振動(dòng)，橋體的擺動(dòng)偏差甚至高達(dá)20 cm. 橋上的人們開始慌亂起來，管理人員最后不得不臨時(shí)關(guān)閉了大橋. 互聯(lián)網(wǎng)上也有一些對(duì)網(wǎng)絡(luò)性能不利的同步現(xiàn)象. 例如，互聯(lián)網(wǎng)上的每一個(gè)路由器各自都要周期性地發(fā)布路由消息，盡管各個(gè)路由器都是獨(dú)立工作的，但是許多路由器最終竟然會(huì)以同步的方式發(fā)送路由消息，從而引發(fā)網(wǎng)絡(luò)交通堵塞.

復(fù)雜網(wǎng)絡(luò)作為載體展示了豐富多彩的網(wǎng)絡(luò)同步現(xiàn)象. 盡管復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)構(gòu)成各異、數(shù)目眾多，且節(jié)點(diǎn)間的耦合強(qiáng)度和耦合關(guān)系復(fù)雜，但當(dāng)大規(guī)模節(jié)點(diǎn)突然地一起運(yùn)動(dòng)或行動(dòng)就會(huì)導(dǎo)致同步現(xiàn)象的出現(xiàn). 網(wǎng)絡(luò)同步主要取決于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)的動(dòng)力因素，近年來人們對(duì)這方面進(jìn)行了較深入的研究，取得了長(zhǎng)足的進(jìn)展：

1）復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)與復(fù)雜網(wǎng)絡(luò)的同步能力之間的內(nèi)在關(guān)系

復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)對(duì)其同步性能的影響是不言而喻的. 研究發(fā)現(xiàn)：對(duì)于任何 2個(gè)節(jié)點(diǎn)之間都是直接相連的全連接網(wǎng)絡(luò)，無論耦合強(qiáng)度多大，只要網(wǎng)絡(luò)規(guī)模充分大，則一個(gè)全局耦合的網(wǎng)絡(luò)必然會(huì)產(chǎn)生同步現(xiàn)象；對(duì)于一個(gè)只有局部連接的規(guī)則網(wǎng)絡(luò)，不論2個(gè)節(jié)點(diǎn)間的連接強(qiáng)度有多大，若網(wǎng)絡(luò)充分大，則它是不可能達(dá)到同步的；對(duì)于小世界網(wǎng)絡(luò)，只要在原來規(guī)則網(wǎng)絡(luò)的基礎(chǔ)上引入少量的長(zhǎng)程連接，就能顯著改善網(wǎng)絡(luò)同步化的能力；而對(duì)無標(biāo)度網(wǎng)絡(luò)，因?yàn)榫W(wǎng)絡(luò)的非均勻特性，只有極少量的節(jié)點(diǎn)與大量節(jié)點(diǎn)相連接，而其余大部分節(jié)點(diǎn)的連接度數(shù)很低，所以無標(biāo)度網(wǎng)絡(luò)在同步意義下具有“魯棒而又脆弱”的含義. 也就是網(wǎng)絡(luò)對(duì)于隨機(jī)攻擊具有很強(qiáng)的穩(wěn)定性，同步性能不受影響，但在惡意攻擊下它的同步性能容易被破壞.

2）復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)動(dòng)力學(xué)與復(fù)雜網(wǎng)絡(luò)的同步能力之間的內(nèi)在關(guān)系

目前的研究幾乎都是假定復(fù)雜網(wǎng)絡(luò)具有相同的節(jié)點(diǎn)，即各節(jié)點(diǎn)耦合強(qiáng)度一致. 但事實(shí)上，真實(shí)復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)之間或多或少地存在一些差異，并不完全相同. 更為重要的是節(jié)點(diǎn)本身可能是一個(gè)非線性系統(tǒng)，如混沌系統(tǒng)、時(shí)空系統(tǒng)、時(shí)滯系統(tǒng)、隨機(jī)或脈沖切換系統(tǒng)等. 而節(jié)點(diǎn)動(dòng)力學(xué)性質(zhì)的復(fù)雜性問題仍然是目前一個(gè)十分具有挑戰(zhàn)性的研究課題.

3）復(fù)雜網(wǎng)絡(luò)同步能力的優(yōu)化與控制

復(fù)雜網(wǎng)絡(luò)的同步現(xiàn)象有益也有害，對(duì)于有益的同步，我們要采取各種技術(shù)手段保持或強(qiáng)化它；而對(duì)有害的同步，則要采取各種技術(shù)手段破壞它，這就是復(fù)雜網(wǎng)絡(luò)同步的控制問題. 但并非任意的控制手段都能有效地解決該問題，這受到網(wǎng)絡(luò)實(shí)際情況的制約——在網(wǎng)絡(luò)中節(jié)點(diǎn)間的耦合關(guān)系難以用統(tǒng)一的準(zhǔn)確的數(shù)值來衡量，尤其是具有海量節(jié)點(diǎn)的復(fù)雜系統(tǒng). 目前解決復(fù)雜網(wǎng)絡(luò)控制問題大致有2條思路：①利用網(wǎng)絡(luò)本身的拓?fù)浣Y(jié)構(gòu)和性質(zhì)實(shí)現(xiàn)常規(guī)的網(wǎng)絡(luò)控制. 例如，能否通過網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的微小改變，如增加、減少或者改變幾條連接邊數(shù)，來大大增強(qiáng)整個(gè)網(wǎng)絡(luò)同步控制的效果. ②對(duì)于一個(gè)給定的網(wǎng)絡(luò)，能否通過使用最簡(jiǎn)單的控制策略來控制盡可能少的網(wǎng)絡(luò)節(jié)點(diǎn)而達(dá)到最好的同步效益. 由于復(fù)雜網(wǎng)絡(luò)的一個(gè)典型特征就是擁有大量的網(wǎng)絡(luò)節(jié)點(diǎn)，從某種意義上說，我們通常不可能通過控制所有的節(jié)點(diǎn)來實(shí)現(xiàn)網(wǎng)絡(luò)同步，但是我們可能通過控制少量的關(guān)鍵節(jié)點(diǎn)來實(shí)現(xiàn)網(wǎng)絡(luò)同步，這就是復(fù)雜網(wǎng)絡(luò)的牽制控制（pining control）[17]. 例如，利用無標(biāo)度網(wǎng)絡(luò)結(jié)構(gòu)的非均勻特性，有針對(duì)地對(duì)網(wǎng)絡(luò)中的少數(shù)關(guān)鍵節(jié)點(diǎn)（集散節(jié)點(diǎn)）施加反饋牽制控制，由此牽一發(fā)而動(dòng)全身，利用節(jié)點(diǎn)之間關(guān)聯(lián)耦合的虛擬控制作用，使規(guī)模龐大的復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)能夠被鎮(zhèn)定到平衡點(diǎn)，獲得很高的控制效率. 這種通過局部控制策略而影響整個(gè)系統(tǒng)的全局群體行為的思想，曾經(jīng)在多智能體（multi-agent）控制中體現(xiàn)得淋漓盡致.

3.4 網(wǎng)絡(luò)傳播[18-20]

什么叫做復(fù)雜網(wǎng)絡(luò)的傳播現(xiàn)象？通俗地講，就是最初一個(gè)小的擾動(dòng)或一個(gè)局部的小故障，是怎么樣在網(wǎng)絡(luò)中擴(kuò)散及最終影響整個(gè)網(wǎng)絡(luò)行為的. 例如，因?yàn)榭耧L(fēng)暴雨，使得某一個(gè)地方的電線桿倒了，這就有可能在很短時(shí)間內(nèi)導(dǎo)致一片區(qū)域都斷電，造成電力網(wǎng)中的連鎖故障. 又如像艾滋病、SARS這樣的病毒，最初只有一兩個(gè)人、少數(shù)幾個(gè)人被感染，為什么會(huì)逐漸在廣大人群中傳播開來，這與我們?nèi)祟愔g的連接到底有什么關(guān)系，還有各種各樣的計(jì)算機(jī)病毒又是怎么樣在互聯(lián)網(wǎng)上蔓延的等.事實(shí)上，病毒、疾病、謠言乃至?xí)r尚在社會(huì)中的擴(kuò)散都可以看作服從某種規(guī)律的網(wǎng)絡(luò)傳播行為.

過去的數(shù)十年間，科學(xué)家致力于擴(kuò)散理論的研究. 研究結(jié)果指出：一種傳染病要在人群中傳播開來，必須要跨越某一個(gè)臨界值. 任何病毒、疾病或時(shí)尚的感染力一旦低于這個(gè)臨界值，將不可避免地自行消亡；而一旦超過臨界值，就會(huì)呈指數(shù)增長(zhǎng)，最終傳遍整個(gè)系統(tǒng). 若傳染病長(zhǎng)期存在，則必然波及大量個(gè)體. 但實(shí)證研究表明：計(jì)算機(jī)病毒、麻疹、性病等一般僅波及少數(shù)個(gè)體但能夠長(zhǎng)期存在. 這個(gè)問題在很長(zhǎng)一段時(shí)間內(nèi)一直是傳播動(dòng)力學(xué)研究的主要困惑之一.

最近，西班牙巴塞羅那加泰羅尼亞理工大學(xué)的學(xué)者 Pastor-Satorras和意大利特里雅斯特國(guó)際理論物理研究中心的學(xué)者Vespigniani研究發(fā)現(xiàn)，在無標(biāo)度網(wǎng)絡(luò)里并不存在上面所說的臨界值. 這意味著，所有病毒都可在網(wǎng)絡(luò)中傳播和長(zhǎng)期存在，即便是那些傳染力很低的病毒也是如此. 這一發(fā)現(xiàn)告訴我們，病毒或疫病在網(wǎng)絡(luò)中傳播不能用傳統(tǒng)的擴(kuò)散理論來解釋. 那么網(wǎng)絡(luò)的無標(biāo)度特性會(huì)不會(huì)是病毒或疾病傳播的原因呢？這一問題立刻引起了對(duì)無標(biāo)度網(wǎng)絡(luò)上傳播行為的研究熱潮.

許多實(shí)際網(wǎng)絡(luò)包括互聯(lián)網(wǎng)、社會(huì)關(guān)系網(wǎng)等都是無標(biāo)度網(wǎng)絡(luò). 病毒在這些網(wǎng)絡(luò)中的傳播是因?yàn)榧⒐?jié)點(diǎn)會(huì)連接到很多其他節(jié)點(diǎn)上，所以任何一個(gè)遭受病毒入侵的節(jié)點(diǎn)，都將連帶感染至少一個(gè)集散節(jié)點(diǎn)，而一旦有集散節(jié)點(diǎn)被感染，它就會(huì)把病毒傳播給眾多的其他節(jié)點(diǎn)，當(dāng)中也包括其他的集散節(jié)點(diǎn)，這就導(dǎo)致了病毒在整個(gè)網(wǎng)絡(luò)里的傳播；因此研究復(fù)雜網(wǎng)絡(luò)的傳播機(jī)理必須考慮網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)及其統(tǒng)計(jì)特征（如冪律分布）. 對(duì)于節(jié)點(diǎn)規(guī)模巨大的因特網(wǎng)，病毒正是通過連通度很高的集散節(jié)點(diǎn)（這樣的節(jié)點(diǎn)往往是重要的服務(wù)器）迅速擴(kuò)散到互聯(lián)網(wǎng)的各處，而且除非所有的主機(jī)同時(shí)使用殺毒軟件，否則病毒將會(huì)迅速蔓延. 但是在大多數(shù)情況下，對(duì)于連通度小的節(jié)點(diǎn)而言，病毒僅僅會(huì)在小范圍內(nèi)傳播，而且會(huì)較快得到抑制.

近年來，關(guān)于復(fù)雜網(wǎng)絡(luò)傳播問題的研究方興未艾，除了常見的基于WS網(wǎng)絡(luò)和BA網(wǎng)絡(luò)等通用理論模型的傳播行為研究之外，人們已經(jīng)開始關(guān)注真實(shí)網(wǎng)絡(luò)上傳播行為的實(shí)證研究，以及基于其上的傳染病模型. 其中具有代表性的是關(guān)于 Internet和 E-mail網(wǎng)絡(luò)上的計(jì)算機(jī)病毒傳播，城市社會(huì)網(wǎng)絡(luò)上的傳染病如艾滋病、非典和禽流感的傳播，以及性接觸網(wǎng)絡(luò)上的性病傳播. 科學(xué)家們還將復(fù)雜網(wǎng)絡(luò)傳播動(dòng)力學(xué)應(yīng)用于傳染病的建模、預(yù)測(cè)與免疫等方面. 所有這些研究，將有助于電腦科技工作者設(shè)計(jì)出更有效的策略保護(hù)互聯(lián)網(wǎng)免受病毒的侵害；有助于為決策者控制流行病蔓延、改善公共衛(wèi)生提供有效的手段；有助于經(jīng)濟(jì)管理人員了解公司、產(chǎn)業(yè)與經(jīng)濟(jì)之間的連接方式，為監(jiān)控與預(yù)防大規(guī)模的經(jīng)濟(jì)衰退提出有效的措施. 總之，隨著復(fù)雜網(wǎng)絡(luò)傳播動(dòng)力學(xué)的深入研究及應(yīng)用，讓人們看到了應(yīng)對(duì)病毒和傳染病威脅的曙光.

4 結(jié)語

21世紀(jì)，人類正跨入網(wǎng)絡(luò)信息時(shí)代！復(fù)雜網(wǎng)絡(luò)的發(fā)展代表了當(dāng)代科學(xué)技術(shù)發(fā)展的新潮流，復(fù)雜網(wǎng)絡(luò)的研究將成為科學(xué)研究的前沿課題和主導(dǎo)趨勢(shì)，復(fù)雜網(wǎng)絡(luò)理論是一門嶄新的交叉科學(xué)，它與數(shù)學(xué)、物理學(xué)、生物學(xué)、計(jì)算機(jī)與信息科學(xué)、系統(tǒng)科學(xué)、復(fù)雜性科學(xué)、社會(huì)科學(xué)等眾多科學(xué)交叉，引起了不同領(lǐng)域科學(xué)工作者的高度重視與廣泛參與，成為國(guó)內(nèi)外最熱門的科學(xué)之一，是一個(gè)充滿挑戰(zhàn)與機(jī)會(huì)的領(lǐng)域，前景十分美好.

[1]方錦清，汪小帆，鄭志剛，等. 一門嶄新的交叉科學(xué)：網(wǎng)絡(luò)科學(xué)（上）[J]. 物理學(xué)進(jìn)展，2007, 27(3): 239-334.

[2]吳彤. 復(fù)雜網(wǎng)絡(luò)研究及其意義[J]. 哲學(xué)研究，2004(8): 58-63.

[3]WATTS D J, STROGATZ S H. Collective dynamics of ‘Small-World’ networks[J]. Nature, 1998, 393: 440-442.

[4]BARABASI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286: 509-512.

[5]陳禹. 人類對(duì)于網(wǎng)絡(luò)的認(rèn)識(shí)的新發(fā)展[J]. 系統(tǒng)辯證學(xué)學(xué)報(bào)，2005, 13(4): 18-22.

[6]車宏安，顧基發(fā). 無標(biāo)度網(wǎng)絡(luò)及其系統(tǒng)科學(xué)意義[J]. 系統(tǒng)工程理論與實(shí)踐，2004, 4: 11-16.

[7]史定華. 網(wǎng)絡(luò)：探索復(fù)雜性的新途徑[J]. 系統(tǒng)工程學(xué)報(bào)，2005, 20(2): 115-210.

[8]BARABASI A L, BONABEAU Eric. 無標(biāo)度網(wǎng)絡(luò)[J]. 科學(xué)美國(guó)人，2003(7): 50-59.

[9]DOROGVTSEV S N, MENDES J F. Evolution of networks[J]. Advances in Physics, 2002, 51(4): 1 079-1 187.

[10]史定華，劉黎明. 演化網(wǎng)絡(luò)：模型、測(cè)度及方法[M]. 郭雷，許曉鳴. 復(fù)雜網(wǎng)絡(luò). 上海：上?？萍冀逃霭嫔?，2006.

[11]JEONG H, NDA Z, BARABASI A L. Measuring preferential attachment in evolving networks[J]. Europhys Leit, 2003, 61: 567-572.

[12]LI Menghui, FAN Ying, CHEN Jiawei, et al. Weighted networks of scientific communication: the measurement and topological role of weight[J]. Physics A, 2005, 350: 643-656.

[13]李夢(mèng)輝，樊瑛，狄增如. 加權(quán)網(wǎng)絡(luò)[M]//郭雷，許曉鳴. 復(fù)雜網(wǎng)絡(luò). 上海：上海科教出版社，2006.

[14]YOOK S H, JEONG H, BARABASI A L. Weighted evolving networks[J]. Physical Review Letters, 2001, 86: 5835-5838.

[15]WANG Xiaofan, CHEN Guanrong. Synchronization in complex dynamical networks[J]. Systems Science & Complexity, 2003, 16: 1-14.

[16]呂金虎. 復(fù)雜網(wǎng)絡(luò)的同步：理論、方法、應(yīng)用與展望[J]. 力學(xué)進(jìn)展，2008: 38(6): 713-722.

[17]WANG Xiaofan, CHEN Guanrong. Pinning control of scale-free dynamical networks[J]. Physical A, 2002, 310: 521-531.

[18]BALTHROP J, FORREST S, NEWMAN M E J, et al. Technological networks and the spread of computer 1 viruses[J]. Science, 2004, 304: 527-529.

[19]周濤，汪秉宏. 網(wǎng)絡(luò)傳播[M]//郭雷，許曉鳴. 復(fù)雜網(wǎng)絡(luò). 上海：上?？萍冀逃霭嫔纾?006.

[20]KEPHART J O, WHITE S R, CHESS D M. Computers and epidemiology[J]. IEEE Spectr, 1993, 30: 20-26.

[責(zé)任編輯：熊玉濤]

An Introduction to Complex Networks

WU Jin-pei
(Institute of Intelligence Technology and System, Wuyi University, Jiangmen 529020, China)

In recent years, research on complex networks has aroused great interests among researchers from different disciplines. This paper briefly introduces the concepts on complex networks, especially the features of small-world and scale-free networks, and proposes some key problems meriting further research.

complex networks; small-world networks; scale-free networks

TP393

A

1006-7302（2010）02-0012-01

2009-05-14 特約稿

吳今培（1937—），男，江西吉安人，教授，中南大學(xué)、北京航空航天大學(xué)博士生導(dǎo)師，研究方向：智能信息處理，E-mail: wjpwyu@163.com.