復(fù)雜網(wǎng)絡(luò)的基本概念、模型及應(yīng)用

復(fù)雜網(wǎng)絡(luò)的基本概念、模型及應(yīng)用

一、復(fù)雜網(wǎng)絡(luò)的基本概念前面我們?cè)凇抖嘀黧w建模和智能優(yōu)化算法》一文中,介紹過實(shí)際網(wǎng)絡(luò),有了這些實(shí)際網(wǎng)絡(luò)，我們就要對(duì)它進(jìn)行研究。在研究之前，我們必須把它抽象成可以用數(shù)學(xué)進(jìn)行描述的問題，即復(fù)雜網(wǎng)絡(luò)。1.復(fù)雜網(wǎng)絡(luò)的數(shù)學(xué)描述網(wǎng)絡(luò)G=（V,E），由點(diǎn)集V（G）和邊集E（G）組成的一個(gè)圖，可分為無向、有向和加權(quán)網(wǎng)絡(luò)。令ei∈E（G），每條邊ei有V（G）中的一對(duì)點(diǎn)(u,v)與之對(duì)應(yīng)；如果任意(u,v)與(v,u)對(duì)應(yīng)同一條邊，則稱為無向網(wǎng)絡(luò)，否則為有向網(wǎng)絡(luò)；如果任意∣ei∣=1，則稱為無權(quán)網(wǎng)絡(luò)，否則為加權(quán)網(wǎng)絡(luò)。2.無向網(wǎng)絡(luò)無向網(wǎng)絡(luò)是最簡(jiǎn)單的網(wǎng)絡(luò)類型，它節(jié)點(diǎn)跟節(jié)點(diǎn)之間的連邊只表示連接關(guān)系，無方向的概念，如圖1所示。

