復(fù)雜網(wǎng)絡(luò)簡介

1、復(fù)雜網(wǎng)絡(luò)簡介 第一部分：引言 第二部分：幾種經(jīng)典的網(wǎng)絡(luò)模型 第三部分：網(wǎng)絡(luò)研究中常見的統(tǒng)計量第一部分 引言 1.1 網(wǎng)絡(luò)的概念以及相關(guān)研究 1.2 與交通相關(guān)的網(wǎng)絡(luò)研究1.1 網(wǎng)絡(luò)的概念以及相關(guān)研究 復(fù)雜網(wǎng)絡(luò)研究的是介于確定和隨機之間的現(xiàn)實中的系統(tǒng)。一個典型的網(wǎng)絡(luò)由節(jié)點和連接兩個節(jié)點的邊組成。很長時間以來，網(wǎng)絡(luò)被考慮成點和邊的隨意集合，在數(shù)學(xué)上用隨機圖表示。近幾年，由于計算機數(shù)據(jù)處理和運算能力的飛速發(fā)展，這種狀況發(fā)生了根本性的改變。人們開始研究大規(guī)模復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，研究發(fā)現(xiàn)，盡管很多網(wǎng)絡(luò)具有明顯的復(fù)雜性和隨機性，但也會出現(xiàn)可以用數(shù)學(xué)和統(tǒng)計語言來描述的清晰的模式和規(guī)律，其中最重要的是小世界效

2、應(yīng)（small-world effect），(Watts & Strogatz, 1998)和無標(biāo)度特性（scale-free property），(Barabsi & Albert, 1999)。 第一部分 引言1.2 與交通相關(guān)的網(wǎng)絡(luò)研究 迄今為止，對交通系統(tǒng)及相關(guān)網(wǎng)絡(luò)復(fù)雜性的研究成果還十分有限，較少的研究也主要集中在航空、地鐵和鐵路網(wǎng)絡(luò)上。Amaral et. al.（2000）研究了世界航空網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)；Latora和Marchiori（2002）對波士頓地鐵的網(wǎng)絡(luò)特性進行了初步研究； Sen et. al.（2002）研究了印度鐵路網(wǎng)絡(luò)的小世界特性； Jiang和C

3、laramunt（2004）對城市道路網(wǎng)絡(luò)進行了研究，以實例說明了此網(wǎng)絡(luò)具有小世界特性；Wu et. al. (2004a) 以北京市為例，說明了城市公交網(wǎng)絡(luò)為無標(biāo)度網(wǎng)絡(luò)；借助于SIR傳播模型，Wu et. al. (2004b) 提出了一種交通擁堵的演化模型。但是城市交通網(wǎng)絡(luò)的相關(guān)研究結(jié)果并不十分深入，其理論也并不完善。如何深入理解城市交通網(wǎng)絡(luò)的演化機制，是合理設(shè)計網(wǎng)絡(luò)的基礎(chǔ)。第一部分 引言第二部分 幾種經(jīng)典的網(wǎng)絡(luò)模型 2.1 網(wǎng)絡(luò)的生成過程 2.2 網(wǎng)絡(luò)圖 2.1 網(wǎng)絡(luò)的生成過程 在這一部分，我們將主要討論以下幾種網(wǎng)絡(luò)模型：規(guī)則網(wǎng)絡(luò)（Lattice network）、隨機網(wǎng)絡(luò)（ER模型）、

4、小世界網(wǎng)絡(luò)（WS模型）、無標(biāo)度網(wǎng)絡(luò)（BA模型）。 在復(fù)雜網(wǎng)絡(luò)的研究過程中，人們將網(wǎng)絡(luò)中的節(jié)點用1，2，N表出（注意：網(wǎng)絡(luò)中的節(jié)點個數(shù)N可以是動態(tài)變化的，也就是說網(wǎng)絡(luò)可以而且應(yīng)該是一個不斷演化的過程），網(wǎng)絡(luò)建模主要考慮的是點與點之間的連邊機制，下面詳細(xì)說明一下這四種網(wǎng)絡(luò)的生成過程。第二部分 幾種經(jīng)典的網(wǎng)絡(luò)模型 （i）規(guī)則網(wǎng)絡(luò)（Lattice）：節(jié)點個數(shù)N為不變的參數(shù)，將這N個編號的節(jié)點通過以下的連邊機制：每個節(jié)點連接到它的K臨近的節(jié)點 ，這里K是一個偶整數(shù)。 （ii）隨機網(wǎng)絡(luò)（ER）：節(jié)點個數(shù)N為不變的參數(shù)，將這N個編號的節(jié)點通過以下的連邊機制：節(jié)點 和節(jié)點 連接的概率為 。 （iii）小世界網(wǎng)

5、絡(luò)（WS）：節(jié)點個數(shù)N為不變的參數(shù)，將這N個編號的節(jié)點通過以下兩個過程的連邊機制：（1）初始化：構(gòu)造一個Lattice網(wǎng)絡(luò)；（2）隨機化：將網(wǎng)絡(luò)中的每一條邊以概率 進行重連（即遍歷選取每一條邊，固定邊的一個節(jié)點，以概率選擇另一個節(jié)點進行連接）。顯然WS網(wǎng)絡(luò)是規(guī)則網(wǎng)絡(luò)當(dāng) ，是隨機網(wǎng)絡(luò)當(dāng) 。 （iv）無標(biāo)度網(wǎng)絡(luò)（BA）：節(jié)點個數(shù)N不斷增加的演化網(wǎng)絡(luò)，點邊機制是通過以下兩個過程生成的：（1）增長性：初始網(wǎng)絡(luò)為 個節(jié)點，在每一個時間步增加一個新的節(jié)點，同時這個新節(jié)點與網(wǎng)絡(luò)中 個已經(jīng)存在的節(jié)點相連；（2）偏好連接：新節(jié)點選擇節(jié)點進行連接是有偏好的，連接概率 正比與節(jié)點的度，即選擇節(jié)點 進行連接的概率 。

