復雜網絡模型發展綜述

盛　夏

（吉林建筑大學城建學院，吉林長春130111）

復雜網絡模型發展綜述

盛夏

（吉林建筑大學城建學院，吉林長春130111）

復雜網絡是近年來新興的熱門交叉科學,本文綜述了復雜網絡的誕生和發展,介紹了復雜網絡模型的相關概念及其分類,例舉了一些具有實際意義的常見復雜網絡模型.通過近年來國內外科學家對復雜網絡的一些相關研究,展望了未來復雜網絡的一些發展方向.

復雜網絡；小世界；無標度；動力學

網絡自問世以來就受到了科學家們的關注,它是一種由數學中的圖論演變出來的新興交叉科學. 20世紀美國斥巨資建立的覆蓋整個北美大陸的巨大電力系統網絡卻因一個小事故導致紐約900萬居民經歷了25小時的大規模停電,損失達3500萬美元.其根本原因是當時人們對此類電力網絡的復雜結構認識并不夠清,不能規劃出一個可以處理個別緊急突發狀況的系統[1].由此看來,正確的認識復雜網絡,并對其進行有效的管理和利用成了人們關心的問題.

1　網絡的發展歷程

1736年,Euler Leonhard提出了著名的“歐拉圖問題”,即基于哥尼斯堡七橋問題:由4個點和7條線構成的一個圖,從任一點出發經過每條邊一次而后回到原點的回路是否存在？[2]這實際就是網絡的前身——圖.自此,圖論成為數學的一個重要分支而被廣泛的應用到各種社會科學以及自然科學等領域.從某種意義上來說,在網絡發展的初期,圖論的完善也意味著網絡科學的發展[1].

20世紀50年代末和60年代間,Erd?s和Renyi創立的正式的隨機圖論意味著網絡發展迎來了第二次標志性突破.這是一種用相對簡單的隨機圖來描述網絡的方法,簡稱ER.該理論利用圖論的閾函數、分支涌現的相變等為網絡研究提供了重要的數學基礎[2],引領了網絡研究40年之久.然而,隨機圖并不是“全能”的,生活中我們真正接觸到的各類網絡不是都能用隨機圖簡單描述清楚的.如,60億人口中任意兩個人相互認識的概率僅有6000萬分之一[1],而實際上這兩個人互相認識的幾率會遠比這個大的多.由此看來,隨機圖論并不適合描述非完全隨機的網絡.

1998年,Watts和Strogatz發表的“小世界網絡的群體動力行為”和1999年Barabási和Albert發表的“隨機網絡中標度的涌現”則標志著復雜網絡的研究進入了一個全新的時代.前者描述了從完全規則網絡到完全隨機網絡的轉變,后者則是揭示了復雜網絡連接度分布的冪律特性,發現了復雜網絡的無標度性質[2].

2　復雜網絡的一些基本知識

2.1基本概念

大部分實際系統都是由相互作用的一組基本單元構成,忽略單元的基本結構,將它們看成一個個簡單節點;同時忽略節點之間的復雜作用,將其抽象成基本單元之間的鏈接,這就構成了一個圖.

網絡可以描述成一組節點和一組邊構成的圖G,其中一個節點與邊的階梯序列u=v0e1v1e2…vn-1envn稱為G的一條路徑,v0和vn分別為起點和終點,路徑中的邊數稱為路徑“長”.節點v0和vn間最短的一條路徑稱為“最短路徑”,其長稱為“距離”.將網絡中所有節點間“距離”的平均值定義為網絡的平均路徑長度,它是衡量網絡全局性特征的量[3].

節點度指結點i的度ki表示與此節點直接相連接的邊的個數.一個圖的平均度k是網絡中所有節點的平均連接數.結點度越大的節點在網絡中越重要.度分布指一個隨機選擇的節點具有k條邊的概率,也等于網絡中度為k的結點數占網絡結點總數的比值[4].

聚類系數是描述網絡中節點之間結集程度的量.一個節點的聚類系數是它的所有鄰接節點相互間實際存在的連接數與最多可能存在的邊數的比值.將所有節點的聚類系數的平均值定義為網絡的聚類系數,它是網絡的局部特征.