圖1無向網(wǎng)絡(luò)的鄰接矩陣無向網(wǎng)絡(luò)由節(jié)點(diǎn)和連邊構(gòu)成，我們把節(jié)點(diǎn)和連邊用矩陣進(jìn)行刻畫。圖1展示了一個(gè)非常小的網(wǎng)絡(luò)，把它寫成矩陣的形式，實(shí)際上是一個(gè)4×4的矩陣，由于節(jié)點(diǎn)1和節(jié)點(diǎn)4之間有連邊，我們把矩陣中（1,4）這個(gè)地方記為1；節(jié)點(diǎn)2和節(jié)點(diǎn)4有連接，那么第二行第四列我們記為1；節(jié)點(diǎn)3和節(jié)點(diǎn)4是有連接，那么第三行第四列記為1；節(jié)點(diǎn)4和節(jié)點(diǎn)1、2、3都有連接，所以第四行的第1、2、3列都記為1，其他地方是0。這個(gè)矩陣就把一個(gè)網(wǎng)絡(luò)的信息全部記錄下來了，通過數(shù)學(xué)語言對(duì)網(wǎng)絡(luò)進(jìn)行了抽象。對(duì)于無向網(wǎng)絡(luò)，實(shí)際上我們可以對(duì)應(yīng)的把它做一些調(diào)整，就可以模擬很多現(xiàn)實(shí)中的網(wǎng)絡(luò)。3.有向網(wǎng)絡(luò)有向網(wǎng)絡(luò)是另外一類復(fù)雜網(wǎng)絡(luò)。例如微博，在微博網(wǎng)絡(luò)中，每一個(gè)節(jié)點(diǎn)是一個(gè)微博用戶，節(jié)點(diǎn)跟節(jié)點(diǎn)之間的連邊表示“關(guān)注”關(guān)系，由于我粉你，但你不一定粉我，所以連接關(guān)系是有向的。同樣的，還有引文網(wǎng)絡(luò)，在引文網(wǎng)絡(luò)里每一個(gè)點(diǎn)是一篇文章，文章跟文章之間的引用關(guān)系是有向的，我引用你，你不一定引用我，所以這是有向網(wǎng)絡(luò)。對(duì)于有向網(wǎng)絡(luò)，我們把它抽象成矩陣的形式進(jìn)行描述。但是，有向網(wǎng)絡(luò)與無向網(wǎng)絡(luò)在矩陣層面上的最大區(qū)別在于無向網(wǎng)絡(luò)的矩陣一定是對(duì)稱的，有向網(wǎng)絡(luò)的矩陣不一定是對(duì)稱的。4.加權(quán)網(wǎng)絡(luò)加權(quán)網(wǎng)絡(luò)是更復(fù)雜的網(wǎng)絡(luò)。我們?cè)趯?shí)際網(wǎng)絡(luò)（社交網(wǎng)絡(luò)）中提到科學(xué)家跟科學(xué)家之間的合作可以抽象成復(fù)雜網(wǎng)絡(luò)，但其中的連邊可以表示科學(xué)家跟科學(xué)家的合作次數(shù)。在矩陣中，每一行每一列的元素表示合作次數(shù)，即數(shù)值不一定僅記為1和0，數(shù)值大小代表權(quán)重。因此，不同類型的復(fù)雜網(wǎng)絡(luò)都可以通過數(shù)學(xué)語言抽象的矩陣來進(jìn)行刻畫。5.二分網(wǎng)絡(luò)后面我們?cè)诮榻B關(guān)于信息挖掘部分會(huì)涉及到一個(gè)與之前介紹過的不同的網(wǎng)絡(luò)，二分網(wǎng)絡(luò)。如圖2所示，二分網(wǎng)絡(luò)是由兩類的節(jié)點(diǎn)來構(gòu)成的，它可以刻畫很多在線系統(tǒng)。在線系統(tǒng)里面，一類節(jié)點(diǎn)表示“用戶”，另外一類節(jié)點(diǎn)表示“商品”，或者是電影、視頻等等。在二分網(wǎng)絡(luò)中，連邊存在于兩類的節(jié)點(diǎn)之間，同類節(jié)點(diǎn)之間沒有連邊。它可以幫助刻畫在線用戶的行為，例如購(gòu)物，你在淘寶上買了一個(gè)東西，那么你就作為一個(gè)“用戶”節(jié)點(diǎn)，你購(gòu)買的東西是“商品”節(jié)點(diǎn)，然后把這兩個(gè)節(jié)點(diǎn)之間連一條邊。二分網(wǎng)絡(luò)能抽象用戶的在線行為，對(duì)應(yīng)的鄰接矩陣與前文介紹的網(wǎng)絡(luò)的鄰接矩陣有所不同，它不再是一個(gè)方陣。前文介紹的網(wǎng)絡(luò)的鄰接矩陣一定是方陣，因?yàn)闄M軸縱軸對(duì)應(yīng)同一類節(jié)點(diǎn)，而二分網(wǎng)絡(luò)對(duì)應(yīng)的鄰接矩陣，它是n×m，n是“用戶”節(jié)點(diǎn)，m是“產(chǎn)品”節(jié)點(diǎn)。如果n和m不相等，這就不是一個(gè)方陣。如果1號(hào)用戶購(gòu)買了5號(hào)產(chǎn)品，就在（1，5）處記為1；如果沒有購(gòu)買這個(gè)產(chǎn)品，就在相應(yīng)處記為0。

圖2二分網(wǎng)絡(luò)

6.多層網(wǎng)絡(luò)還有一類最近研究比較多的網(wǎng)絡(luò)，多層網(wǎng)絡(luò)。多層網(wǎng)絡(luò)是更復(fù)雜的系統(tǒng)。例如航空系統(tǒng)就可以抽象成多層網(wǎng)絡(luò)。我們知道很多國(guó)家都有自己的航空公司，每家航空公司都有自己的航線。一家航空公司就可以形成一個(gè)自己公司內(nèi)部的航空網(wǎng)絡(luò)。我們把若干家航空公司的內(nèi)部網(wǎng)絡(luò)重疊（不一定是疊加），就可以用多層網(wǎng)絡(luò)來構(gòu)建一個(gè)航空系統(tǒng)。理論上，多層網(wǎng)絡(luò)有多種刻畫方式，例如用大矩陣刻畫，把節(jié)點(diǎn)抽象成大矩陣?yán)锩娴男辛?，也可以抽象成很多小矩陣，例如圖3中有5個(gè)小矩陣，但因?yàn)橛袝r(shí)層與層之間會(huì)有連接，所以需要更多的矩陣去刻畫一個(gè)多層網(wǎng)絡(luò)。