6、程序的終止條件是事先給定的時間步或者網(wǎng)絡(luò)的規(guī)模N。1,2,.,2Kiiiijpp0p 1p 0m0()mm mipiiijjkpk2.2 網(wǎng)絡(luò)圖 對應(yīng)的網(wǎng)絡(luò)如圖1（規(guī)則網(wǎng)絡(luò)、隨機網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)）和圖2（無標(biāo)度網(wǎng)絡(luò)）：Fig. 1 The random rewiring procedure of the Watts-Strogatz model, which interpolates between a regular ring lattice and a random network without altering the number of nodes or edges. We star

7、t with N=20 nodes, each connected to its four nearest neighbors. For p=0 the original ring is unchanged; as p increases the network becomes increasingly disordered until for p=1 all edges are rewired randomly. 第二部分 幾種經(jīng)典的網(wǎng)絡(luò)模型Fig. 2 An example of scale-free network.第三部分 網(wǎng)絡(luò)研究中常見的統(tǒng)計量 3.1 各種常見統(tǒng)計量的求解過程 3.

8、2 部分統(tǒng)計量的關(guān)系圖3.1 各種常見統(tǒng)計量的求解過程 在復(fù)雜網(wǎng)絡(luò)的研究中，人們經(jīng)常用到的統(tǒng)計量有：度分布（degree distribution）、平均最短距離（average shortest path length）、群聚系數(shù)（clustering coefficient）、度相關(guān)系數(shù)（assortativity coefficient）、介中性（betweenness centrality）等，下面將詳述它們的求解過程。第三部分 網(wǎng)絡(luò)研究中常見的統(tǒng)計量 （i）度分布： ，其中 表示網(wǎng)絡(luò)中度為 k 的節(jié)點個數(shù)， 為網(wǎng)絡(luò)中的總節(jié)點數(shù)。 （ii）平均最短距離： ，其中 表示節(jié)點 與節(jié)點 之間

9、的最短距離，求兩點之間的最短距離的算法很多，這里不再贅述。 （iii）群聚系數(shù)： ，其中 ， 表示節(jié)點的度，即它的鄰居個數(shù)， 表示 個鄰居中相互連接的對數(shù)。這種只是其中一個比較常用的定義方式，還有一些其它的關(guān)于群聚系數(shù)的定義，這里不再贅述。( )knP knknn1(1)/2iji jldn nijdij1iiCCnid(1)/2iiiieCd dieid （iv）度相關(guān)系數(shù)：關(guān)于度相關(guān)系數(shù) 的定義也很多，這里只敘述其中一個，如下：先提出節(jié)點的超出度 為節(jié)點度減1，超出度分布 ，其中 是度分布，再定義一個概率 表示超出度為 j 的節(jié)點與超出度為 k 的節(jié)點之間有邊連接的聯(lián)合概率。則 ，其中 。

10、 （v）介中性：有節(jié)點介中性和邊介中性之分，表示網(wǎng)絡(luò)中任何兩個節(jié)點之間的最短路經(jīng)過某一節(jié)點或邊的總次數(shù)，如果兩節(jié)點之間的最短路 條，則均勻分配在每條最短路上，即經(jīng)過每條最短路的次數(shù)為 ，這樣所有節(jié)點或邊的介中性就可以統(tǒng)計出來。介中性在交通運輸方面有一定的意義。rq(1) (1)( )( )kkP kq kkP k( )P jke21( ) ( )jkjkqrjk eq j q k222( ) ( )qkkk q kkq kijT1ijT3.2 部分統(tǒng)計量的關(guān)系圖 就上面四種網(wǎng)絡(luò)，關(guān)于這些統(tǒng)計量的研究如下表：第三部分 網(wǎng)絡(luò)研究中常見的統(tǒng)計量 其中度分布是目前最具有代表性的統(tǒng)計量，對于ER模型、W

11、S模型和BA模型的度分布如圖3-4。另外，對于WS模型，網(wǎng)絡(luò)的最短平均距離L和群聚系數(shù)C與重連概率p的變化關(guān)系如圖5所示 Fig. 3 Degree distribution of the Watts-Strogatz model for K=3, N=1000 and various p.Fig. 4 Numerical simulations of network evolution: Degree distribution of the Barabasi-Albert model, with , and , ;, ; , ; , . The slope of the dashed lin

12、e is , providing the best fit to the data. The inset shows the rescaled distribution (see text) for the same values of m, the slope of the dashed line being .0300000Nmt 01mm03mm05mm07mm2.92( )/2P km3Fig. 5 Characteristic average shortest path length L (p) and clustering coefficient C(p) for the Watts-Strogatz model. The data are normalized by the values L (0) and C(0) for a regular lattice. A logarithmic horizontal scale resolves the rapid drop in L (p)