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

復(fù)雜網(wǎng)絡(luò)概念復(fù)雜網(wǎng)絡(luò)含義

大量真實(shí)復(fù)雜系統(tǒng)的拓?fù)涑橄螅辉诟杏X上比規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)復(fù)雜；大量復(fù)雜系統(tǒng)得以存在的拓?fù)浠A(chǔ)。復(fù)雜網(wǎng)絡(luò)的研究歷史

哥尼斯堡七橋——>隨機(jī)圖論——>小世界和無(wú)標(biāo)度網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)研究簡(jiǎn)史格尼斯堡七橋問題Euler（1707~1783），瑞士數(shù)學(xué)家，圖論之父一筆畫問題1736年，七橋游戲2隨機(jī)圖理論

20世紀(jì)60年代，由兩位匈牙利數(shù)學(xué)家Erdǒs和Rényi建立的隨機(jī)圖理論（randomgraphtheory）被公認(rèn)為是在數(shù)學(xué)上開創(chuàng)了復(fù)雜網(wǎng)絡(luò)理論的系統(tǒng)性研究。Erdǒs和Rényi的最重要的發(fā)現(xiàn)是：ER隨機(jī)圖的許多重要性質(zhì)都是突然涌現(xiàn)的。也就是說(shuō)，對(duì)于任一給定的概率p，要么幾乎每一個(gè)圖都具有某個(gè)性質(zhì)Q（比如說(shuō)，連通性），要么幾乎每一個(gè)圖都不具有該性質(zhì)。在20世紀(jì)的后40年中，隨機(jī)圖理論一直是研究復(fù)雜網(wǎng)絡(luò)的基本理論。3小世界實(shí)驗(yàn)20世紀(jì)60年代美國(guó)哈佛大學(xué)的社會(huì)心理學(xué)家StanleyMilgram通過(guò)一些社會(huì)調(diào)查后給出的推斷是：地球上任意兩個(gè)人之間的平均距離是6。這就是著名的“六度分離”（sixdegreesofseparation）推斷。

為了檢驗(yàn)“六度分離”的正確性，小世界實(shí)驗(yàn)—Bacon數(shù)。美國(guó)Virginia大學(xué)計(jì)算機(jī)系的科學(xué)家建立了一個(gè)電影演員的數(shù)據(jù)庫(kù)，放在網(wǎng)上供人們隨意查詢。網(wǎng)站的數(shù)據(jù)庫(kù)里目前總共存有近60萬(wàn)個(gè)世界各地的演員的信息以及近30萬(wàn)部電影信息。通過(guò)簡(jiǎn)單地輸入演員名字就可以知道這個(gè)演員的Bacon數(shù)。