圖3多層網(wǎng)絡(luò)7.度與度分布復(fù)雜網(wǎng)絡(luò)中有一個(gè)經(jīng)典的概念——度，用于衡量節(jié)點(diǎn)的連邊數(shù)，即一個(gè)節(jié)點(diǎn)有多少條連邊，我們就定義它的度是多少。例如一個(gè)節(jié)點(diǎn)有3條連邊，它的度就是3。網(wǎng)絡(luò)中，節(jié)點(diǎn)在不同度值上的分布稱為度分布。我們通常用度分布的頻數(shù)統(tǒng)計(jì)圖展現(xiàn)網(wǎng)絡(luò)中節(jié)點(diǎn)的連邊數(shù)的分布情況。二、復(fù)雜網(wǎng)絡(luò)基本模型我們從最原始的研究開始介紹復(fù)雜網(wǎng)絡(luò)的基本模型。復(fù)雜網(wǎng)絡(luò)起源于1998年和1999年在《Nature》和《Science》雜志中的兩篇文章，分別提出了小世界網(wǎng)絡(luò)模型和無標(biāo)度網(wǎng)絡(luò)模型，推動(dòng)了復(fù)雜網(wǎng)絡(luò)領(lǐng)域近20年的發(fā)展。1.規(guī)則網(wǎng)絡(luò)與隨機(jī)網(wǎng)絡(luò)最早在物理學(xué)領(lǐng)域的研究中應(yīng)用較多的網(wǎng)絡(luò)模型是規(guī)則網(wǎng)絡(luò)，例如晶格網(wǎng)絡(luò)。與規(guī)則網(wǎng)絡(luò)相對(duì)的是隨機(jī)網(wǎng)絡(luò)，在圖論中關(guān)于隨機(jī)網(wǎng)絡(luò)的研究比較多，任意兩個(gè)節(jié)點(diǎn)之間以一定概率隨機(jī)連接，就會(huì)形成隨機(jī)網(wǎng)絡(luò)。這兩類網(wǎng)絡(luò)在很多傳統(tǒng)科學(xué)研究中較為常見，但是當(dāng)現(xiàn)實(shí)的數(shù)據(jù)收集越來越多時(shí)，人們發(fā)現(xiàn)這兩類傳統(tǒng)的網(wǎng)絡(luò)模型對(duì)現(xiàn)實(shí)中網(wǎng)絡(luò)的刻畫能力越來越差，直到上世紀(jì)90年代末小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)模型的提出。2.小世界網(wǎng)絡(luò)及六度分離小世界網(wǎng)絡(luò)模型描述的對(duì)象是社交網(wǎng)絡(luò)。社交網(wǎng)絡(luò)有兩個(gè)特點(diǎn)是傳統(tǒng)模型無法刻畫的，一是有比較大的集聚系數(shù)，二是最短路徑非常小。集聚系數(shù)指一個(gè)節(jié)點(diǎn)直接相連的其他節(jié)點(diǎn)（下文稱為“鄰居”）之間的連邊數(shù)。如果“鄰居”之間連接非常緊密，那么這個(gè)節(jié)點(diǎn)的集聚系數(shù)就比較大。在社交網(wǎng)絡(luò)中這一現(xiàn)象非常普遍，例如一個(gè)人的朋友之間相互認(rèn)識(shí)的可能性是很大的，他們之間很可能也是朋友。另外，在復(fù)雜性科學(xué)中有一個(gè)概念叫六度分離理論。六度分離理論指在這個(gè)世界上，看似沒有關(guān)系的任意兩個(gè)人都可以通過六步左右的路徑連接在一起。例如一個(gè)股票專家做過一個(gè)實(shí)驗(yàn)，將一封有關(guān)股票信息的電子郵件發(fā)送給一個(gè)陌生人，并要求他把電子郵件轉(zhuǎn)發(fā)給一個(gè)愛炒股的人,當(dāng)這封電子郵件第六次轉(zhuǎn)發(fā)時(shí)，竟然又轉(zhuǎn)發(fā)到股票專家手中。經(jīng)過無數(shù)次實(shí)驗(yàn)結(jié)果相同,所以得出初步結(jié)論：任何兩個(gè)陌生人之間，可以通過六個(gè)人來建立聯(lián)系。我們可以通過有限的步驟把由70多億人組成的社交網(wǎng)絡(luò)中任意兩個(gè)點(diǎn)通過非常短的步驟連接在一起，這就是非常小的最短路徑特點(diǎn)。但是這兩個(gè)特點(diǎn)在規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)里都不能被體現(xiàn)。例如，規(guī)則網(wǎng)絡(luò)的集聚性特別高，但是最短路徑可能很大；而隨機(jī)網(wǎng)絡(luò)因?yàn)檫B邊隨機(jī)，所以隨機(jī)選取兩個(gè)點(diǎn)，它們能以非常短的距離連接，但它的集聚性不高，我們?nèi)我膺x取一個(gè)點(diǎn)會(huì)發(fā)現(xiàn)它的鄰居之間往往連邊很少。所以，規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)僅僅分別刻畫了社交網(wǎng)絡(luò)兩個(gè)特點(diǎn)之一。1998年發(fā)表在《Nature》期刊的一篇文章通過非常簡(jiǎn)單的模型把社交網(wǎng)絡(luò)的兩個(gè)特點(diǎn)呈現(xiàn)出來了，即這一模型既有規(guī)則網(wǎng)絡(luò)的高集聚性，又有隨機(jī)網(wǎng)絡(luò)小的最短路徑特點(diǎn)。在規(guī)則網(wǎng)絡(luò)的基礎(chǔ)上，引入一個(gè)非常小的概率

