復雜網(wǎng)絡初探

吳今培

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

復雜網(wǎng)絡初探

吳今培

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

討論了復雜網(wǎng)絡的基本概念，重點介紹了小世界網(wǎng)絡和無標度網(wǎng)絡，提出了一些值得進一步研究的復雜網(wǎng)絡問題.

復雜網(wǎng)絡；小世界網(wǎng)絡；無標度網(wǎng)絡

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

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

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

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

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

1）度分布（Degree Distribution）

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

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

3）平均路徑長度（Average Path Length）

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

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

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

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

第二、標度不變性（Scale-Free）的概念

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

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

圖1 冪律度分布

圖2 雙對數(shù)坐標下冪律度分布

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

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

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

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

2.2 隨機網(wǎng)絡

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

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

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

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

圖3 泊松度分布

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

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

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

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

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

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

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

1）初始：t=0時給定m0個節(jié)點.

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

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

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

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

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

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

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

圖5 隨機網(wǎng)絡意外故障

圖6 無標度網(wǎng)絡意外故障

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

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

[2]吳彤. 復雜網(wǎng)絡研究及其意義[J]. 哲學研究，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]陳禹. 人類對于網(wǎng)絡的認識的新發(fā)展[J]. 系統(tǒng)辯證學學報，2005, 13(4): 18-22.

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

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

[8]BARABASI A L, BONABEAU Eric. 無標度網(wǎng)絡[J]. 科學美國人，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)絡：模型、測度及方法[M]. 郭雷，許曉鳴. 復雜網(wǎng)絡. 上海：上?？萍冀逃霭嫔?，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]李夢輝，樊瑛，狄增如. 加權(quán)網(wǎng)絡[M]//郭雷，許曉鳴. 復雜網(wǎng)絡. 上海：上海科教出版社，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]呂金虎. 復雜網(wǎng)絡的同步：理論、方法、應用與展望[J]. 力學進展，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)絡傳播[M]//郭雷，許曉鳴. 復雜網(wǎng)絡. 上海：上?？萍冀逃霭嫔?，2006.

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

[責任編輯：熊玉濤]

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—），男，江西吉安人，教授，中南大學、北京航空航天大學博士生導師，研究方向：智能信息處理，E-mail: wjpwyu@163.com.