復(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ò)研究的是介于確定和隨機(jī)之間的現(xiàn)實中的系統(tǒng)。 一個典型的網(wǎng)絡(luò)由節(jié)點(diǎn)和連接兩個節(jié)點(diǎn)的邊組成。很長時 間以來，網(wǎng)絡(luò)被考慮成點(diǎn)和邊的隨意集合，在數(shù)學(xué)上用隨 機(jī)圖表示。近幾年，由于計算機(jī)數(shù)據(jù)處理和運(yùn)算能力的飛 速發(fā)展，這種狀況發(fā)生了根本性的改變。人們開始研究大 規(guī)模復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，研究發(fā)現(xiàn)，盡管很多網(wǎng)絡(luò)具有 明顯的復(fù)雜性和隨機(jī)性，但也會出現(xiàn)可以用數(shù)學(xué)和統(tǒng)計語 言來描述的清晰的模式和規(guī)律，其

2、中最重要的是小世界效 應(yīng)（small-world effect），(Watts 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.2 部分統(tǒng)計量的關(guān)系圖 3.1 各種常見統(tǒng)計量的求解過程 在復(fù)雜網(wǎng)絡(luò)的研究中，人們經(jīng)常用到的統(tǒng)計量有：度分布 （degree

3、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é)點(diǎn)個數(shù)， 為網(wǎng)絡(luò)中的總節(jié)點(diǎn)數(shù)。 （ii）平均最短距離： ，其中 表示節(jié) 點(diǎn) 與節(jié)點(diǎn) 之間的最短距離，求兩點(diǎn)之間的最短 距離的算法很多，這里不再贅述。 （iii）群聚系數(shù)： ，其中 ， 表示 節(jié)點(diǎn)的度，即

4、它的鄰居個數(shù)， 表示 個鄰居中 相互連接的對數(shù)。這種只是其中一個比較常用的 定義方式，還有一些其它的關(guān)于群聚系數(shù)的定義， 這里不再贅述。 ( ) k n P k n k n n 1 (1)/2 ij i j ld n n ij d i j 1 i i CC n i d(1)/2 i i ii e C d d i e i d （iv）度相關(guān)系數(shù)：關(guān)于度相關(guān)系數(shù) 的定義也很 多，這里只敘述其中一個，如下：先提出節(jié)點(diǎn)的 超出度 為節(jié)點(diǎn)度減1，超出度分布 ，其 中 是度分布，再定義一個概率 表示超出度為 j 的節(jié)點(diǎn)與超出度為 k 的節(jié)點(diǎn)之間有邊連接的聯(lián)合 概率。則 ，其中 。 （v）介中性：有節(jié)點(diǎn)介中

5、性和邊介中性之分，表 示網(wǎng)絡(luò)中任何兩個節(jié)點(diǎn)之間的最短路經(jīng)過某一節(jié) 點(diǎn)或邊的總次數(shù)，如果兩節(jié)點(diǎn)之間的最短路 條， 則均勻分配在每條最短路上，即經(jīng)過每條最短路 的次數(shù)為 ，這樣所有節(jié)點(diǎn)或邊的介中性就可以 統(tǒng)計出來。介中性在交通運(yùn)輸方面有一定的意義。 r q (1) (1) ( ) ( ) k kP k q k kP k ()P jk e 2 1 ( ) ( ) jk jk q rjk eq j q k 222 ( ) ( ) q kk k q kkq k ij T 1 ij T 3.2 部分統(tǒng)計量的關(guān)系圖 就上面四種網(wǎng)絡(luò)，關(guān)于這些統(tǒng)計量的研究如下表： 第三部分 網(wǎng)絡(luò)研究中常見的統(tǒng)計量 其中度分布是

6、目前最具有代表性的統(tǒng)計量，對于ER模型、 WS模型和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 , ;, ; , ; , . Th

7、e slope of the dashed line 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 . 0 300000Nmt 0 1mm 0 3mm 0 5mm 0 7mm 2.9 2 ( )/2P km 3 Fig. 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), corresponding to the onset of the small-world phenomenon. During this d