，對(duì)原有的一條連邊以概率

剪斷，然后隨機(jī)在網(wǎng)絡(luò)里選取兩個(gè)節(jié)點(diǎn)連接在一起。當(dāng)

時(shí)，任意一條連邊都不會(huì)重新連接，即規(guī)則網(wǎng)絡(luò)；如果

，每一條連邊都會(huì)以100%的概率被剪斷，然后重新連接到網(wǎng)絡(luò)里的任意兩個(gè)點(diǎn)，這樣的一個(gè)極端情況就是隨機(jī)網(wǎng)絡(luò)；當(dāng)

時(shí)，網(wǎng)絡(luò)不但能保證原網(wǎng)絡(luò)比較高的集聚性，而且因?yàn)榧魯嗔松倭康倪B邊使之重連，所以能出現(xiàn)一些長(zhǎng)連邊，從而有效地縮短了整個(gè)網(wǎng)絡(luò)的最短路徑。由此看出，小世界網(wǎng)絡(luò)提出了一種能夠更好重現(xiàn)社交網(wǎng)絡(luò)的模型。

圖4規(guī)則網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)、隨機(jī)網(wǎng)絡(luò)3.無標(biāo)度網(wǎng)絡(luò)及網(wǎng)絡(luò)增長(zhǎng)1999年《Science》期刊上發(fā)表的另外一篇文章認(rèn)為，雖然小世界網(wǎng)絡(luò)模型能夠很好地重現(xiàn)社交網(wǎng)絡(luò)，但是社交網(wǎng)絡(luò)另一個(gè)非常重要的特點(diǎn)被小世界網(wǎng)絡(luò)忽略了。眾所周知，實(shí)際網(wǎng)絡(luò)是隨時(shí)間不斷增長(zhǎng)的，例如引文網(wǎng)絡(luò)和微博網(wǎng)絡(luò)，因?yàn)橛行碌奈恼卤话l(fā)表，有新的用戶使用微博；社交網(wǎng)絡(luò)也是隨時(shí)間不斷增長(zhǎng)的，但是小世界網(wǎng)絡(luò)它的節(jié)點(diǎn)數(shù)是固定的。為了重現(xiàn)這一特點(diǎn)，文章提出了一個(gè)增長(zhǎng)網(wǎng)絡(luò)的模型，首先有若干個(gè)初始節(jié)點(diǎn)，然后每一步都會(huì)有新的節(jié)點(diǎn)加入，而這個(gè)新的節(jié)點(diǎn)會(huì)與一些老的節(jié)點(diǎn)相連，演化結(jié)束以后，會(huì)得到一個(gè)網(wǎng)絡(luò)，我們稱之為無標(biāo)度網(wǎng)絡(luò)。這個(gè)網(wǎng)絡(luò)有一個(gè)性質(zhì)是小世界網(wǎng)絡(luò)無法重現(xiàn)的，即實(shí)際網(wǎng)絡(luò)中廣泛地觀測(cè)到的度不均勻的現(xiàn)象。例如在微博網(wǎng)絡(luò)里，少數(shù)的大V有很多的粉絲，而大多數(shù)普通用戶就可能只有二三十個(gè)粉絲，這種不均勻性是小世界網(wǎng)絡(luò)無法刻畫的。再例如引文網(wǎng)絡(luò)中，一些文章的被引用次數(shù)是非常多的，成千上萬，但是絕大多數(shù)文章的被引用次數(shù)都非常少，而這樣一個(gè)增長(zhǎng)網(wǎng)絡(luò)刻畫的就是這一現(xiàn)象。因?yàn)槊恳粋€(gè)節(jié)點(diǎn)進(jìn)入的時(shí)候只能連比它更老的節(jié)點(diǎn)，這使得老的節(jié)點(diǎn)會(huì)有更長(zhǎng)的時(shí)間去積累連邊，所以在這個(gè)網(wǎng)絡(luò)里，大量新的節(jié)點(diǎn)的連邊數(shù)都比較少，若干個(gè)老的節(jié)點(diǎn)的連邊數(shù)會(huì)非常多。這個(gè)網(wǎng)絡(luò)模型解釋了實(shí)際網(wǎng)絡(luò)里的“二八”效應(yīng)，20%的點(diǎn)占了80%的連邊數(shù)。這兩篇文章讓人們發(fā)現(xiàn)，實(shí)際網(wǎng)絡(luò)有很多特點(diǎn)是傳統(tǒng)的網(wǎng)絡(luò)模型無法刻畫的。除小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)模型之外，還有哪些實(shí)際網(wǎng)絡(luò)的特性未被發(fā)現(xiàn)，所以近年來涌現(xiàn)了一大批的對(duì)于實(shí)際網(wǎng)絡(luò)進(jìn)行建模的文章，提出的模型也是千差萬別。小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)度分布如圖5和圖6所示（p是連接概率）。我們發(fā)現(xiàn)，小世界網(wǎng)絡(luò)的度分布接近于正態(tài)分布，而且橫軸基本上是同一數(shù)量級(jí)的（10的1次方）。小世界網(wǎng)絡(luò)節(jié)點(diǎn)的度值差別不大。而無標(biāo)度網(wǎng)絡(luò)的度分布頻數(shù)統(tǒng)計(jì)圖中（橫軸是節(jié)點(diǎn)的度，縱軸是該度值的節(jié)點(diǎn)數(shù)在網(wǎng)絡(luò)里面所有節(jié)點(diǎn)所占的比例），有很大比例的點(diǎn)的度非常小（10的1次方，10的0次方），有少量的點(diǎn)的連邊數(shù)極其多，數(shù)量能達(dá)到10的2次方，10的3次方，所以無標(biāo)度網(wǎng)絡(luò)展現(xiàn)了節(jié)點(diǎn)度分布極度不均勻的特點(diǎn)，其中大量的點(diǎn)是小度節(jié)點(diǎn)，有少量的節(jié)點(diǎn)的連邊數(shù)特別多，而這種分布被稱為冪律分布（在頻數(shù)統(tǒng)計(jì)圖上坐標(biāo)軸取雙對(duì)數(shù)，圖像是一條直線）。