一個(gè)有趣的數(shù)學(xué)家故事：Erdǒs數(shù)證明小世界實(shí)驗(yàn)。4小世界實(shí)驗(yàn)---六度分離米爾格倫的實(shí)驗(yàn)過(guò)程是：他計(jì)劃通過(guò)人傳人的送信方式來(lái)統(tǒng)計(jì)人與人之間的聯(lián)系。首先把信交給志愿者A，告訴他信最終要送給收信人S。如果他不認(rèn)識(shí)S，那么就送信到某個(gè)他認(rèn)識(shí)的人B手里，理由是A認(rèn)為在他的交集圈里B是最可能認(rèn)識(shí)S的。但是如果B也不認(rèn)識(shí)S，那么B同樣把信送到他的一個(gè)朋友C手中，……，就這樣一步步最后信終于到達(dá)S那里。這樣就從A到B到C到……最后到S連成了一個(gè)鏈。斯坦利?米爾格倫就是通過(guò)對(duì)這個(gè)鏈做了統(tǒng)計(jì)后做出了六度分離的結(jié)論。然而在這個(gè)實(shí)驗(yàn)中，實(shí)際上只有三分之一的信送到了收信人那里，因此實(shí)驗(yàn)的完成率很低。小世界實(shí)驗(yàn)—六度分離我們或許有過(guò)這樣的經(jīng)歷：偶爾碰到一個(gè)陌生人，同他聊了一會(huì)后發(fā)現(xiàn)你認(rèn)識(shí)的某個(gè)人居然他也認(rèn)識(shí)，然后一起發(fā)出”這個(gè)世界真小”的感嘆。那么對(duì)于世界上任意兩個(gè)人來(lái)說(shuō)，借助第三者、第四者這樣的間接關(guān)系來(lái)建立起他們兩人的聯(lián)系平均來(lái)說(shuō)最少要通過(guò)多少人呢？美國(guó)社會(huì)心理學(xué)家斯坦利?米爾格倫(StanleyMilgram)在1967年通過(guò)一些實(shí)驗(yàn)后得出結(jié)論：中間的聯(lián)系人平均只需要5個(gè)。他把這個(gè)結(jié)論稱為“六度分離”。六度分離:平均只要通過(guò)5個(gè)人，你就能與世界任何一個(gè)角落的任何一個(gè)人發(fā)生聯(lián)系。這個(gè)結(jié)論定量地說(shuō)明了我們世界的”大小”，或者說(shuō)人與人關(guān)系的緊密程度。30多年來(lái)，六度分離理論一直被作為社會(huì)心理學(xué)的經(jīng)典范例之一。盡管如此，實(shí)際上這個(gè)理論并沒有得到嚴(yán)格的證實(shí)。美國(guó)心理學(xué)教授朱迪斯?克蘭菲爾德(JudithKleinfeld)對(duì)米爾格倫最初的實(shí)驗(yàn)提出不同意見，因?yàn)樗l(fā)現(xiàn)實(shí)驗(yàn)的完成率極低。小世界實(shí)驗(yàn)---Bacon數(shù)截止到幾天前，世界電影史上共產(chǎn)生了大約23萬(wàn)部電影，78多萬(wàn)名電影演員（參見互聯(lián)網(wǎng)電影庫(kù)

）.KavinBacon在許多部電影中飾演小角色。幾年前,Virginia大學(xué)的計(jì)算機(jī)專家BrettTjaden設(shè)計(jì)了一個(gè)游戲，他聲稱電影演員KevinBacon是電影界的中心。在游戲里定義了一個(gè)所謂的Bacon數(shù)：隨便想一個(gè)演員，如果他（她）和KavinBacon一起演過(guò)電影，那么他（她）的Bacon數(shù)就為1；如果他（她）沒有和Bacon演過(guò)電影，但是和Bacon數(shù)為1的演員一起演過(guò)電影，那么他的Bacon數(shù)就為2；依此類推。發(fā)現(xiàn):在曾經(jīng)參演的美國(guó)電影演員中，沒有一個(gè)人的Bacon數(shù)超過(guò)4。小世界實(shí)驗(yàn)---Bacon數(shù)在網(wǎng)上有一個(gè)網(wǎng)頁(yè)/oracle/。網(wǎng)站的數(shù)據(jù)庫(kù)里總共存有有783940個(gè)世界各地的演員的信息以及231,088部電影信息。通過(guò)簡(jiǎn)單地輸入演員名字就可以知道這個(gè)演員的bacon數(shù)。目前比如輸入StephenChow（周星馳）就可以得到這樣的結(jié)果：周星馳在1991年的《豪門夜宴(Haomenyeyan)》中與洪金寶(SammoHungKam-Bo)合作；而洪金寶又在李小龍的最后一部電影，即1978年的《死亡的游戲（GameofDeath）》中與ColleenCamp合作；ColleenCamp在去年的電影《Trapped》中與KevinBacon合作。這樣周星馳的Bacon數(shù)為3。對(duì)78萬(wàn)個(gè)演員所做的統(tǒng)計(jì)：演員的最大Bacon數(shù)僅僅為8，平均Bacon數(shù)僅為2.948。小世界實(shí)驗(yàn)---Erdos數(shù)PaulErdos((1913-1996)：是出生于匈牙利的猶太籍?dāng)?shù)學(xué)家，被公認(rèn)為20世紀(jì)最偉大的天才之一。Erdos畢生發(fā)表的論文超過(guò)1500篇（在數(shù)學(xué)史上僅次于歐拉(Euler

，1707-1783))，超長(zhǎng)的合作者名單,合作者超過(guò)450位。但若加上別人所做但曾獲他關(guān)鍵性提示之論文，則他的論文應(yīng)有數(shù)萬(wàn)篇。他的研究領(lǐng)域主要是數(shù)論和組合數(shù)學(xué)，但他的論文中涵蓋的學(xué)科有逼近論、初等幾何、集合論、概率論、數(shù)理邏輯、格與序代數(shù)結(jié)構(gòu)、線性代數(shù)、群論、拓?fù)淙?、多?xiàng)式、測(cè)度論、單復(fù)變函數(shù)、差分方程與函數(shù)方程、數(shù)列、Fourier分析、泛函分析、一般拓?fù)浜痛鷶?shù)拓?fù)洹⒔y(tǒng)計(jì)、數(shù)值分析、計(jì)算機(jī)科學(xué)、信息論等等。"MathematicalReviews"曾把數(shù)學(xué)劃分為大約六十個(gè)分支，Erdos的論文涉及到了其中的40%.