2.2網絡的主要分類

依據不同網絡的動力學及統計學特性,將網絡分為規則網絡、隨機網絡和復雜網絡,其中復雜網絡又分為自相似、小世界和無標度網絡.而規則網絡和隨機網絡的特性相對單一,其研究價值不及復雜網絡.

2.2.1小世界網絡

小世界網絡既像規則網絡有較高聚類系數,又像隨機網絡有較短的平均路徑長度.從圖的角度說,就是大部分的節點不與彼此鄰接,但任一節點可以經過少數幾步到達其他節點[3].

實際網絡是極其復雜的,而非一成不變的,一些細節上的小變化可能影響到整個網絡特征的變化.適當的添加少量的長連接可以減小平均路徑長度,同時聚類系數卻不會產生很大的變化,使得一般規則網絡逐漸演變成小世界網絡.這種方法常被人為的利用,以此達到提高整個網絡工作效率的目的. WS模型和NW模型就是小世界網絡的典型例子.

2.2.2無標度網絡

在無標度網絡中,大部分節點只和少數幾個節點連接,而有些節點與非常多的節點連接,這些關鍵節點被稱為集散節點.集散節點擁有的連接可以成百上千,這也反映了網絡中邊分布的不均勻性,即無標度性.

集散節點使得網絡對意外故障的發生具有強大的承受能力,但面對協同式攻擊則顯得非常脆弱.前者如同電力系統網絡,只保護好重要的“樞紐”,那么一般小故障不會對全局造成大影響,也就不會出現開篇提到的大規模停電情況;而后者則如互聯網絡中的黑客攻擊以及病毒傳播,無差別攻擊或者傳播會造成全網癱瘓.具有代表性的無標度網絡有BA模型、BBV模型等.

3　一些常見的復雜網絡模型

3.1計算機網絡

Internet網絡可以看作是有許多計算機通過光、電纜等相互連接起來的網絡系統,其中節點是單獨的計算機或路由器,它們之間的物理連接看作邊.而運行于Internet上的萬維網也是一個復雜網絡系統,節點代表網頁,邊則是網頁之間的超文本連接,如圖1[5].

圖1　計算機網絡和WWW網絡結構示意圖

3.2交通網絡

交通網絡包括公路交通網絡、鐵路交通網絡和航空交通網絡.網絡中的節點代表車站、機場等,而邊則是連接不同站點之間的公路、鐵路和航線等.

圖2　美國高速公路和航空網絡示意圖

3.3生物網絡

將生物體內新陳代謝中所涉及的化學反應物看成節點,而把反應需要的物質之間用邊連接起來就構成了新陳代謝網絡.基因網絡是將基因看成節點,發生表達則是建立了不同基因之間的連接.生物網絡還包括蛋白質網絡、生物神經網絡、食物鏈網絡等.

3.4社會網絡

社會網絡是社會個體之間在相互接觸過程中,按照某種組織形式和聯系而形成的一個整體,包括個人之間的友誼網絡、公司之間的業務網絡等.其中節點可以是單個人或者公司,連接則是人與人之間的社會關系或公司之間的業務聯絡.演員網絡、科研合作網絡、論文的引用網絡都屬于社會網絡.

4　近年來復雜網絡的一些研究課題

4.1復雜網絡的疾病傳播

傳染病的研究是復雜網絡傳播理論的一個重要課題,包括Internet上的病毒傳播、人類社會中的SARS和艾滋病傳播等.通過對特殊疾病在給定網絡上的傳播建立合適的數學模型,研究傳染病在網絡上的傳播規律,從而給出防、病治病的方法.假設染病個體位于一個復雜網絡的節點上,傳播只能通過邊進行,而傳染效率由傳播率來決定.在均勻網絡中,存在一個傳播閾值lc,當傳染率l

4.2復雜網絡的動力學同步