圖5小世界網(wǎng)絡(luò)的度分布

圖6無標(biāo)度網(wǎng)絡(luò)的度分布三、復(fù)雜網(wǎng)絡(luò)在解決實(shí)際問題中的應(yīng)用1.網(wǎng)絡(luò)的魯棒性當(dāng)出現(xiàn)擾動(dòng)時(shí)，我們需要評(píng)價(jià)網(wǎng)絡(luò)的受損程度，如果網(wǎng)絡(luò)的受損程度小，系統(tǒng)還能正常運(yùn)行，我們就稱這個(gè)網(wǎng)絡(luò)具有魯棒性。網(wǎng)絡(luò)的魯棒性涉及到滲流理論，關(guān)注的是網(wǎng)絡(luò)中的最大連通集團(tuán)。很多實(shí)際網(wǎng)絡(luò)并不是全連通的，但會(huì)有一個(gè)最大的連通集團(tuán)，其他節(jié)點(diǎn)散布在最大連通集團(tuán)周圍。最大連通集團(tuán)非常重要，肩負(fù)著網(wǎng)絡(luò)里面的很多功能，例如在航空網(wǎng)絡(luò)里，如果一個(gè)點(diǎn)不在最大連通集團(tuán)之內(nèi)，這個(gè)點(diǎn)的航班無法到達(dá)很多其他的空港；在神經(jīng)網(wǎng)絡(luò)里，連通的神經(jīng)元之間才能傳遞信息；在電力網(wǎng)絡(luò)里，網(wǎng)絡(luò)須有較好的連通性才能給一個(gè)點(diǎn)供電。因此，為確保網(wǎng)絡(luò)的魯棒性，應(yīng)該保護(hù)網(wǎng)絡(luò)中的最大連通集團(tuán)。實(shí)際網(wǎng)絡(luò)的特點(diǎn)是有大量的節(jié)點(diǎn)連邊數(shù)特別少，但是有少量的節(jié)點(diǎn)連邊數(shù)特別多。我們以航空網(wǎng)絡(luò)為例，航空網(wǎng)絡(luò)受到外界的干擾，如果是自然災(zāi)害影響，因?yàn)樽匀粸?zāi)害一般沒有目的性，大多是天氣導(dǎo)致的，它可能會(huì)影響到某一些空港，使得空港的飛機(jī)無法起飛。在這種隨機(jī)影響下，整個(gè)網(wǎng)絡(luò)的功能性到底能有多大的保持？那么發(fā)現(xiàn)在這樣的網(wǎng)絡(luò)里面，我們將受到災(zāi)害影響的節(jié)點(diǎn)從航空網(wǎng)絡(luò)里去掉，因?yàn)榻^大多數(shù)的節(jié)點(diǎn)度值都很小而整個(gè)網(wǎng)絡(luò)的最大連通集團(tuán)還比較大，所以航空網(wǎng)絡(luò)對(duì)于這種隨機(jī)干擾，它的魯棒性很高，對(duì)災(zāi)害的敏感性不那么強(qiáng)；但是如果是外界蓄意攻擊，例如一個(gè)恐怖組織計(jì)劃破壞航空系統(tǒng)，必然不是隨機(jī)選取一個(gè)空港進(jìn)行攻擊，而是攻擊網(wǎng)絡(luò)的中樞——最繁忙的機(jī)場(chǎng)。我們把這個(gè)機(jī)場(chǎng)從網(wǎng)絡(luò)中刪掉，最后發(fā)現(xiàn)網(wǎng)絡(luò)的最大連通集團(tuán)變得特別小，使很多空港的飛機(jī)都無法與其他空港連接。大量的實(shí)際網(wǎng)絡(luò)都是由這樣的結(jié)構(gòu)所刻畫的，而這樣的結(jié)構(gòu)的魯棒性和脆弱性是共存的。因?yàn)榫W(wǎng)絡(luò)中有大量的點(diǎn)都是小度值的，所以隨機(jī)擾動(dòng)并不能影響這個(gè)系統(tǒng)的運(yùn)轉(zhuǎn)，但是對(duì)于蓄意攻擊，網(wǎng)絡(luò)是非常敏感的。2.網(wǎng)絡(luò)擁堵交通擁堵是大城市病之一。我們對(duì)交通進(jìn)行建模，評(píng)價(jià)交通的運(yùn)行狀況，評(píng)價(jià)交通網(wǎng)絡(luò)的設(shè)計(jì)是否合理，會(huì)不會(huì)造成大范圍的擁堵。例如將北京的道路抽象成網(wǎng)絡(luò)的形式，每一個(gè)節(jié)點(diǎn)表示一個(gè)路口，每一條邊表示路口與路口之間的道路。復(fù)雜網(wǎng)絡(luò)中有一個(gè)衡量節(jié)點(diǎn)重要性的指標(biāo)叫做介數(shù)，表示通過一個(gè)點(diǎn)連接網(wǎng)絡(luò)中任意兩點(diǎn)最短路徑的數(shù)量，如果通過的最短路徑數(shù)量很多，那么這個(gè)點(diǎn)的介數(shù)就大。我們把道路系統(tǒng)抽象成網(wǎng)絡(luò)后，就可以計(jì)算網(wǎng)絡(luò)中每一個(gè)點(diǎn)的介數(shù)。那么我們可以列出介數(shù)很大的若干個(gè)點(diǎn)，它們擔(dān)負(fù)著若干個(gè)集團(tuán)之間相互溝通的任務(wù)。如果一個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)介數(shù)分布非常均勻，那么整個(gè)系統(tǒng)的交通流就被平均分擔(dān)到了各個(gè)路口，一般不會(huì)出現(xiàn)大量的擁堵。但是如果有若干個(gè)點(diǎn)的介數(shù)特別高，就說明這個(gè)路網(wǎng)的設(shè)計(jì)不太穩(wěn)健，一般會(huì)造成這個(gè)點(diǎn)上的擁堵。如果需要評(píng)價(jià)一個(gè)網(wǎng)絡(luò)可能出現(xiàn)的擁堵情況，我們就可以觀察節(jié)點(diǎn)中最大的介數(shù)，如果最大的介數(shù)都比較小，網(wǎng)絡(luò)的交通流分布就不會(huì)特別集中在若干個(gè)節(jié)點(diǎn)上，發(fā)生擁堵的可能性就小。我們以一個(gè)實(shí)例來說明上述的方法。如圖7所示，我們把北京西站附近的路網(wǎng)抽象為復(fù)雜網(wǎng)絡(luò)，每一個(gè)路口抽象為一個(gè)點(diǎn)，路口與路口之間的道路抽象為一條連邊。攝像頭可以記錄道路上的交通情況。圖中道路的顏色不是表示車的數(shù)量，而是表示車流的速度。電子地圖中的實(shí)時(shí)路況信息，顏色為紅色并不表示車多，而是表示道路上車速比較慢。在網(wǎng)絡(luò)建模并獲得了實(shí)際數(shù)據(jù)之后，我們就觀察每條道路的車流速度，車流速度慢就標(biāo)為紅色，車流速度快就標(biāo)為綠色。當(dāng)然在不同的時(shí)間情況會(huì)不同，9點(diǎn)的時(shí)候紅色的道路就特別多，12點(diǎn)的時(shí)候紅色的道路就特別少。我們把網(wǎng)絡(luò)里紅的連邊刪掉，然后觀察網(wǎng)絡(luò)的連通集團(tuán)到底會(huì)發(fā)生什么變化。當(dāng)然，刪去的連邊越多，網(wǎng)絡(luò)的連通性就越差。