小世界實(shí)驗(yàn)---Erdos數(shù)Erdos從來(lái)沒有一個(gè)固定的職位，從來(lái)不定居在一個(gè)地方，也沒有結(jié)婚，帶著一半空的手提箱，穿梭于學(xué)術(shù)研討會(huì)，浪跡天涯，頗富傳奇色彩。有人稱他為流浪學(xué)者(wandering

scholar)。他效忠的是科學(xué)的皇后，

而非一特定的地方。各地都有熱心的數(shù)學(xué)家提供他舒適的食宿，安排他的一切，他則對(duì)招待他的主人，給出一些挑戰(zhàn)性的數(shù)學(xué)難題，或給予研究上的指導(dǎo)做為回饋。他可以和許多不同領(lǐng)域的數(shù)學(xué)家合作。數(shù)學(xué)家常將本身長(zhǎng)久解決不了的問題和他討論，于是很快地一篇論文便誕生了。小世界實(shí)驗(yàn)---Erdos數(shù)數(shù)學(xué)家以下述方式來(lái)定義Erdos數(shù)(Erdos

number)

:

Erdos本人之Erdos數(shù)為0，任何人若曾與Erdos合寫過(guò)論文，

則其Erdos數(shù)為1。任何人若曾與一位Erdos數(shù)為l(且不曾與有更少的Erdos數(shù))

的人合寫過(guò)論文，

則他的Erdos數(shù)為2…幾乎每一個(gè)當(dāng)代數(shù)學(xué)家都有一個(gè)有限的Erdos數(shù)，而且這個(gè)數(shù)往往非常小，小得出乎本人的預(yù)料。比如說(shuō)證明Fermat大定理的AndrewWiles，他的研究方向與Erdos相去甚遠(yuǎn)，但他的Erdos數(shù)只有3，是通過(guò)這個(gè)途徑實(shí)現(xiàn)的：Erdos--AndrewOdlyzko--ChrisM.Skinner--AndrewWiles.小世界實(shí)驗(yàn)---Erdos數(shù)

Fields獎(jiǎng)得主的Erdos數(shù)都不超過(guò)5，（只有Cohen和Grothendieck的Erdos數(shù)是5，）