同步指性質相近的動力系統間通過相互作用,使它們在不同的初始條件下演化成狀態逐步接近的動力系統,最后達到完全相同的狀態并保持穩定.隨著小世界網絡和無標度網絡的建立,對復雜網絡同步的研究也迅速發展起來,主要的研究工作包括:網絡上動力系統同步的穩定性分析,復雜網絡結構與同步能力之間的關系,提高網絡同步能力的方法,復雜網絡上動力系統的同步控制等[8].

4.3復雜網絡的控制

控制是通過有選擇地對網絡中的部分節點施加控制而使整個網絡具有期待的行為,其中研究的關鍵是控制的可行性和有效性.可行性是指復雜網絡是否可控;有效性則是盡量降低控制的代價達到控制目標的效果.2011年Liu,Barabási等基于線性系統控制理論建立了復雜網絡可控制的理論模型,發現任意控制網絡中的最有影響力的節點對整個網絡控制的影響最大[9].

4.4復雜網絡的結構識別

目前,動力網絡大多研究網絡拓撲結構已知條件下網絡動力學的控制與同步等問題,或網絡結構的各種特征參數對網絡動力學的影響.而實際模型中復雜網絡存在各種不確定的信息,往往只有部分已知網絡的結構和節點動力學,拓撲連接、耦合時滯分布等,并且在基因表達網絡、能量網絡和生物神經網絡中隨時空變化.因此動力網絡結構的識別問題有著廣泛的實際背景,它也是分析、控制和預測實際的真實網絡動力學行為的先決條件[10].

4.5復雜網絡的魯棒性

魯棒性指網絡中的部分邊或者節點被破壞時,仍能維持其功能的能力.靜態魯棒性指刪除網絡中部分節點時,不需要對節點或邊進行重新分配,仍保持功能的能力;而動態魯棒性則是當部分節點發生破壞時,網絡流需要重新分配,經過動態平衡后,仍維持功能的能力.網絡類型的不同決定了面對各種破壞的不同魯棒性,如無標度網絡對隨機破壞具有高度的魯棒性,但對于蓄意破壞網絡中度較大或者介數較大的節點網絡的魯棒性較差;而隨機網絡的容錯能力和抗毀能力則大致相同[10].

5　前景展望

前文所述,網絡的研究中涉及到了拓撲結構、混沌控制、動力學理論、統計學知識,甚至是計算機模擬等多方面的研究.而對于不同類別實例的系統了解上又體現出了多學科交叉的特點,而未來,復雜網絡的研究領域將會涵蓋的更廣.今后的一段時間的研究還會圍繞復雜網絡動力學控制以及復雜網絡的結構識別來進行,而小世界網絡和無標度網絡仍會是復雜網絡界的“寵兒”.

〔1〕Watts D J.Six degrees:The science of a connected age[M].WW Norton,2004.

〔2〕方錦清.網絡科學的誕生與發展前景[J].廣西師范大學學報:自然科學版,2007,25(3):2-6.

〔3〕WangXF,ChenG.Complexnetworks: small-world,scale-free and beyond[J].Circuits and Systems Magazine,IEEE,2003,3(1):6-20.

〔4〕劉濤,陳忠,陳曉榮.復雜網絡理論及其應用研究概述[J].系統工程,2005,23(6):1-7.

〔5〕林海.復雜網絡若干動力學問題的研究[D].廈門大學,2007.

〔6〕Pastor-SatorrasR,VespignaniA.Epidemic spreading in scale-free networks[J].Physical review letters,2001,86(14):3200-3203.

〔7〕Kitsak M,Gallos L K,Havlin S,et al.Identification of influential spreaders in complex networks[J].Nature Physics,2010,6(11):888-893.

〔8〕Zhao M,Zhou T,Wang B H,et al.Enhanced synchronizability by structural perturbations[J].Physical Review E,2005,72(5):057102.

〔9〕Liu Y Y,Slotine J J,Barabási A L.Controllability of complex networks[J].Nature,2011, 473(7346):167-173.

〔10〕汪小帆,李翔,陳關榮.復雜網絡理論及其應用[M].清華大學出版社有限公司,2006.

O175.13

A

1673-260X（2016）03-0008-03

2015-11-25