圖7北京西站附近的交通圖

圖8最大連通集團(tuán)的變化為什么我們要關(guān)注網(wǎng)絡(luò)的連通性？因?yàn)樵诮煌ňW(wǎng)絡(luò)里，如果刪去若干條連邊后，一個(gè)點(diǎn)和別的點(diǎn)無法連在一起，在現(xiàn)實(shí)中你就永遠(yuǎn)到不了上班的地方。把這些特別擁堵的連邊從網(wǎng)絡(luò)里刪掉，因?yàn)檫@些道路擁堵了，你無法通過，就堵在路上了。如圖8，我們發(fā)現(xiàn)網(wǎng)絡(luò)中的最大連通集團(tuán)含有節(jié)點(diǎn)數(shù)隨逐漸刪去連邊而下降，但不是平緩下降，而是在某一點(diǎn)陡降。這說明在網(wǎng)絡(luò)里，擁堵的連邊往往溝通了兩個(gè)區(qū)域，它并不是在網(wǎng)絡(luò)里隨機(jī)分布的，而是往往出現(xiàn)在網(wǎng)絡(luò)里介數(shù)比較大的點(diǎn)上。所以當(dāng)刪到某一條邊后，你兩個(gè)區(qū)域不再連通，那么網(wǎng)絡(luò)中的最大連通集團(tuán)就陡降了。交通網(wǎng)絡(luò)里會(huì)存在若干這種瓶頸路，一旦把它們刪掉，網(wǎng)絡(luò)的溝通情況就會(huì)變得特別差，從而分成兩個(gè)集團(tuán)，而如果要疏導(dǎo)交通或提高交通的運(yùn)行體驗(yàn)，不需要全面地提升整個(gè)網(wǎng)絡(luò)，例如不需要把北京市所有的道路拓寬兩個(gè)車道，只需要把若干瓶頸路拓寬，就會(huì)很大程度上緩解交通擁堵。3.網(wǎng)絡(luò)傳播網(wǎng)絡(luò)傳播問題的研究對(duì)象是社交網(wǎng)絡(luò)。2013年發(fā)表在《Science》上的一篇文章研究了網(wǎng)絡(luò)上的傳播過程所具有的特點(diǎn)。它收集了2003年和2009年的兩組全球的數(shù)據(jù)，2003年是非典疫情爆發(fā)的一年，2009年是H1N1流感爆發(fā)的那年。數(shù)據(jù)中每個(gè)國(guó)家具有兩個(gè)數(shù)據(jù)，第一個(gè)數(shù)據(jù)是國(guó)家離病毒源頭的距離，我們知道SARS疫情是在中國(guó)爆發(fā)的，H1N1是在墨西哥爆發(fā)的，第二個(gè)數(shù)據(jù)是這個(gè)國(guó)家在中國(guó)爆發(fā)疫情后多長(zhǎng)時(shí)間被感染。收集完數(shù)據(jù)以后，作者就做了散點(diǎn)圖，每個(gè)點(diǎn)代表一個(gè)國(guó)家，橫軸是它離中國(guó)的距離，縱軸是它感染病毒的時(shí)間。結(jié)果發(fā)現(xiàn)一個(gè)國(guó)家在什么時(shí)候被感染病毒與它距離源頭有多遠(yuǎn)沒有明顯的關(guān)系。你離中國(guó)特別近，也不一定你明天就感染病毒，你離中國(guó)特別遠(yuǎn)，也并不意味著你很安全，距離的遠(yuǎn)近，實(shí)際上對(duì)病毒的傳染并沒有作出一個(gè)很好的解釋。