Nevanlinna獎(jiǎng)得主的Erdos數(shù)不超過(guò)3，（只有Valiant的Erdos數(shù)是3）Wolf數(shù)學(xué)獎(jiǎng)得主的Erdos數(shù)不超過(guò)6，（只有V.I.Arnold是6，且只有Kolmogorov是5，）Steele獎(jiǎng)的終身成就獎(jiǎng)得主的Erdos數(shù)不超過(guò)4.在具有有限Erdos數(shù)的人名單中往往還能發(fā)現(xiàn)一些其他領(lǐng)域的專家，如:比爾蓋茲(BillGates)，他的Erdos數(shù)是4，通過(guò)如下途徑實(shí)現(xiàn)：Erdos--PavolHell--XiaoTieDeng--ChristosH.Papadimitriou--WilliamH.(Bill)Gates.愛因斯坦的Erdos數(shù)是2.

有兩篇開創(chuàng)性的文章可以看作是復(fù)雜網(wǎng)絡(luò)研究新紀(jì)元開始的標(biāo)志：

一篇是美國(guó)康奈爾（Cornell）大學(xué)理論和應(yīng)用力學(xué)系的博士生Watts及其導(dǎo)師、非線性動(dòng)力學(xué)專家Strogatz教授于1998年6月在Nature雜志上發(fā)表的題為《“小世界”網(wǎng)絡(luò)的集體動(dòng)力學(xué)》（CollectiveDynamicsof‘Small-World’Networks）的文章；另一篇是美國(guó)NotreDame大學(xué)物理系的Barabāsi教授及其博士生Albert于1999年10月在Science雜志上發(fā)表的題為《隨機(jī)網(wǎng)絡(luò)中標(biāo)度的涌現(xiàn)》（EmergenceofScalinginRandomNetworks）的文章。這兩篇文章分別揭示了復(fù)雜網(wǎng)絡(luò)的小世界特征和無(wú)標(biāo)度性質(zhì)，并建立了相應(yīng)的模型以闡述這些特性的產(chǎn)生機(jī)理。

13復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)四種結(jié)構(gòu)模型：規(guī)則網(wǎng)絡(luò)隨機(jī)網(wǎng)絡(luò)小世界網(wǎng)絡(luò)無(wú)標(biāo)度網(wǎng)絡(luò)規(guī)則網(wǎng)絡(luò)系統(tǒng)中節(jié)點(diǎn)及其與邊的關(guān)系是固定的。

（a）全局耦合網(wǎng)絡(luò)；（b）最近鄰耦合網(wǎng)絡(luò)；（c）星形網(wǎng)絡(luò)

全局耦合網(wǎng)絡(luò)具有最小的平均路徑長(zhǎng)度Lgc=1和最大的聚類系數(shù)Cgc=1；最近鄰耦合網(wǎng)絡(luò):包含N個(gè)圍成一個(gè)環(huán)的點(diǎn)，其中每個(gè)節(jié)點(diǎn)都與它左右各K/2個(gè)鄰居點(diǎn)相連（K為偶數(shù)），對(duì)于較大的K值，最近鄰耦合網(wǎng)絡(luò)的聚類系數(shù)為因此，這樣的網(wǎng)絡(luò)是高度聚類的。對(duì)于固定的K值，網(wǎng)絡(luò)平均路徑長(zhǎng)度為

星形耦合網(wǎng)絡(luò)：有一個(gè)中心點(diǎn)，其余N-1個(gè)點(diǎn)都只與這個(gè)中心點(diǎn)連接，其平均路徑長(zhǎng)度為

聚類系數(shù)為

隨機(jī)圖隨機(jī)圖是與規(guī)則網(wǎng)絡(luò)相反的網(wǎng)絡(luò)，一個(gè)典型模型是Erdos和Renyi于40多年前開始研究的隨機(jī)圖模型。假設(shè)有大量的紐扣（N》1）散落在地上，并以相同的概率p給每對(duì)紐扣系上一根線。這樣就會(huì)得到一個(gè)有N個(gè)節(jié)點(diǎn)，約pN(N-1)/2條邊的ER隨機(jī)圖的實(shí)例。1998，Watts和Strogatz：WS小世界網(wǎng)絡(luò)D.J.Watts,andS.H.Strogatz,Nature,393,440-442(1998).18C(p):平均聚集系數(shù)

