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

1、復(fù)雜網(wǎng)絡(luò)簡介,復(fù)雜網(wǎng)絡(luò)簡介,第一部分：引言 第二部分：幾種經(jīng)典的網(wǎng)絡(luò)模型 第三部分：網(wǎng)絡(luò)研究中常見的統(tǒng)計(jì)量,第一部分 引言,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)實(shí)中的系統(tǒng)。一個(gè)典型的網(wǎng)絡(luò)由節(jié)點(diǎn)和連接兩個(gè)節(jié)點(diǎn)的邊組成。很長時(shí)間以來，網(wǎng)絡(luò)被考慮成點(diǎn)和邊的隨意集合，在數(shù)學(xué)上用隨機(jī)圖表示。近幾年，由于計(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)計(jì)語言來描述的清晰的模式和規(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)計(jì)量,3.1 各種常見統(tǒng)計(jì)量的求解過程 3.2 部分統(tǒng)計(jì)量的關(guān)系圖,3.1 各種常見統(tǒng)計(jì)量的求解過程,在復(fù)雜網(wǎng)絡(luò)的研究中，人們經(jīng)常用到的統(tǒng)計(jì)量有：度分布（degree dis

3、tribution）、平均最短距離（average shortest path length）、群聚系數(shù)（clustering coefficient）、度相關(guān)系數(shù)（assortativity coefficient）、介中性（betweenness centrality）等，下面將詳述它們的求解過程。,第三部分 網(wǎng)絡(luò)研究中常見的統(tǒng)計(jì)量,（i）度分布： ，其中 表示網(wǎng)絡(luò)中度為 k 的節(jié)點(diǎn)個(gè)數(shù)， 為網(wǎng)絡(luò)中的總節(jié)點(diǎn)數(shù)。 （ii）平均最短距離： ，其中 表示節(jié)點(diǎn) 與節(jié)點(diǎn) 之間的最短距離，求兩點(diǎn)之間的最短距離的算法很多，這里不再贅述。 （iii）群聚系數(shù)： ，其中 ， 表示節(jié)點(diǎn)的度，即它的鄰居個(gè)數(shù)，

4、表示 個(gè)鄰居中相互連接的對數(shù)。這種只是其中一個(gè)比較常用的定義方式，還有一些其它的關(guān)于群聚系數(shù)的定義，這里不再贅述。,（iv）度相關(guān)系數(shù)：關(guān)于度相關(guān)系數(shù) 的定義也很多，這里只敘述其中一個(gè)，如下：先提出節(jié)點(diǎn)的超出度 為節(jié)點(diǎn)度減1，超出度分布 ，其中 是度分布，再定義一個(gè)概率 表示超出度為 j 的節(jié)點(diǎn)與超出度為 k 的節(jié)點(diǎn)之間有邊連接的聯(lián)合概率。則 ，其中 。 （v）介中性：有節(jié)點(diǎn)介中性和邊介中性之分，表示網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)之間的最短路經(jīng)過某一節(jié)點(diǎn)或邊的總次數(shù)，如果兩節(jié)點(diǎn)之間的最短路 條，則均勻分配在每條最短路上，即經(jīng)過每條最短路的次數(shù)為 ，這樣所有節(jié)點(diǎn)或邊的介中性就可以統(tǒng)計(jì)出來。介中性在交通運(yùn)輸方

5、面有一定的意義。,3.2 部分統(tǒng)計(jì)量的關(guān)系圖,就上面四種網(wǎng)絡(luò)，關(guān)于這些統(tǒng)計(jì)量的研究如下表：,第三部分 網(wǎng)絡(luò)研究中常見的統(tǒng)計(jì)量,其中度分布是目前最具有代表性的統(tǒng)計(jì)量，對于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 distr

6、ibution of the Barabasi-Albert model, with , and , ;, ;, ; , . The 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 .,Fig. 5 Characteristic average shortest path length

7、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 drop C(p) remains almost constan