圖9疾病傳播時(shí)間與和疾病起源地有效距離的關(guān)系作者還關(guān)注到了全球航空網(wǎng)絡(luò)，搜集了兩個(gè)空港之間每天的航班數(shù)量及人流量，從而定義了一個(gè)有效距離

其中m和n分別代表一個(gè)國(guó)家，

表示這兩國(guó)之間的日常人流量，

越大，

越小，即如果兩個(gè)國(guó)家之間人流量特別多，這兩個(gè)國(guó)家的有效距離就越小。在重新定義距離后，作者作出了新的散點(diǎn)圖，縱軸依然是這個(gè)國(guó)家感染病毒的時(shí)間，橫軸表示有效距離，結(jié)果發(fā)現(xiàn)散點(diǎn)大多落在了一條直線上。這說明你離一個(gè)國(guó)家的有效距離比較近，你就會(huì)在比較早的時(shí)間感染這個(gè)病毒；如果一個(gè)國(guó)家離另外一個(gè)國(guó)家有效距離比較遠(yuǎn)的話，那么你感染這個(gè)病毒的時(shí)間也會(huì)比較靠后，病毒要經(jīng)過比較長(zhǎng)的時(shí)間才能傳播到這個(gè)地方。所以決定一個(gè)國(guó)家感染病毒的快慢，實(shí)際上是網(wǎng)絡(luò)的有效距離，而不是地理距離。我們?cè)谌粘Ｉ钪幸灿型瑯拥母杏X。例