L(p):平均最短路徑WS小世界模型NW小世界模型小世界網(wǎng)絡(luò)作為從完全規(guī)則網(wǎng)絡(luò)向完全隨機(jī)圖的過(guò)渡，Watts和Strogtz于1998年引入了一個(gè)小世界網(wǎng)絡(luò)模型，稱為WS小世界模型。其構(gòu)造算法如下：①?gòu)囊?guī)則圖開始：考慮一個(gè)含有N個(gè)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)，它們圍成一個(gè)環(huán)，其中每個(gè)節(jié)點(diǎn)都與它左右相鄰的各K/2個(gè)節(jié)點(diǎn)相連，K是偶數(shù)。②隨機(jī)化重連：以概率p隨機(jī)地重連網(wǎng)絡(luò)中的每個(gè)邊，即將邊的一個(gè)端點(diǎn)保持不變，而另一個(gè)端點(diǎn)取為網(wǎng)絡(luò)中隨機(jī)選擇的一個(gè)節(jié)點(diǎn)。其中規(guī)定，任意兩個(gè)不同節(jié)點(diǎn)之-間至多只能有一條邊，并且每一個(gè)節(jié)點(diǎn)都不能有邊與自身相連。P=0對(duì)應(yīng)于完全規(guī)則網(wǎng)絡(luò)，p=1對(duì)應(yīng)于完全隨機(jī)網(wǎng)絡(luò)。小世界網(wǎng)絡(luò)具有較短的平均路徑長(zhǎng)度又具有較高的聚類系數(shù)的網(wǎng)絡(luò)就稱為小世界網(wǎng)絡(luò)。

Newman和Watts提出了NW小世界模型，用“隨機(jī)化加邊”取代WS小世界模型構(gòu)造中的“隨機(jī)化重連”。算法如下：①?gòu)囊?guī)則圖開始：含有N個(gè)節(jié)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)。②隨機(jī)化加邊：以概率P在隨機(jī)選取的一對(duì)節(jié)點(diǎn)之間加上一條邊。

NW小世界模型中，p=0對(duì)應(yīng)于原來(lái)的最近鄰耦合網(wǎng)絡(luò)，p=1對(duì)應(yīng)于全局耦合網(wǎng)絡(luò)。無(wú)標(biāo)度網(wǎng)絡(luò)模型

研究發(fā)現(xiàn)許多復(fù)雜網(wǎng)絡(luò)的連接度分布函數(shù)具有冪律形式，由于這類網(wǎng)絡(luò)的節(jié)點(diǎn)的連接度沒有明顯的特征長(zhǎng)度，故稱為無(wú)標(biāo)度網(wǎng)絡(luò)。

Barabasi和Albert提出了一個(gè)無(wú)標(biāo)度網(wǎng)絡(luò)模型，稱為BA模型。該模型考慮到了實(shí)際網(wǎng)絡(luò)的兩個(gè)重要特性：①增長(zhǎng)特性；②優(yōu)先連接特性?；谶@兩個(gè)特性，BA無(wú)標(biāo)度網(wǎng)絡(luò)模型構(gòu)造算法如下：①增長(zhǎng)：從一個(gè)具有m0個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)開始，每次引入一個(gè)新的節(jié)點(diǎn)，并且連到m個(gè)已存在的節(jié)點(diǎn)上，這里。②優(yōu)先連接：一個(gè)新節(jié)點(diǎn)與一個(gè)已經(jīng)存在的節(jié)點(diǎn)i相連接的概率與節(jié)點(diǎn)i的度ki，節(jié)點(diǎn)j的度kj之間滿足如下關(guān)系：

冪律分布函數(shù)的無(wú)標(biāo)度性質(zhì)：考慮一個(gè)概率分