【文章內(nèi)容簡(jiǎn)介】 網(wǎng)絡(luò)我們稱之為有向網(wǎng)絡(luò)(directed network)。無(wú)向圖的概念：若圖中的每條邊都是沒有方向的，用和表示頂點(diǎn)，用(，)表示點(diǎn)之間的邊。因此，在有向圖中，兩條邊可分別用，與，表示，而在無(wú)向圖中，(，)與(，)只能代表同一條邊。在無(wú)向圖中邊是沒有方向的，包含無(wú)向圖的網(wǎng)絡(luò)我們稱之為無(wú)向網(wǎng)絡(luò)(undirected network)。簡(jiǎn)單圖：沒有環(huán)及多重邊的圖。無(wú)權(quán)網(wǎng)絡(luò)我們還可以給網(wǎng)絡(luò)圖中的邊賦予一定的權(quán)值或者不賦，如果網(wǎng)絡(luò)圖中的邊不含有權(quán)值，那該網(wǎng)絡(luò)就稱為無(wú)權(quán)網(wǎng)絡(luò)(unweighted networks)。如果給圖中的每條邊賦予一定的權(quán)值，那么我們稱該網(wǎng)絡(luò)為加權(quán)網(wǎng)絡(luò)(weighted networks)。本章研究的網(wǎng)絡(luò)是無(wú)向無(wú)權(quán)網(wǎng)絡(luò)，并且作出如下假設(shè)：不包括自環(huán)和重邊(即沒有以同一個(gè)節(jié)點(diǎn)為起點(diǎn)和終點(diǎn)的邊，且任意兩個(gè)節(jié)點(diǎn)之間至多只有一條邊)。(1)鄰接矩陣通常要將一個(gè)圖表達(dá)清楚，最好方法是將它描畫出來(lái)，即用直觀的圖形來(lái)表示。但直觀的圖形不利于計(jì)算機(jī)計(jì)算，為了對(duì)圖進(jìn)行更好的研究，我們需要將圖的有關(guān)數(shù)據(jù)輸入計(jì)算機(jī)中，根據(jù)圖論理論，在存儲(chǔ)圖的時(shí)候常常使用鄰接矩陣表示法來(lái)實(shí)現(xiàn)。圖中節(jié)點(diǎn)之間的關(guān)系用鄰接矩陣來(lái)表示。若圖G=(V，E)包含有n個(gè)節(jié)點(diǎn)，則此圖的鄰接矩陣便是一個(gè)n階方陣，該方陣符合下列條件： （1）根據(jù)鄰接矩陣的定義，我們可以得到有向圖的鄰接矩陣一般不為對(duì)稱矩陣（在特殊情況下可能為對(duì)稱矩陣），而無(wú)向圖的鄰接矩陣是對(duì)稱的矩陣。我們很容易根據(jù)于鄰接矩陣來(lái)判斷任兩個(gè)節(jié)點(diǎn)之間是否存在邊，并且根據(jù)鄰接矩陣，我們很容易求得各個(gè)節(jié)點(diǎn)的度。對(duì)于無(wú)向圖而言，節(jié)點(diǎn)的度由下述方法計(jì)算：鄰接矩陣中第i行(或列)的值不為0的元素個(gè)數(shù)，即元素之和的值為節(jié)點(diǎn)的度。網(wǎng)絡(luò)可以用一種帶權(quán)的連通圖表示，基于此，我們只要稍加擴(kuò)充鄰接矩陣的內(nèi)容，便可用來(lái)表示網(wǎng)絡(luò)。設(shè)網(wǎng)絡(luò)G=(V，E，W)具有n個(gè)頂點(diǎn)，編號(hào)為l，2，?，n。描述網(wǎng)絡(luò)G的帶權(quán)鄰接矩陣為一個(gè)n階方陣A，其元素定義為： （2）為表示節(jié)點(diǎn)間的相鄰關(guān)系，我們需要在計(jì)算機(jī)中存儲(chǔ)一個(gè)的鄰接矩陣，這樣才能用鄰接矩陣法來(lái)表示圖。需個(gè)位置來(lái)存儲(chǔ)有向圖的鄰接矩陣。任意兩個(gè)節(jié)點(diǎn)和之間是否有長(zhǎng)度為m的路徑相連，我們可以用鄰接矩陣來(lái)加以判斷。方法很簡(jiǎn)單，只需驗(yàn)證一下鄰接矩陣的第i行和第j列元素是否為0就可以了。(2)鄰接鏈表圖的另外一種存儲(chǔ)方式除了鄰接矩陣表示法外，還有另外一種存儲(chǔ)方式，即鄰接鏈表表示法。鄰接鏈表可以這樣描述：在圖中，建立一個(gè)單鏈表與每個(gè)節(jié)點(diǎn)相對(duì)應(yīng)，依附于節(jié)點(diǎn)的邊用第i個(gè)單鏈表中的節(jié)點(diǎn)表示(對(duì)于有向圖是以為尾的弧)。鄰接鏈表中的節(jié)點(diǎn)有兩種類型：分別為表節(jié)點(diǎn)和表頭節(jié)點(diǎn)，如下所示。表節(jié)點(diǎn)adjvexnextarcinfo表頭節(jié)點(diǎn)damfirstarc其含義為：adjvex指示和節(jié)點(diǎn)相鄰接的節(jié)點(diǎn)的序號(hào)；nextarc指示下一個(gè)邊或者弧的節(jié)點(diǎn)；info用于存儲(chǔ)和邊或弧相關(guān)的一些的信息，如權(quán)值等；dam存儲(chǔ)節(jié)點(diǎn)的名或其他有關(guān)信息；firstarc指示鏈表中的第一條邊或者弧。對(duì)于無(wú)向圖的鄰接鏈表，頂點(diǎn)的度恰好為第i個(gè)鄰接鏈表中表節(jié)點(diǎn)的數(shù)目。隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，復(fù)雜網(wǎng)絡(luò)作為一種新技術(shù)，被越來(lái)越多的行業(yè)應(yīng)用，在股票行業(yè)，復(fù)雜網(wǎng)絡(luò)也正已蓬勃的勢(shì)頭嶄露頭角。股票市場(chǎng)的研究者利用網(wǎng)絡(luò)知識(shí)研究股票的各種特性，以便對(duì)股票的下一態(tài)勢(shì)做出評(píng)估和預(yù)測(cè)，這一研究也被越來(lái)越多的人關(guān)注。股票網(wǎng)絡(luò)，簡(jiǎn)單的說(shuō)，就是把不同種類的股票作為節(jié)點(diǎn)，把各種類股票之間的存在的聯(lián)系看做邊而連成的網(wǎng)絡(luò)。對(duì)于股票網(wǎng)絡(luò)的邊的生成，要通過(guò)計(jì)算兩只股票之間的相關(guān)系數(shù)的大小是否大于規(guī)定的閾值而定。通過(guò)計(jì)算得到的各節(jié)點(diǎn)之間的邊，有很強(qiáng)的聯(lián)系性，也能更好的描述股票之間的關(guān)系以及相互之間的影響。股票網(wǎng)絡(luò)是基于復(fù)雜網(wǎng)絡(luò)這一技術(shù)引申而來(lái)的具體應(yīng)用，對(duì)于股票網(wǎng)絡(luò)的實(shí)現(xiàn)原理或者機(jī)制的研究，歸根結(jié)底，要從復(fù)雜網(wǎng)絡(luò)出發(fā)，而統(tǒng)計(jì)特性是復(fù)雜網(wǎng)絡(luò)這一新興技術(shù)研究的基礎(chǔ)。本篇文章將對(duì)其統(tǒng)計(jì)特性進(jìn)行簡(jiǎn)單的研究，經(jīng)過(guò)學(xué)習(xí)研究與總結(jié)，將復(fù)雜網(wǎng)絡(luò)的研究基礎(chǔ)進(jìn)行歸納。具體分為以下三種特性：第一種特性，平均路徑長(zhǎng)度，簡(jiǎn)單理解就是所有路徑長(zhǎng)度的平均值，這里的路徑長(zhǎng)度，在網(wǎng)絡(luò)圖中是邊的數(shù)目，而不是通常理解的距離。第二種特性，聚集系數(shù)， 可以理解為網(wǎng)絡(luò)中各元素的之間的聯(lián)系的緊密情況，比如說(shuō)， A城市有直接到B城市的公交，A城市有直接到C城市的公交，那么A城市有可能有直接到C城市的公交，B城市也可能有直接到C城市的公交，在這個(gè)例子中，聚集系數(shù)就是用來(lái)研究 A城市到C城市以及B城市到C城市有直達(dá)公交的系數(shù)。第三種特性，度，這個(gè)就是我們常說(shuō)的與某個(gè)節(jié)點(diǎn)直接相連的節(jié)點(diǎn)的數(shù)目，也可以說(shuō)成是從這個(gè)節(jié)點(diǎn)引出的邊的數(shù)目。在復(fù)雜網(wǎng)絡(luò)的研究中，對(duì)于復(fù)雜網(wǎng)絡(luò)的圖譜基于的是無(wú)向網(wǎng)絡(luò)圖。在實(shí)際的網(wǎng)絡(luò)圖研究中，會(huì)分為有向和無(wú)向兩種情況。所以，在這邊的本文所說(shuō)的度，沒有出度還是入度之分。 在復(fù)雜網(wǎng)絡(luò)圖中，路徑長(zhǎng)度指的是邊的數(shù)目，而不是具體的距離，比如兩個(gè)節(jié)點(diǎn)i和j，從i出發(fā)可以通過(guò)很多條路徑d(i)到達(dá)j，這些路徑的長(zhǎng)度有長(zhǎng)有短，選取其中的長(zhǎng)度最短的路徑dmin,其中dmin=min(d(i))，則dmin中包含的邊的數(shù)目就是i和j之間的距離dij。在復(fù)雜網(wǎng)絡(luò)圖中，對(duì)所有節(jié)點(diǎn)之間的距離進(jìn)行計(jì)算，會(huì)得到一個(gè)最大值dmax，這個(gè)最大值dmax被稱為網(wǎng)絡(luò)的直徑，記為D，即 （3）在復(fù)雜網(wǎng)絡(luò)中，對(duì)所有節(jié)點(diǎn)之間的距離進(jìn)行計(jì)算，求這些距離的平均值dave，這個(gè)平均值就是平均路徑長(zhǎng)度，網(wǎng)絡(luò)的特征路徑長(zhǎng)度是dave 的另一種說(shuō)法，在此我們記dave為L(zhǎng)，即 （4）其中N為網(wǎng)絡(luò)中節(jié)點(diǎn)的總個(gè)數(shù)。為了處理的方便，在平均路徑長(zhǎng)度的上述計(jì)算公式中，包含了節(jié)點(diǎn)到自身的距離，雖然這個(gè)距離為零。如果忽略節(jié)點(diǎn)到自身的長(zhǎng)度，上述公式就會(huì)有偏差，但是在復(fù)雜網(wǎng)絡(luò)的具體實(shí)現(xiàn)中，這種偏差是很小的，甚至可以忽略。由a個(gè)節(jié)點(diǎn)，b條邊構(gòu)成的網(wǎng)絡(luò)的平均路徑長(zhǎng)度，可以通過(guò)廣度優(yōu)先搜索算法來(lái)確定。在城市交通開通關(guān)系網(wǎng)中，dave是網(wǎng)絡(luò)內(nèi)兩個(gè)城市之間最短關(guān)系鏈中的經(jīng)過(guò)的城市的平均個(gè)數(shù)。在你城市交通網(wǎng)中，B城市和C城市很可能彼此也是交通直達(dá)的，這被稱為網(wǎng)絡(luò)的聚類性。在網(wǎng)絡(luò)圖中，對(duì)于圖中的每一個(gè)節(jié)點(diǎn)，我們假設(shè)有ki條邊與之相連接，我們稱這ki條邊連接的節(jié)點(diǎn)為節(jié)點(diǎn)i的鄰居。根據(jù)數(shù)學(xué)計(jì)算N個(gè)點(diǎn)，它們之間邊的數(shù)目的最大值為N(N1)/2。在研究復(fù)雜網(wǎng)絡(luò)的特性中，我們假設(shè)連接N個(gè)節(jié)點(diǎn)的邊的實(shí)際數(shù)目為M，則定義聚集系數(shù)就是M/N的結(jié)果，在這兒，我們記節(jié)點(diǎn)i的聚集系數(shù)為Ci，即如下所示，可以得到Ci的計(jì)算公式。 (5)在前面的研究中，本文對(duì)復(fù)雜網(wǎng)絡(luò)的另一特性，平均路徑長(zhǎng)度進(jìn)行了研究，整個(gè)網(wǎng)絡(luò)圖的平均路徑長(zhǎng)度是各個(gè)節(jié)點(diǎn)路徑長(zhǎng)度的平均值，引申到聚集系數(shù)，則就是所有節(jié)點(diǎn)的聚集系數(shù)的平均值，記為Cave，記任一節(jié)點(diǎn)的聚集系數(shù)為Ci，則Cave=（C1+C2+…Ci+…Cn）/n。 如圖所示，是本文的規(guī)范表示，其中，C表示整個(gè)復(fù)雜網(wǎng)絡(luò)的聚集系數(shù)： (6)根據(jù)上面對(duì)聚集系數(shù)的計(jì)算方式，本文將對(duì)公式中各參數(shù)的取值情況進(jìn)行全面的分析。第一種情況，網(wǎng)絡(luò)圖中僅僅是一個(gè)孤立節(jié)點(diǎn)，則C=O；第二種情況，任意兩個(gè)節(jié)點(diǎn)沒有通過(guò)第三個(gè)節(jié)點(diǎn)相連，此時(shí)C=1，這時(shí)候就是全局耦合網(wǎng)絡(luò)圖；還有一種極端情況，就是網(wǎng)絡(luò)圖中包含的無(wú)窮多個(gè)節(jié)點(diǎn)，此時(shí)C=O(N1)；第四種情況就是我們研究的普遍情況了，這種情況是復(fù)雜網(wǎng)絡(luò)實(shí)際應(yīng)用的最常見也是最有實(shí)用性的情況，這時(shí)候的C，取值在O(N1)和1之間。度是復(fù)雜網(wǎng)絡(luò)中一個(gè)重要的概念。網(wǎng)絡(luò)中節(jié)點(diǎn)的度表示為與這個(gè)節(jié)點(diǎn)相連的邊數(shù)。如果某個(gè)節(jié)點(diǎn)的度數(shù)很大則表示此節(jié)點(diǎn)在股票網(wǎng)絡(luò)中的地位比較重要。復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)的度數(shù)的平均值為平均度，用k來(lái)表示。 我們用P(k)來(lái)表示復(fù)雜網(wǎng)絡(luò)中度的分布，表示網(wǎng)絡(luò)中節(jié)點(diǎn)度數(shù)為k的概率。也可表示為節(jié)點(diǎn)度數(shù)為k的結(jié)點(diǎn)個(gè)數(shù)與總結(jié)點(diǎn)數(shù)的比值。得到P(k)=frequencc(k)/N。v3v1v2v5v4v7v8v9v6圖1 簡(jiǎn)單網(wǎng)絡(luò)模型上圖是很簡(jiǎn)單的網(wǎng)絡(luò)，它有9個(gè)節(jié)點(diǎn)，它的節(jié)點(diǎn)集是V={v1，v2，v3...v9}，度分布分別是p(5)=1/9，p(3)=2/9，p(2)=5/9，p(1)=1/9。規(guī)則網(wǎng)絡(luò)的節(jié)點(diǎn)的度是相同的，其分布符合Detla分布。ER隨機(jī)網(wǎng)絡(luò)中的節(jié)點(diǎn)的連接是以概率P相連的，它的分布符合泊松分布。WS小世界網(wǎng)絡(luò)模型，它的度分布有點(diǎn)相似于ER網(wǎng)絡(luò)模型，不過(guò)如果它的度數(shù)很大的時(shí)候，WS小世界網(wǎng)絡(luò)的度分布符合公式，0a1。實(shí)際的度分布和泊松分布不相符合。生活中大多數(shù)的網(wǎng)絡(luò)符合冪律分布，它存在于生活總的很多方面。符合冪律分布的網(wǎng)絡(luò)我們把它叫做無(wú)標(biāo)度網(wǎng)絡(luò)。 復(fù)雜網(wǎng)絡(luò)基本模型 ER模型在1959年，Erdos和Renyi提出了ER模型。隨機(jī)網(wǎng)絡(luò)中的節(jié)點(diǎn)是固定的N，節(jié)點(diǎn)之間以概率p相連接，最終可以得到N條邊。如果隨機(jī)網(wǎng)絡(luò)全連通，則p=1，可以得到總變數(shù)為；如果p=0，網(wǎng)絡(luò)中的節(jié)點(diǎn)都是孤立的邊數(shù)是O；當(dāng)p處于01之間是網(wǎng)絡(luò)中有條；度的平均值為。隨機(jī)網(wǎng)絡(luò)模型首先是由Erdos和Renyi建立的，并且研究了隨機(jī)網(wǎng)絡(luò)的度分布，發(fā)現(xiàn)當(dāng)N很大時(shí)，p(k)符合泊松；如果這時(shí)p接近于0網(wǎng)絡(luò)中的節(jié)點(diǎn)大多是孤立的導(dǎo)致網(wǎng)絡(luò)的直徑L非常大，當(dāng)p慢慢變大時(shí)網(wǎng)絡(luò)節(jié)點(diǎn)之間的聯(lián)系變的越來(lái)越密切，當(dāng)連接概率p為1時(shí)股票網(wǎng)絡(luò)中的節(jié)點(diǎn)L為1。隨機(jī)網(wǎng)絡(luò)的聚類系數(shù)為，表示連接數(shù)它越大，聚類系數(shù)C越大；但若系統(tǒng)的節(jié)點(diǎn)很多，C反而會(huì)變小。隨機(jī)網(wǎng)絡(luò)有以下三種性質(zhì)：(1)較短的平均路徑長(zhǎng)度；(2)較小的聚類系數(shù)；(3) 泊松度分布。 WS小世界模型 一般大家在生活中認(rèn)識(shí)的都是鄰居，同學(xué)或者同事，也會(huì)有少數(shù)的外國(guó)的親朋好友。互聯(lián)網(wǎng)上的網(wǎng)頁(yè)不是像隨機(jī)網(wǎng)絡(luò)模型那樣隨便關(guān)聯(lián)的。1998年，Watts和Strogtz提出了了小世界模型的概念， WS小世界模型的構(gòu)造算法如下： (1)以完全規(guī)則圖作為開始：把一個(gè)含有N個(gè)節(jié)點(diǎn)的耦合網(wǎng)絡(luò)圍成一個(gè)環(huán)(2)隨機(jī)的連接：一條邊連接兩個(gè)端點(diǎn)，選取其中一個(gè)斷點(diǎn)，另一個(gè)斷點(diǎn)以概率p與之相連接且每個(gè)節(jié)點(diǎn)不能自連接。上面的建模中，p為0時(shí)是規(guī)則網(wǎng)絡(luò)，p=l是ER網(wǎng)絡(luò)模型，當(dāng)p處于01之間的時(shí)候就是我們所說(shuō)的WS模型，如下圖所示。 圖2 WS小世界模型通過(guò)上面的方法得到的股票網(wǎng)絡(luò)的聚類系數(shù)是概率p的函數(shù)。平均路徑長(zhǎng)度也是概率p的函數(shù)。當(dāng)p為0時(shí)網(wǎng)絡(luò)的聚類系數(shù)很高是為C(0)=3/4。而平均路徑長(zhǎng)度也很大為。當(dāng)p遠(yuǎn)小于1時(shí)，得到的網(wǎng)絡(luò)的聚類系數(shù)接近于C(0)，而其平均路徑長(zhǎng)度且遠(yuǎn)小于。我們把具有較短的平均路徑長(zhǎng)度以及較高聚類系數(shù)的網(wǎng)絡(luò)模型成為WS小世界模型 隨機(jī)模型可以用泊松分布來(lái)表示。小世界模型也可以用泊松分布來(lái)表示。泊松分布是在k處有一峰值后呈指數(shù)衰減。表明當(dāng)度遠(yuǎn)大于度平均值時(shí)，這個(gè)節(jié)點(diǎn)大多是不存在的。所以這種類型的網(wǎng)絡(luò)被稱為均勻網(wǎng)絡(luò)。最近對(duì)于復(fù)雜網(wǎng)絡(luò)研究的重大發(fā)現(xiàn)是許多網(wǎng)絡(luò)包括互聯(lián)網(wǎng)等的度分布具有冪律分布。這種網(wǎng)絡(luò)被稱為無(wú)標(biāo)度網(wǎng)絡(luò)。BA網(wǎng)絡(luò)的構(gòu)造方法如下： (1)增長(zhǎng)性：假設(shè)股票網(wǎng)絡(luò)中存在個(gè)節(jié)點(diǎn)將新節(jié)點(diǎn)連接股票網(wǎng)絡(luò)