序論：寫作是一種深度的自我表達(dá)。它要求我們深入探索自己的思想和情感，挖掘那些隱藏在內(nèi)心深處的真相，好投稿為您帶來(lái)了一篇復(fù)雜網(wǎng)絡(luò)論文范文，愿它們成為您寫作過(guò)程中的靈感催化劑，助力您的創(chuàng)作。

基于復(fù)雜網(wǎng)絡(luò)理論的計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)浞治?

摘要：復(fù)雜網(wǎng)絡(luò)是指具有無(wú)標(biāo)度、小世界、吸引子、自相似、自組織中部分或者所有性質(zhì)的網(wǎng)絡(luò)。在現(xiàn)實(shí)世界中，許多復(fù)雜的系統(tǒng)基本上都能以網(wǎng)絡(luò)來(lái)進(jìn)行描述，而現(xiàn)實(shí)中的那些復(fù)雜的系統(tǒng)則可以以“復(fù)雜網(wǎng)絡(luò)”來(lái)稱之，比如社會(huì)網(wǎng)、交通網(wǎng)、電力網(wǎng)、萬(wàn)維網(wǎng)、因特網(wǎng)等等都可以稱之為復(fù)雜網(wǎng)絡(luò)。本文主要通過(guò)對(duì)復(fù)雜網(wǎng)絡(luò)理論的介紹，從而對(duì)計(jì)算機(jī)Internet網(wǎng)進(jìn)行分析，對(duì)Internet網(wǎng)這一復(fù)雜系統(tǒng)進(jìn)行探究，揭示Internet拓?fù)洮F(xiàn)象的特性、規(guī)律及動(dòng)因。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；計(jì)算機(jī)網(wǎng)絡(luò)；網(wǎng)絡(luò)拓?fù)?

在現(xiàn)實(shí)世界中，許多復(fù)雜的系統(tǒng)基本上都能以網(wǎng)絡(luò)來(lái)進(jìn)行描述，而現(xiàn)實(shí)中的那些復(fù)雜的系統(tǒng)則可以以“復(fù)雜網(wǎng)絡(luò)”來(lái)稱之，比如社會(huì)網(wǎng)、交通網(wǎng)、電力網(wǎng)、萬(wàn)維網(wǎng)、因特網(wǎng)等等都可以稱之為復(fù)雜網(wǎng)絡(luò)。在這些復(fù)雜系統(tǒng)中，那些現(xiàn)實(shí)中的實(shí)體往往通過(guò)復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)來(lái)表示，實(shí)體跟節(jié)點(diǎn)相對(duì)應(yīng)，節(jié)點(diǎn)之間的連線（即邊）則對(duì)應(yīng)于實(shí)體與實(shí)體之間的關(guān)系。而Internet網(wǎng)絡(luò)自從誕生開(kāi)始，其一直沿著更優(yōu)、更高級(jí)、更復(fù)雜的路徑演化和發(fā)展著，現(xiàn)在Internet網(wǎng)絡(luò)已經(jīng)成為一個(gè)開(kāi)放的、無(wú)中心控制的、異構(gòu)的、分布式的極其復(fù)雜的網(wǎng)絡(luò)系統(tǒng)。其復(fù)雜性主要表現(xiàn)在：第一，Internet網(wǎng)絡(luò)結(jié)構(gòu)日益復(fù)雜。Internet網(wǎng)絡(luò)的規(guī)模在不斷的擴(kuò)大，網(wǎng)絡(luò)中的節(jié)點(diǎn)不斷加入和退出，各個(gè)節(jié)點(diǎn)以及它們之間的鏈路時(shí)常發(fā)生失效，鏈路也經(jīng)常出現(xiàn)方向和權(quán)重的變化。第二，網(wǎng)絡(luò)中節(jié)點(diǎn)日益復(fù)雜化。各節(jié)點(diǎn)越來(lái)越具有復(fù)雜非線性行為的動(dòng)力學(xué)系統(tǒng)。第三，復(fù)雜因素之間的彼此影響。各個(gè)節(jié)點(diǎn)之間或者數(shù)據(jù)包流和節(jié)點(diǎn)之間出現(xiàn)了非線性的作用及其各個(gè)用戶之間的競(jìng)爭(zhēng)和合作等等都是彼此的影響因素。

一、復(fù)雜網(wǎng)絡(luò)理論簡(jiǎn)介

復(fù)雜網(wǎng)絡(luò)是指具有無(wú)標(biāo)度、小世界、吸引子、自相似、自組織中部分或者所有性質(zhì)的網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)理論的主要內(nèi)容有：網(wǎng)絡(luò)的演化特征、演化規(guī)律、演化動(dòng)力學(xué)機(jī)制、演化的統(tǒng)計(jì)規(guī)律以及網(wǎng)絡(luò)的模型特質(zhì)、形成機(jī)制、幾何性質(zhì)、結(jié)構(gòu)穩(wěn)定性等。在自然科學(xué)中，復(fù)雜網(wǎng)絡(luò)研究的最為基本的內(nèi)容包括：度、相關(guān)性、集聚程度、最短距離、介數(shù)以及它們的分布特征。

復(fù)雜網(wǎng)絡(luò)系統(tǒng)一般有著下面幾個(gè)特征：

（1）小世界。復(fù)雜網(wǎng)絡(luò)通過(guò)簡(jiǎn)單的描述對(duì)許多復(fù)雜的現(xiàn)實(shí)網(wǎng)絡(luò)進(jìn)行了解釋，認(rèn)為不管規(guī)模多大的網(wǎng)絡(luò)，其任意兩個(gè)節(jié)點(diǎn)都是由一條路徑連接的事實(shí)。它闡釋無(wú)論什么世界都是通過(guò)相互關(guān)系非常小的無(wú)數(shù)個(gè)節(jié)點(diǎn)所連接起來(lái)的。比如，在現(xiàn)實(shí)的社會(huì)網(wǎng)中，每個(gè)人的生活圈很小，人跟人認(rèn)識(shí)的數(shù)目非常少，但是這個(gè)社會(huì)卻是由無(wú)數(shù)個(gè)關(guān)系所組成的，通過(guò)一條關(guān)系，可以找到跟你相距很遠(yuǎn)的無(wú)關(guān)系的陌生人。就好像麥克盧漢所講的，地球?qū)⒃絹?lái)越小，是一個(gè)小的地球村，即一個(gè)小世界。

（2）集群性。復(fù)雜網(wǎng)絡(luò)會(huì)越來(lái)越具有集群性。比如，在現(xiàn)實(shí)的社會(huì)網(wǎng)絡(luò)中，每個(gè)人都有自己的朋友圈、熟人圈，在這個(gè)圈子里，每位成員都可能跟其他成員認(rèn)識(shí)。集群性就是指網(wǎng)絡(luò)具有一種內(nèi)聚的傾向，即在一個(gè)大網(wǎng)絡(luò)中，會(huì)分布著許多個(gè)彼此聯(lián)系的積聚小網(wǎng)絡(luò)。比如一個(gè)朋友圈往往會(huì)通過(guò)某種關(guān)系跟另一個(gè)朋友圈聯(lián)系著。

（3）冪律的度分布。度是指網(wǎng)絡(luò)中的節(jié)點(diǎn)及其節(jié)點(diǎn)關(guān)系的數(shù)量；度的相關(guān)性是指各個(gè)節(jié)點(diǎn)之間的聯(lián)系緊密程度；介數(shù)是指網(wǎng)絡(luò)中所有最短路徑經(jīng)過(guò)某一節(jié)點(diǎn)的數(shù)量，即有一節(jié)點(diǎn)A，在網(wǎng)絡(luò)中，所有經(jīng)過(guò)A的數(shù)量，它反映的是節(jié)點(diǎn)A的影響力。無(wú)標(biāo)度網(wǎng)絡(luò)的特征主要集中反映了集聚的集中性。總之，復(fù)雜網(wǎng)絡(luò)的主要特征有：無(wú)標(biāo)度性、小世界效應(yīng)、節(jié)點(diǎn)度的冪律分布。

二、Internet網(wǎng)絡(luò)的拓?fù)浞治?

（一）Internet拓?fù)涞奶攸c(diǎn)

近些年來(lái)對(duì)于Internet拓?fù)涞难芯浚钪匾某晒菍?duì)于Internet拓?fù)涔?jié)點(diǎn)度的冪律分布。這種分布在規(guī)模不同的網(wǎng)絡(luò)拓?fù)渲斜憩F(xiàn)出一定的穩(wěn)定性，也就是指，在規(guī)模不同的Internet拓?fù)渲?，它們的?jié)點(diǎn)度表現(xiàn)出一種冪律分布，即：

P（k）=k-β

其中，β一般在2―3這個(gè)小范圍內(nèi)進(jìn)行波動(dòng)，k是指節(jié)點(diǎn)度，P（k）表示度為k的節(jié)點(diǎn)出現(xiàn)的概率，即分布率。

Interne作為一個(gè)復(fù)雜網(wǎng)絡(luò)，從其通信網(wǎng)絡(luò)的優(yōu)化目的來(lái)說(shuō)，其實(shí)現(xiàn)節(jié)點(diǎn)間平均距離最小化、網(wǎng)絡(luò)邊數(shù)最小化是其拓?fù)鋬?yōu)化的主要目標(biāo)。即未來(lái)通信網(wǎng)絡(luò)的趨勢(shì)就是小世界網(wǎng)絡(luò)?？墒荌nternet網(wǎng)絡(luò)所覆蓋的范圍非常巨大，具有全球性，其拓?fù)浣Y(jié)構(gòu)的發(fā)展還面臨著許多技術(shù)上的問(wèn)題。所以，對(duì)于Internet網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的優(yōu)化目標(biāo)的實(shí)現(xiàn)有點(diǎn)不大可能。但是話又說(shuō)回來(lái)，盡管Internet的發(fā)展并不能實(shí)現(xiàn)拓?fù)湓O(shè)計(jì)的整體優(yōu)化，它的小世界、較少邊、高聚集等特性足以表明其還是具有小范圍優(yōu)化的特點(diǎn)，這些特點(diǎn)的產(chǎn)生可表現(xiàn)出其一些規(guī)律，即Internet網(wǎng)絡(luò)具有優(yōu)先連接和生長(zhǎng)的規(guī)律。生長(zhǎng)表示的是Internet具有動(dòng)態(tài)增長(zhǎng)的特性，所以Internet的拓?fù)浣Y(jié)構(gòu)也是一個(gè)動(dòng)態(tài)的過(guò)程。優(yōu)先連接規(guī)律表示新節(jié)點(diǎn)進(jìn)入Internet網(wǎng)絡(luò)的規(guī)則，即在新節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)會(huì)選擇擁有較大連接數(shù)的節(jié)點(diǎn)進(jìn)行連接。

（二）基于復(fù)雜網(wǎng)絡(luò)理論的Internet網(wǎng)絡(luò)拓?fù)淠Ｐ偷臉?gòu)建

在世人發(fā)現(xiàn)Internet網(wǎng)絡(luò)節(jié)點(diǎn)度具有冪律分布的規(guī)律之后，Internet網(wǎng)絡(luò)拓?fù)淠Ｐ偷臉?gòu)建產(chǎn)生巨大的轉(zhuǎn)變。大家更多的選擇從優(yōu)先連接和生長(zhǎng)等這一網(wǎng)絡(luò)拓?fù)湟?guī)律入手進(jìn)行Internet網(wǎng)絡(luò)的拓?fù)浣＃渲饕菫榱俗尫犀F(xiàn)實(shí)Internet拓?fù)湫再|(zhì)的模型通過(guò)一些簡(jiǎn)單規(guī)則的演化讓其自動(dòng)地產(chǎn)生出來(lái)。可利用優(yōu)先連接來(lái)對(duì)新節(jié)點(diǎn)加入網(wǎng)絡(luò)的過(guò)程進(jìn)行描述還比較粗糙，首先是因?yàn)樾鹿?jié)點(diǎn)在加入之前，對(duì)網(wǎng)絡(luò)全局的信息進(jìn)行了解和把握具有很大的難度，其次一個(gè)原因是單一的優(yōu)先連接不能夠描述復(fù)雜的加入決策過(guò)程，而且在全網(wǎng)中容易形成少量的集散節(jié)點(diǎn)。所以要建立更加符合現(xiàn)實(shí)Internet拓?fù)涮卣鞯木W(wǎng)絡(luò)模型則需要考慮更完善的加入規(guī)則。

現(xiàn)在對(duì)于構(gòu)建Internet模型主要是依據(jù)自治域級(jí)和路由器級(jí)，但由于Internet網(wǎng)絡(luò)拓?fù)涮匦栽诓煌瑢哟魏筒煌?guī)模中表現(xiàn)出某種本質(zhì)上的相似性，所以，本拓?fù)淠Ｐ偷臉?gòu)建都適應(yīng)于這兩個(gè)級(jí)。此模型主要的規(guī)則是前面提到的通過(guò)生長(zhǎng)和局部?jī)?yōu)先連接，來(lái)形成Internet拓?fù)淠Ｐ停@種形成機(jī)制就好像一個(gè)層次化比較強(qiáng)的選舉過(guò)程，如下圖所示：

此模型首先假設(shè)在一個(gè)平面中分布著n個(gè)節(jié)點(diǎn)，并存在著一個(gè)離散的均勻走動(dòng)的時(shí)鐘，這些節(jié)點(diǎn)都清楚自己是何時(shí)進(jìn)入網(wǎng)絡(luò)的，這些節(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)的時(shí)刻分布是從零時(shí)刻開(kāi)始至具體某一特定時(shí)刻內(nèi)的隨機(jī)分布。每個(gè)節(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)前后的動(dòng)作就是接收和發(fā)送消息及依據(jù)所接收的消息產(chǎn)生響應(yīng)。發(fā)送和接收的消息中包括了自己的優(yōu)先度以及消息傳達(dá)的范圍等內(nèi)容。并且這些節(jié)點(diǎn)優(yōu)先度將對(duì)其消息傳送的范圍即輻射半徑產(chǎn)生直接的影響。在節(jié)點(diǎn)接收消息之后往往是按照消息源的優(yōu)先度來(lái)確定其是否跟發(fā)送消息的節(jié)點(diǎn)建立連接，若所接收到的許多消息源節(jié)點(diǎn)存在相近的優(yōu)先度，其將會(huì)隨機(jī)地選擇一個(gè)消息源節(jié)點(diǎn)進(jìn)行連接。通過(guò)這種規(guī)則進(jìn)行不斷的演化和發(fā)展，將會(huì)得出上圖的結(jié)果。其中a圖表示Internet網(wǎng)絡(luò)形成的初始階段，那時(shí)僅僅只有一小部分節(jié)點(diǎn)進(jìn)行活動(dòng)，每個(gè)節(jié)點(diǎn)度都比較小，其發(fā)送和接收消息的范圍還比較小，所以這些節(jié)點(diǎn)往往只跟自己相鄰的節(jié)點(diǎn)進(jìn)行連接。而隨著時(shí)間的不斷推進(jìn)，節(jié)點(diǎn)度的不斷增加，各個(gè)節(jié)點(diǎn)的消息所能到達(dá)的距離越來(lái)越遠(yuǎn)，即所形成的連接會(huì)越來(lái)越大、越來(lái)越多。在局部區(qū)域勝出的節(jié)點(diǎn)代表整個(gè)區(qū)域參與更大范圍的競(jìng)爭(zhēng)，以致形成更大區(qū)域的代表。這個(gè)過(guò)程將持續(xù)下去，直到網(wǎng)絡(luò)中形成幾個(gè)較大的聚集中心。如圖（b）、（c）所示，這種自組織的層次網(wǎng)絡(luò)并不具有預(yù)先設(shè)置的層次數(shù)。這就是Internet網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的形成模型，是一種消息自組織和傳遞接收的模型。

三、結(jié)束語(yǔ)

綜上所述，復(fù)雜網(wǎng)絡(luò)理論最主要的特性是無(wú)標(biāo)度性、小世界效應(yīng)、節(jié)點(diǎn)度的冪律分布。Internet網(wǎng)絡(luò)延續(xù)著這些性質(zhì)，在其拓?fù)浣Y(jié)構(gòu)構(gòu)建和形成中表現(xiàn)出來(lái)，具體所形成的拓?fù)湟?guī)則是：Internet網(wǎng)絡(luò)中節(jié)點(diǎn)的生長(zhǎng)性和優(yōu)先連接。通過(guò)其不斷的生長(zhǎng)以及生長(zhǎng)出的節(jié)點(diǎn)的優(yōu)先連接，從而促使網(wǎng)絡(luò)拓?fù)涫且环N消息自組織和傳遞的過(guò)程。

復(fù)雜網(wǎng)絡(luò)論文:計(jì)算機(jī)網(wǎng)絡(luò)行為的復(fù)雜性理論研究

摘要：在信息時(shí)代的大背景下，計(jì)算機(jī)網(wǎng)絡(luò)行為越來(lái)越復(fù)雜，傳統(tǒng)的研究計(jì)算機(jī)網(wǎng)絡(luò)行為的方法已難適應(yīng)大規(guī)模的計(jì)算機(jī)網(wǎng)絡(luò)。為更好地管理和控制復(fù)雜的計(jì)算機(jī)網(wǎng)絡(luò)，提高網(wǎng)絡(luò)服務(wù)的質(zhì)量，將復(fù)雜性理論應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)行為的研究，探索出一種復(fù)雜網(wǎng)絡(luò)行為研究新方法。分析計(jì)算機(jī)網(wǎng)絡(luò)行為研究的傳統(tǒng)方法之不足，闡明復(fù)雜性理論應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)行為研究的有效性，并概述其發(fā)展現(xiàn)狀，以及指明其廣泛的應(yīng)用前景。

關(guān)鍵詞：計(jì)算機(jī)網(wǎng)絡(luò)；網(wǎng)絡(luò)行為；復(fù)雜性理論

一、引言

當(dāng)今的計(jì)算機(jī)網(wǎng)絡(luò)異常復(fù)雜，運(yùn)行時(shí)的動(dòng)態(tài)變化規(guī)律成超分布、超并行、超復(fù)雜性質(zhì)。計(jì)算機(jī)網(wǎng)絡(luò)行為研究的對(duì)象正是這種動(dòng)態(tài)變化規(guī)律，具體研究對(duì)象有：拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)變化、傳輸性能動(dòng)態(tài)演化、網(wǎng)絡(luò)安全、故障診斷、以及動(dòng)態(tài)網(wǎng)絡(luò)流量等。建立或優(yōu)化出具有更高性能的計(jì)算機(jī)網(wǎng)絡(luò)，在巨量用戶的情況下，依然能保證高質(zhì)量服務(wù)。故，研究計(jì)算機(jī)網(wǎng)絡(luò)行為具有重要的意義。

傳統(tǒng)的計(jì)算機(jī)網(wǎng)絡(luò)行為分析方法的基礎(chǔ)理論大多為“還原論”思想，一定程度不適合當(dāng)今復(fù)雜計(jì)算機(jī)網(wǎng)絡(luò)行為研究的發(fā)展需求。基于傳統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)行為研究方法的缺陷，將復(fù)雜性理論應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)行為研究之中，為探索復(fù)雜網(wǎng)絡(luò)行為研究方法提供新思路。復(fù)雜性理論是一種基于非線性、動(dòng)態(tài)、復(fù)雜系統(tǒng)的理論，其是解決系統(tǒng)整體性的新方法。故在研究計(jì)算機(jī)網(wǎng)絡(luò)宏觀行為特性時(shí)，復(fù)雜性理論有其巨大優(yōu)勢(shì)。

二、傳統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)行為研究

傳統(tǒng)的計(jì)算機(jī)網(wǎng)絡(luò)行為分析方法的基礎(chǔ)理論大多為“還原論”思想，一定程度不能較全面地當(dāng)今復(fù)雜計(jì)算機(jī)網(wǎng)絡(luò)行為研究的發(fā)展需求，其局限主要表現(xiàn)在以下幾個(gè)方面：

1.傳統(tǒng)的計(jì)算機(jī)網(wǎng)絡(luò)中的采樣和測(cè)量理論已不適用于現(xiàn)在復(fù)雜背景下的計(jì)算機(jī)網(wǎng)絡(luò)。

2.復(fù)雜計(jì)算機(jī)網(wǎng)絡(luò)中的宏觀可靠性的研究甚少。

3.復(fù)雜計(jì)算機(jī)網(wǎng)絡(luò)中的安全行和宏觀安全監(jiān)控理論缺乏。

4.傳統(tǒng)的陣列新能評(píng)估理論不能處理長(zhǎng)程相關(guān)條件下的性能評(píng)估。

5.復(fù)雜計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)鋱D狀態(tài)分析理論甚少。

6.復(fù)雜計(jì)算機(jī)網(wǎng)絡(luò)中時(shí)常發(fā)生異常大流量，對(duì)這種顯現(xiàn)的研究和處理理論甚少，而傳統(tǒng)的Poisson和Markov理論不能準(zhǔn)確刻畫，故，需要新的數(shù)學(xué)理論對(duì)其進(jìn)行研究。

7.研究復(fù)雜計(jì)算機(jī)網(wǎng)絡(luò)中的流量實(shí)時(shí)測(cè)量和監(jiān)控理論較少。

然而，現(xiàn)今的計(jì)算機(jī)網(wǎng)絡(luò)發(fā)展迅猛，已經(jīng)深入人們生活的各個(gè)領(lǐng)域，故，探索新的方法，來(lái)研究復(fù)雜計(jì)算機(jī)網(wǎng)絡(luò)行的方法，以提高網(wǎng)絡(luò)服務(wù)質(zhì)量，因此其具有重要的理論意義和實(shí)用價(jià)值。

三、復(fù)雜性理論

復(fù)雜性理論被譽(yù)為“二十一世紀(jì)的科學(xué)”，作為一種介于相對(duì)論和量子力學(xué)之間的新科學(xué)研究工具。

將復(fù)雜性理論應(yīng)用于現(xiàn)今的復(fù)雜計(jì)算機(jī)網(wǎng)絡(luò)行為研究之中，可從計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)的宏觀上研究和分析其網(wǎng)絡(luò)行為特性，該領(lǐng)域的研究能突破傳統(tǒng)算法的一些局限，更好地建設(shè)出和優(yōu)化現(xiàn)今的計(jì)算機(jī)網(wǎng)絡(luò)結(jié)構(gòu)，保證服務(wù)質(zhì)量。

復(fù)雜性理論主要包括：混沌學(xué)、分形學(xué)、自組織學(xué)、以及復(fù)雜網(wǎng)絡(luò)學(xué)等，是一種新型的交叉科學(xué)：

1.混沌是非線性系統(tǒng)中，貌似隨機(jī)運(yùn)動(dòng)的復(fù)雜現(xiàn)象，各個(gè)科學(xué)領(lǐng)域，包括計(jì)算機(jī)網(wǎng)絡(luò)中，存在大量的混沌現(xiàn)象，其主要特征包括有界性、遍歷性、不可預(yù)測(cè)性、分為性、普適性等。

2.分形所描述的一個(gè)粗糙或零碎的幾何形狀，可以分成多個(gè)部分，且每一部分都是體縮小尺寸的形狀，即自相似性。由于其由非線性、非平衡過(guò)程所產(chǎn)生，故其具有非周期、無(wú)規(guī)則的自相似特征。

3.自組織是一種系統(tǒng)的自我調(diào)節(jié)的過(guò)程，為整個(gè)系統(tǒng)自我生存、尋求適應(yīng)性、創(chuàng)造性的行為。各種內(nèi)在因素相互影響，使復(fù)雜系統(tǒng)能夠自動(dòng)地變換成“自組織臨界狀態(tài)”，此時(shí)，系統(tǒng)的時(shí)空動(dòng)力學(xué)行為不再具有特征時(shí)間和特征空間尺度，而是時(shí)空關(guān)聯(lián)（滿足冪定律分布），如果越過(guò)該臨界狀態(tài)，系統(tǒng)會(huì)產(chǎn)生復(fù)雜的相變現(xiàn)象。

復(fù)雜計(jì)算機(jī)網(wǎng)絡(luò)行為的復(fù)雜性是宏觀的，包括行為復(fù)雜、功能復(fù)雜、結(jié)構(gòu)復(fù)雜等各個(gè)方面。而復(fù)雜性理論的自組織性、臨界性、自相似性、非線性等鮮明特征正好符合研究復(fù)雜計(jì)算機(jī)網(wǎng)絡(luò)行為的各種特征。

四、計(jì)算機(jī)網(wǎng)絡(luò)行為的復(fù)雜性理論發(fā)展

由于復(fù)雜性理論的特性適用于研究復(fù)雜計(jì)算機(jī)網(wǎng)絡(luò)行為，故國(guó)內(nèi)外很多學(xué)者對(duì)將復(fù)雜性理論應(yīng)用于網(wǎng)絡(luò)行為研究感興趣，并取得了一些成果。

在計(jì)算機(jī)網(wǎng)絡(luò)流量行為研究方面，WE Leland等人于1994年發(fā)現(xiàn)實(shí)際的計(jì)算機(jī)網(wǎng)絡(luò)流量符合自相似特性，而并不符合傳統(tǒng)的poisson分步布，這表明傳統(tǒng)的poisson、馬爾科夫流、自回歸等分析手段不在適用，后來(lái)進(jìn)過(guò)大量學(xué)者深入研究，建立了一系列流量模型，比如報(bào)酬模型、無(wú)限源Poisson模型、MMPP模型、On/Off模型等。

在網(wǎng)絡(luò)拓?fù)湫袨檠芯糠矫妫芯砍晒砻鲗?shí)際的計(jì)算機(jī)網(wǎng)絡(luò)并不是一個(gè)隨機(jī)網(wǎng)絡(luò)系統(tǒng)，而是一種具有小世界特征和無(wú)尺度特征的復(fù)雜網(wǎng)絡(luò)，其節(jié)點(diǎn)度服從冪律分。欲研究計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)湫袨?，就必須先著手建立有效的網(wǎng)絡(luò)拓?fù)淠Ｐ?，隨著學(xué)者深入研究，提出了比如WS模型、BA模型、局部演化模型等網(wǎng)絡(luò)拓?fù)溲莼Ｐ?，及針?duì)網(wǎng)絡(luò)的魯棒和脆弱性，提出的HOT模型等。

在將混沌學(xué)引入到計(jì)算機(jī)網(wǎng)絡(luò)行為研究中的方面，研究發(fā)現(xiàn)計(jì)算機(jī)網(wǎng)絡(luò)中普遍存在一種貌似隨機(jī)的現(xiàn)象，其具有混沌的各種特性。為引導(dǎo)這種混沌現(xiàn)象向好的方面發(fā)展，學(xué)者陳關(guān)榮等人在詳細(xì)分析了計(jì)算機(jī)網(wǎng)絡(luò)流量控制系統(tǒng)中的混沌現(xiàn)象之后，將將混沌控制方法引入到網(wǎng)絡(luò)流量控制當(dāng)中，另外，國(guó)內(nèi)外一些學(xué)者探索試將混沌最大Lyapunov指數(shù)、以及相空間重構(gòu)技術(shù)引入到計(jì)算機(jī)網(wǎng)絡(luò)流量行為研究和分析領(lǐng)域，獲得了一些成果。

五、展望

將復(fù)雜性理論引入計(jì)算機(jī)網(wǎng)絡(luò)行為研究，雖然取得了豐碩的成果，但也存在一些尚待解決的問(wèn)題?，F(xiàn)今的計(jì)算機(jī)網(wǎng)絡(luò)越來(lái)越復(fù)雜、有其符合復(fù)雜性理論的特性，且復(fù)雜性理論的研究比較成熟。

在計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)錂C(jī)構(gòu)研究方面，網(wǎng)絡(luò)拓?fù)溲莼袨榫哂袆?dòng)力學(xué)、非線性、自組織性等，而將復(fù)雜性理論的自組織學(xué)、混沌學(xué)、分形學(xué)、拓?fù)鋵W(xué)等領(lǐng)域研究成果引入計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)溲芯可胁怀浞郑腋呔唧w的實(shí)際計(jì)算機(jī)網(wǎng)絡(luò)特點(diǎn)結(jié)合復(fù)雜性理論進(jìn)行研究也尚待探索。同樣，在計(jì)算機(jī)網(wǎng)絡(luò)流量行為研究方面，針對(duì)網(wǎng)絡(luò)流量的混沌、自相似等特性，結(jié)合混沌理論、分形理論等，全面闡述網(wǎng)絡(luò)流量行為的特點(diǎn)動(dòng)態(tài)變化形式，并對(duì)計(jì)算機(jī)網(wǎng)絡(luò)流量進(jìn)行有效建模，支持其特征參數(shù)，為給出有效的控制方法奠定基礎(chǔ)、以及為計(jì)算機(jī)網(wǎng)絡(luò)安全防范、穩(wěn)定運(yùn)行等方面提供理論前提。

六、結(jié)論

21世紀(jì)的信息化將給人來(lái)帶來(lái)巨大財(cái)富，計(jì)算機(jī)網(wǎng)絡(luò)行為的研究具有重要的價(jià)值，而計(jì)算機(jī)網(wǎng)絡(luò)行為研究中的復(fù)雜性理論研究將為其提供一種新方法。在此，針對(duì)實(shí)際計(jì)算機(jī)網(wǎng)絡(luò)的復(fù)雜性特點(diǎn)，總結(jié)了傳統(tǒng)網(wǎng)絡(luò)行為分析方法的缺陷，并綜述了計(jì)算機(jī)網(wǎng)絡(luò)行為研究中的復(fù)雜性理論研究現(xiàn)狀，指明其在管理和控制復(fù)雜計(jì)算機(jī)網(wǎng)絡(luò)方和提高網(wǎng)絡(luò)服務(wù)的質(zhì)量方面取得的效果，總結(jié)了復(fù)雜性理論應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)行為研究的有效性，并闡述該理論研究的重要意義，以及其廣闊的發(fā)展前景和應(yīng)用潛力。

復(fù)雜網(wǎng)絡(luò)論文:復(fù)雜網(wǎng)絡(luò)研究

摘要：從復(fù)雜網(wǎng)絡(luò)的三個(gè)主要度量特征量：平均路徑長(zhǎng)度、聚集系數(shù)、度分布的角度分別介紹了復(fù)雜網(wǎng)絡(luò)中最主要的三種網(wǎng)絡(luò)模型,即隨機(jī)網(wǎng)絡(luò)模型、小世界網(wǎng)絡(luò)模型和無(wú)標(biāo)度網(wǎng)絡(luò)模型，并提出了進(jìn)一步研究的一些方向。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；隨機(jī)網(wǎng)絡(luò)；小世界網(wǎng)絡(luò)；無(wú)標(biāo)度網(wǎng)絡(luò)

1 復(fù)雜網(wǎng)絡(luò)研究概況

近年來(lái)，國(guó)內(nèi)外掀起了研究復(fù)雜網(wǎng)絡(luò)的熱潮。復(fù)雜網(wǎng)絡(luò)之所以復(fù)雜，不僅在于網(wǎng)絡(luò)規(guī)模的巨大，網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜，而且網(wǎng)絡(luò)在時(shí)間、空間上都具有動(dòng)態(tài)復(fù)雜，網(wǎng)絡(luò)行為也很復(fù)雜。

現(xiàn)實(shí)世界中的許多系統(tǒng)都可以用復(fù)雜網(wǎng)絡(luò)來(lái)描述，如社會(huì)網(wǎng)絡(luò)中的科研合作網(wǎng)，信息網(wǎng)絡(luò)中的萬(wàn)維網(wǎng)、科研引用網(wǎng)，技術(shù)網(wǎng)絡(luò)中的因特網(wǎng)、電力網(wǎng)等。網(wǎng)絡(luò)節(jié)點(diǎn)為系統(tǒng)元素，邊為元素間的互相作用，例如，在社會(huì)網(wǎng)絡(luò)中，節(jié)點(diǎn)表示個(gè)人、組織機(jī)構(gòu)或國(guó)家，邊表示他(它)們之間的社會(huì)聯(lián)系?，F(xiàn)實(shí)網(wǎng)絡(luò)系統(tǒng)的復(fù)雜性主要體現(xiàn)在三個(gè)方面[1]：首先，網(wǎng)絡(luò)的結(jié)構(gòu)非常復(fù)雜，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)間的連接，至今仍沒(méi)有很清晰的概念;其次，網(wǎng)絡(luò)是不斷演化的，網(wǎng)絡(luò)節(jié)點(diǎn)不斷地增加，節(jié)點(diǎn)之間的連接在不斷地增長(zhǎng)，而且連接之間存在著多樣性;第三，網(wǎng)絡(luò)的動(dòng)力學(xué)具有復(fù)雜性，每個(gè)節(jié)點(diǎn)本身可以是非線性系統(tǒng)，具有分岔和混沌等非線性動(dòng)力學(xué)行為而且在不停地變化。

由于現(xiàn)實(shí)世界網(wǎng)絡(luò)的規(guī)模大，節(jié)點(diǎn)間相互作用復(fù)雜，其拓?fù)浣Y(jié)構(gòu)基本上未知或未曾探索。兩百多年來(lái)，人們對(duì)描述真實(shí)系統(tǒng)拓?fù)浣Y(jié)構(gòu)的研究經(jīng)歷了三個(gè)階段。在最初的一百多年里，科學(xué)家們認(rèn)為真實(shí)系統(tǒng)要素之間的關(guān)系可以用一些規(guī)則的結(jié)構(gòu)表示，例如二維平面上的歐幾里德格網(wǎng);從20世紀(jì)50年代末到90年代末，無(wú)明確設(shè)計(jì)原則的大規(guī)模網(wǎng)絡(luò)主要用簡(jiǎn)單而易于被多數(shù)人接受的隨機(jī)網(wǎng)絡(luò)來(lái)描述，隨機(jī)圖的思想主宰復(fù)雜網(wǎng)絡(luò)研究達(dá)四十年之久;直到最近幾年，科學(xué)家們發(fā)現(xiàn)大量的真實(shí)網(wǎng)絡(luò)既不是規(guī)則網(wǎng)絡(luò)，也不是隨機(jī)網(wǎng)絡(luò)，而是具有與前兩者皆不同的統(tǒng)計(jì)特性的網(wǎng)絡(luò)，其中最有影響的是小世界網(wǎng)絡(luò)和無(wú)標(biāo)度網(wǎng)絡(luò)。這兩種網(wǎng)絡(luò)的發(fā)現(xiàn)，掀起了復(fù)雜網(wǎng)絡(luò)的研究熱潮。

2 復(fù)雜網(wǎng)絡(luò)主要特征度量

2.1 平均路徑長(zhǎng)度(Average Path Length ,APL)

平均路徑長(zhǎng)度是網(wǎng)絡(luò)中一個(gè)重要的特征度量，它指網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間的平均最短距離。這里節(jié)點(diǎn)間的距離指的是從一節(jié)點(diǎn)到另一節(jié)點(diǎn)所要經(jīng)歷的邊的最小數(shù)目，其中所有節(jié)點(diǎn)對(duì)之間的最大距離稱為網(wǎng)絡(luò)的直徑。平均路徑長(zhǎng)度和直徑衡量的是網(wǎng)絡(luò)的傳輸性能與效率。

對(duì)于無(wú)方向無(wú)權(quán)重網(wǎng)絡(luò)，連接點(diǎn)i和點(diǎn)j的連線的數(shù)目即稱為路徑長(zhǎng)度。點(diǎn)i和點(diǎn)j之間的最短路徑是連接這兩點(diǎn)的最短的路長(zhǎng),其長(zhǎng)度是點(diǎn)i和點(diǎn)j之間的距離dij。若圖帶權(quán)重，可以使用同樣的定義，但是要考慮到權(quán)重。計(jì)算dij的平均值，稱為平均路徑長(zhǎng)度：。這樣的定義存在的問(wèn)題是如果在網(wǎng)絡(luò)中存在不連通的節(jié)點(diǎn)，則平均最短距離將發(fā)散。為此Latora和Marhciorlli[2]提出了一種稱為全局效率的相關(guān)測(cè)量量：。

2.2 聚集系數(shù)(簇系數(shù)Cluster Coefficient)

集聚系數(shù)，它衡量的是網(wǎng)絡(luò)的集團(tuán)化程度，是網(wǎng)絡(luò)的另一個(gè)重要參數(shù)。簇系數(shù)的概念有其深刻的社會(huì)根源。對(duì)社會(huì)網(wǎng)絡(luò)而言，集團(tuán)化形態(tài)是其一個(gè)重要特征，集團(tuán)表示網(wǎng)絡(luò)中的朋友圈或熟人圈，集團(tuán)中的成員往往相互熟悉，為衡量這種群集現(xiàn)象，科學(xué)家們提出了聚集系數(shù)的概念。

通常用到了兩種聚集系數(shù)。Barrat和Wegiht[3]提出了對(duì)于無(wú)向無(wú)權(quán)重的網(wǎng)絡(luò)的如下定義：C=3NA/N3 。 其中NA是網(wǎng)絡(luò)中三角形的數(shù)目，N3是三個(gè)點(diǎn)連通的數(shù)目。因子3是考慮到每個(gè)三角形可以看作是三個(gè)不同的三連通點(diǎn)。一個(gè)三角形是每對(duì)點(diǎn)之間都是有連線的三點(diǎn)集，而三連通點(diǎn)則是每個(gè)點(diǎn)都是可以從另外的點(diǎn)到達(dá)的三點(diǎn)集，這樣可以定義給定點(diǎn)i的聚集系數(shù)： 。其中NΔ(i)是包含了點(diǎn)i的三角形的數(shù)目，N3(i)是點(diǎn)i做為中心點(diǎn)的三連通節(jié)點(diǎn)的數(shù)目。若ki是節(jié)點(diǎn)i的鄰居的數(shù)目，則N3=ki(ki-1)；同樣，NΔ(i)是i點(diǎn)的鄰居之間的連線的數(shù)目，用li表示鄰居之間的連線的數(shù)目，則方程可以寫為：。

2.3 度分布(Degree Distribution)

度分布是網(wǎng)絡(luò)的一個(gè)重要統(tǒng)計(jì)特征。這里的度也稱為連通度，節(jié)點(diǎn)的度指的是與該節(jié)點(diǎn)連接的邊數(shù)。度在不同的網(wǎng)絡(luò)中所代表的含義也不同，在社會(huì)網(wǎng)絡(luò)中，度可以表示個(gè)體的影響力和重要程度，度越大的個(gè)體，其影響力就越大，在整個(gè)組織中的作用也就越大，反之亦然。度分布則表示節(jié)點(diǎn)度的概率分布函數(shù)P(k)，它指的是節(jié)點(diǎn)有k條邊連接的概率。在目前的研究中，兩種度分布較為常見(jiàn)：一是指數(shù)度分布，即P(k)隨著k的增大以指數(shù)形式衰減；另一種分布是冪律分布，即P(k)~k-γ，其中γ稱為度指數(shù)，不同γ的網(wǎng)絡(luò)，其動(dòng)力學(xué)性質(zhì)也不同。另外，度分布還有其它形式，如星型網(wǎng)絡(luò)的度分布是兩點(diǎn)分布，規(guī)則網(wǎng)絡(luò)的度分布為單點(diǎn)分布。

3 復(fù)雜網(wǎng)絡(luò)模型

3.1 隨機(jī)網(wǎng)絡(luò)模型

20世紀(jì)50年代末期，匈牙利數(shù)學(xué)家Paul Erds和Alfred Rény首次將隨機(jī)性引入網(wǎng)絡(luò)的研究，提出了著名的隨機(jī)網(wǎng)絡(luò)模型，簡(jiǎn)稱ER模型。他們指出可以用兩種方法建立隨機(jī)網(wǎng)絡(luò)一種方法是給定N個(gè)節(jié)點(diǎn)，從(N(N-1))/2條可能的邊中連接E條邊，忽略重邊情況;另一種方法是給定N個(gè)節(jié)點(diǎn)，每一對(duì)節(jié)點(diǎn)以概率p進(jìn)行連接，所得到的圖是一個(gè)隨機(jī)圖。

隨機(jī)網(wǎng)絡(luò)的基本特性可以歸納如下:

1) 隨機(jī)網(wǎng)絡(luò)的平均度為：

2) 隨機(jī)網(wǎng)絡(luò)的聚集系數(shù)：由于網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)之間的連接都是等概率的，因此對(duì)于某個(gè)節(jié)點(diǎn)i，其鄰接點(diǎn)之間連接的概率也是p，所以隨機(jī)網(wǎng)絡(luò)的簇系數(shù)

網(wǎng)絡(luò)的平均最短距離隨網(wǎng)絡(luò)規(guī)模的增加呈對(duì)數(shù)增長(zhǎng)。

3) 隨機(jī)網(wǎng)絡(luò)的平均最短距離可以進(jìn)行如下估計(jì)：考慮隨機(jī)網(wǎng)絡(luò)的平均度(k)，對(duì)于任意一個(gè)節(jié)點(diǎn)，其一階鄰接點(diǎn)的數(shù)目為(k)，二階鄰接點(diǎn)的數(shù)目為(k)2，依此類推，當(dāng)l步后達(dá)到網(wǎng)絡(luò)的總節(jié)點(diǎn)數(shù)目N，有N=N=(k)l，所以lland~lnN/ln((k))可以看出，隨機(jī)網(wǎng)絡(luò)的平均最短距離隨網(wǎng)絡(luò)規(guī)模的增加呈對(duì)數(shù)增長(zhǎng)。

4) 隨機(jī)網(wǎng)絡(luò)的度分布：給定一個(gè)連接概率為p的隨機(jī)圖，對(duì)于任意節(jié)點(diǎn)i，其度ki遵循二項(xiàng)式分布:當(dāng)網(wǎng)絡(luò)規(guī)模N很大時(shí)，網(wǎng)絡(luò)的度分布接近泊松分布，即 。由于隨機(jī)網(wǎng)絡(luò)中節(jié)點(diǎn)之間的連接是等概率的，因此大多數(shù)節(jié)點(diǎn)的度都在均值(k)附近，網(wǎng)絡(luò)中沒(méi)有度特別大的節(jié)點(diǎn).隨機(jī)網(wǎng)絡(luò)的特征是網(wǎng)絡(luò)的簇系數(shù)較小，平均最短距離也較小。

3.2 小世界網(wǎng)絡(luò)模型

1998年Watts和Strogatz[4]在ER模型基礎(chǔ)上對(duì)比真實(shí)網(wǎng)絡(luò)提出了小世界模型(WS), WS模型構(gòu)造過(guò)程如下：

1) 開(kāi)始于規(guī)則圖形。初始有數(shù)目固定的N個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有k個(gè)臨近節(jié)點(diǎn)，構(gòu)成一個(gè)規(guī)則的一維圓環(huán)。

2) 隨機(jī)化。以概率p對(duì)圓環(huán)中的每一條邊重新連接。這個(gè)過(guò)程中要求不能自身連接和重復(fù)連接。例如圖1[5]所示，p=0對(duì)應(yīng)于規(guī)則圖，p=1對(duì)應(yīng)于隨機(jī)圖；當(dāng)前研究的熱點(diǎn)是p在0到1之間的WS網(wǎng)絡(luò)的性質(zhì)。

圖1 中間為小世界模型(左圖為規(guī)則圖,右圖為隨機(jī)圖)

WS網(wǎng)絡(luò)的主要性質(zhì)為：

a) 平均路徑。圖1中被隨機(jī)選擇又重新連結(jié)后的線稱為捷徑，它對(duì)整個(gè)網(wǎng)絡(luò)的平均路徑有著很大影響。分析表明：當(dāng)p>=2/(NK)，即在保證系統(tǒng)中至少出現(xiàn)一條捷徑的情況下，系統(tǒng)的平均路徑開(kāi)始下降。即使是相當(dāng)少的捷徑也能夠顯著地減小網(wǎng)絡(luò)的平均路徑長(zhǎng)度。這是因?yàn)槊砍霈F(xiàn)一條捷徑，它對(duì)整個(gè)系統(tǒng)的影響是非線性的，它不僅影響到被這條線直接連著的兩點(diǎn)，也影響到了這兩點(diǎn)的最近鄰、次近鄰，以及次次近鄰等。

b) WS網(wǎng)絡(luò)的聚集系數(shù)。由初始固定的節(jié)點(diǎn)數(shù)可計(jì)算出P=0時(shí)規(guī)則網(wǎng)絡(luò)的集群系數(shù)為C(0), C(0)取決于網(wǎng)絡(luò)結(jié)構(gòu)而與尺寸N無(wú)關(guān)，因此有相對(duì)較大的值。隨著邊按一定的概率P隨機(jī)化，集群系數(shù)在C(0)的附近變化。

c) 度分布。WS模型是介于規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)之間的模型，P=0時(shí)規(guī)則網(wǎng)絡(luò)的度分布是中心點(diǎn)位于K=k的δ函數(shù)，P=1時(shí)隨機(jī)網(wǎng)絡(luò)是Poisson分布，在K=k點(diǎn)達(dá)到極大值。P從0變化到1的過(guò)程中，原來(lái)δ函數(shù)形式的度分布逐漸拓寬最終形成 Poisson分布。

3.3 無(wú)標(biāo)度網(wǎng)絡(luò)模型

上世紀(jì)末，Albert 等在對(duì)互聯(lián)網(wǎng)的研究中發(fā)現(xiàn)了無(wú)標(biāo)度網(wǎng)絡(luò)(scale-free network)，開(kāi)辟了人們對(duì)于復(fù)雜網(wǎng)絡(luò)系統(tǒng)認(rèn)識(shí)的新天地。他們發(fā)現(xiàn)，互聯(lián)網(wǎng)實(shí)際上是由少數(shù)高連接性的頁(yè)面組織起來(lái)的，80%以上頁(yè)面的連結(jié)數(shù)不到4 個(gè)。然而只占節(jié)點(diǎn)總數(shù)不到萬(wàn)分之一的極少數(shù)節(jié)點(diǎn)，卻有1000個(gè)以上的連結(jié)。這種網(wǎng)頁(yè)的連接分布遵循所謂的“冪次定律”：任何一個(gè)節(jié)點(diǎn)擁有k 條連接的概率，與1/ k 成正比，這就是無(wú)標(biāo)度網(wǎng)絡(luò)。其后幾年中，各行各業(yè)的研究者們?cè)谠S多不同的領(lǐng)域中，都發(fā)現(xiàn)了無(wú)標(biāo)度網(wǎng)絡(luò)。從生態(tài)系統(tǒng)到人際關(guān)系，從食物鏈到代謝系統(tǒng)，處處可以看到無(wú)標(biāo)度網(wǎng)絡(luò)。

無(wú)標(biāo)度網(wǎng)絡(luò)最顯著特征是度分布屬于冪分布。其表現(xiàn)出的特性是：大多數(shù)的節(jié)點(diǎn)只與一兩個(gè)少數(shù)節(jié)點(diǎn)相連接，但有少數(shù)節(jié)點(diǎn)卻被大量的連接。無(wú)標(biāo)度模型一般用來(lái)分析網(wǎng)絡(luò)的動(dòng)態(tài)特性，揭示大型復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。

基于“成長(zhǎng)性”和“擇優(yōu)連接”這兩種機(jī)制，Albert等在深入分析了ER 模型之后，于1999年提出了BA 模型[6-7]，從理論上解釋了無(wú)標(biāo)度網(wǎng)絡(luò)的現(xiàn)象。它比較準(zhǔn)確地把握了現(xiàn)實(shí)世界中網(wǎng)絡(luò)最基本的特點(diǎn)，較好地解釋了無(wú)標(biāo)度網(wǎng)絡(luò)的形成機(jī)制。

BA模型是第一個(gè)增長(zhǎng)的網(wǎng)絡(luò)模型，其算法如下：

1) 增長(zhǎng)：在初始時(shí)刻，假定系統(tǒng)中已有少量（m0個(gè)）節(jié)點(diǎn)，在以后的每一個(gè)時(shí)間間隔中，新增一個(gè)度為 的點(diǎn)(m≤m0)，并將這m條邊連接到網(wǎng)絡(luò)中已經(jīng)存在的m個(gè)不同的節(jié)點(diǎn)上。

2) 擇優(yōu)連接：當(dāng)在網(wǎng)絡(luò)中選擇節(jié)點(diǎn)與新增節(jié)點(diǎn)連接時(shí)，假定被選擇的節(jié)點(diǎn)v與新節(jié)點(diǎn)連接的概率?蒹(ki)和節(jié)點(diǎn) 的度成正比，即。經(jīng)過(guò)t個(gè)時(shí)間間隔后，便會(huì)形成一個(gè)有N=m0+t個(gè)節(jié)點(diǎn)、 條邊的網(wǎng)絡(luò)。圖2顯示m=m0=2時(shí)的BA模型的演化過(guò)程。初始網(wǎng)絡(luò)有兩個(gè)節(jié)點(diǎn)，每次新增加的一個(gè)節(jié)點(diǎn)按優(yōu)先連接機(jī)制與網(wǎng)絡(luò)中已存在的兩個(gè)節(jié)點(diǎn)相連。

圖2 BA模型的演化過(guò)程

a) 度分布。BA模型生成的網(wǎng)絡(luò)的度分布是無(wú)標(biāo)度的，因?yàn)榫W(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)有k條邊的概率p(k)~2m2l-3，如圖3所示。

b) 平均路徑長(zhǎng)度。BA無(wú)標(biāo)度網(wǎng)絡(luò)的平均路徑長(zhǎng)度為，這表明該網(wǎng)絡(luò)也具有小世界特性。

c) 聚類系數(shù)。BA無(wú)標(biāo)度網(wǎng)絡(luò)的聚類系數(shù)和網(wǎng)絡(luò)大小有關(guān)，近似成一種冪率分布。

4 小結(jié)與展望

綜上所述，以前，用規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)理論來(lái)描述真實(shí)系統(tǒng)的拓?fù)浣Y(jié)構(gòu)，這只反映了眾多系統(tǒng)的兩種極端情況，不能很好地描述多數(shù)現(xiàn)實(shí)系統(tǒng)。近幾年來(lái)，以小世界網(wǎng)絡(luò)與無(wú)標(biāo)度網(wǎng)絡(luò)為核心的復(fù)雜網(wǎng)絡(luò)領(lǐng)域的最新成果反映了大多數(shù)復(fù)雜系統(tǒng)的基本特性，使得對(duì)復(fù)雜系統(tǒng)建模的研究取得了實(shí)質(zhì)性的突破。復(fù)雜網(wǎng)絡(luò)的模型研究雖然己取得很大進(jìn)展，但仍然存在一些問(wèn)題。

例如，小世界效應(yīng)新的產(chǎn)生機(jī)制有待進(jìn)一步研究。以WS模型為代表的小世界網(wǎng)絡(luò)模型很好地展示了小世界的特性，但現(xiàn)實(shí)系統(tǒng)中的小世界網(wǎng)絡(luò)異常豐富，理論上，有多少種現(xiàn)實(shí)網(wǎng)絡(luò)就有多少種生成機(jī)制。因此，研究小世界網(wǎng)絡(luò)形成的新機(jī)制，揭示產(chǎn)生小世界特性的多樣性和新途徑，是十分有意義的。

另外，演化網(wǎng)絡(luò)拓?fù)涞慕馕龇椒ㄈ圆煌晟啤Ｄ壳暗亩鄶?shù)網(wǎng)絡(luò)模型是通過(guò)數(shù)值計(jì)算和近似的分析方法來(lái)建立的，即先以隨機(jī)的方式生成網(wǎng)絡(luò)，然后對(duì)度分布給出解析計(jì)算，而對(duì)其它主要參數(shù)僅給出模擬結(jié)果。由于模擬的結(jié)果帶有很大的隨機(jī)性，所以這種做對(duì)于網(wǎng)絡(luò)拓?fù)涮匦苑矫娴膰?yán)格理解還發(fā)展得遠(yuǎn)遠(yuǎn)不夠。

總之，復(fù)雜網(wǎng)絡(luò)的發(fā)展給了我們一種看待世界研究世界的新方法，隨著其研究工作的進(jìn)一步開(kāi)展，定能給我們帶來(lái)新的驚喜。

復(fù)雜網(wǎng)絡(luò)論文:利用MEX文件實(shí)現(xiàn)復(fù)雜網(wǎng)絡(luò)分形維數(shù)計(jì)算

摘要:復(fù)雜網(wǎng)絡(luò)是最近幾年流行的新興學(xué)科之一。通過(guò)復(fù)雜網(wǎng)絡(luò)的研究可以發(fā)現(xiàn)人工網(wǎng)絡(luò)和自然世界中共同存在的一些普遍特征。復(fù)雜網(wǎng)絡(luò)的分形與自相似是復(fù)雜網(wǎng)絡(luò)在演化成小網(wǎng)絡(luò)時(shí)整體和部分、部分與部分之間呈現(xiàn)出來(lái)的某種相似性,通過(guò)對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行分形維數(shù)的計(jì)算來(lái)達(dá)到探測(cè)網(wǎng)絡(luò)的微觀演化過(guò)程非常重要。本文對(duì)計(jì)算分形維數(shù)的盒子覆蓋法進(jìn)行了算法上的改進(jìn),同時(shí)在具體實(shí)現(xiàn)算法時(shí)采用了Matlab與C的接口程序C-MEX,有效地提高了運(yùn)算速度!

關(guān)鍵詞:復(fù)雜網(wǎng)絡(luò);分形維數(shù);C-MEX

隨著20世紀(jì)末Watts-Strogatz的小世界網(wǎng)絡(luò)模型和Barabasi-Albert的無(wú)尺度網(wǎng)絡(luò)模型的提出,復(fù)雜網(wǎng)絡(luò)的研究取得快速的發(fā)展。經(jīng)過(guò)十幾年的蓬勃發(fā)展,復(fù)雜網(wǎng)絡(luò)已成為最近幾年流行的新興學(xué)科之一,已不同程度的應(yīng)用于工程技術(shù)、經(jīng)濟(jì)、醫(yī)藥、生物等領(lǐng)域。

復(fù)雜網(wǎng)絡(luò)是當(dāng)前重要的一門交叉性學(xué)科,通過(guò)復(fù)雜網(wǎng)絡(luò)的研究可以發(fā)現(xiàn)自然世界和人工網(wǎng)絡(luò)中存在普遍的特征,如小世界、標(biāo)度等,從而使人們重新認(rèn)識(shí)自然世界。復(fù)雜網(wǎng)絡(luò)是從網(wǎng)絡(luò)的視角出發(fā),描述和研究的是系統(tǒng)構(gòu)件如何相互作用而導(dǎo)致系統(tǒng)的宏觀特性與行為。分形與自相似是復(fù)雜網(wǎng)絡(luò)中的一個(gè)重要特性,也是其研究的一個(gè)熱點(diǎn)之一。復(fù)雜網(wǎng)絡(luò)的分形與自相似是復(fù)雜網(wǎng)絡(luò)在演化成小網(wǎng)絡(luò)時(shí),整個(gè)過(guò)程將始終保持自己特征狀態(tài)的相對(duì)穩(wěn)定性,從而使它的整體和部分、部分與部分之間呈現(xiàn)某種相似性。在復(fù)雜網(wǎng)絡(luò)中,定量地描述這種具有自相似的網(wǎng)絡(luò)的參數(shù)就叫做復(fù)雜網(wǎng)絡(luò)的分形維數(shù)。計(jì)算分形維數(shù)最常用方法之一是盒子覆蓋法。本文對(duì)計(jì)算分形維數(shù)的盒子覆蓋法進(jìn)行了算法上的改進(jìn),同時(shí)在具體實(shí)現(xiàn)算法時(shí)采用了Matlab與C的接口程序C-MEX,有效的提高了計(jì)算速度!

1 復(fù)雜網(wǎng)絡(luò)分形維數(shù)探討

復(fù)雜網(wǎng)絡(luò)的分形與自相似性研究是利用復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)內(nèi)部的互動(dòng)性來(lái)探測(cè)網(wǎng)絡(luò)的微觀演化過(guò)程。一個(gè)復(fù)雜網(wǎng)絡(luò)具有分形性是指在對(duì)該網(wǎng)絡(luò)進(jìn)行重整化的過(guò)程中,若覆蓋整個(gè)網(wǎng)絡(luò)中的點(diǎn)所需的大小為lB的盒子的最小數(shù)量為NB,NB會(huì)隨著lB的增長(zhǎng)呈有限指數(shù)的冪律增長(zhǎng),若設(shè)冪律指數(shù)為dB,則為dB為該網(wǎng)絡(luò)的分形維數(shù)。具體滿足關(guān)系模型如式(1):

NB≈lB-dB (1)

盒子覆蓋法是計(jì)算復(fù)雜網(wǎng)絡(luò)分形維數(shù)基本的方法,是應(yīng)用合適的形式于盒子覆蓋的方式求出一個(gè)復(fù)雜網(wǎng)絡(luò)的分形維數(shù)dB。盒子覆蓋法描述為:對(duì)于一個(gè)給定的網(wǎng)絡(luò)G和盒大小lB,一個(gè)盒子是所有任意兩個(gè)節(jié)點(diǎn)i和j之間的距離lij小于lB的節(jié)點(diǎn)集合。盒子的最小數(shù)(記為NB)要能完全覆蓋整個(gè)網(wǎng)絡(luò)。以lB=1為例,那么很明顯NB就為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N。

盒覆蓋算法的最終目標(biāo)就是找到一種行之有效的方式計(jì)算在給定盒子大小lB的情況下NB的最小值。

盒子覆蓋法也有很多方法可以實(shí)現(xiàn),最常用也是最有效的是貪婪著色法,其他的也有如燃燒算法等。本文采用了最常用的貪婪著色法并對(duì)其進(jìn)行了稍微的改進(jìn)。改進(jìn)后的貪婪著色算法可以描述如下:

1) 給網(wǎng)絡(luò)中的所有節(jié)點(diǎn)分配一個(gè)唯一的從1到N的數(shù),每個(gè)節(jié)點(diǎn)并沒(méi)有著色

2) 對(duì)于所有的值lB,分配一個(gè)顏色值0給所有1到其他所有節(jié)點(diǎn),如Ci1=0

3) 將i設(shè)為2,重復(fù)下面的5個(gè)步驟直到i=N

(1) 計(jì)算從i到j(luò)的所有節(jié)點(diǎn)的小于i的距離lij

(2) 將lB設(shè)為1

(3) 對(duì)于所有的lij>=lB選擇一種沒(méi)有使用的顏色Cjlij,就可以得到對(duì)于i的給定的lB的顏色值CilB

(4) 設(shè)lB=lB+1,直到lB=lBmax

(5) i=i+1

通過(guò)以上的算法只要在復(fù)雜網(wǎng)絡(luò)中的所有節(jié)點(diǎn)游走一遍,就可以在給定盒子大小lB的情況下計(jì)算出NB的最小值,接著就可以利用關(guān)系模型公式求出該網(wǎng)絡(luò)的分形維數(shù)dB了。

2 利用CMEX文件計(jì)算復(fù)雜網(wǎng)絡(luò)分形維數(shù)

根據(jù)以上的算法描述,我們用matlab具體實(shí)現(xiàn)了這個(gè)算法。但我們?cè)诰唧w實(shí)現(xiàn)的過(guò)程中,發(fā)現(xiàn)由于復(fù)雜網(wǎng)絡(luò)中的數(shù)據(jù)量非常大,而且MATLAB又是一種解釋性語(yǔ)言,在執(zhí)行M文件時(shí),需要對(duì)矩陣的每個(gè)元素循環(huán)處理,運(yùn)算速度非常的緩慢,例如利用MATLAB實(shí)現(xiàn)上述算法時(shí)僅僅調(diào)用一個(gè)20萬(wàn)行的數(shù)據(jù),就需要執(zhí)行30幾分鐘。

對(duì)于Matlab直接計(jì)算中存在的困難,我們考慮過(guò)從更換編程平臺(tái),但由于matlab一些優(yōu)秀的特性,我們還是希望能用matlab軟件來(lái)實(shí)現(xiàn)上述算法。這使我們把目光投向了CMEX混合編程。

MEX文件又稱為外部程序調(diào)用接口,在進(jìn)行大規(guī)模的數(shù)據(jù)處理,比如影響 MATLAB執(zhí)行速度的循環(huán)體時(shí),可以編寫相應(yīng)的C或C ++子程序完成相同的功能,并編譯成 MEX文件,再由MATLAB調(diào)用此MEX文件以提高運(yùn)行速度。

C-MEX是通過(guò)MATLAB的編譯器轉(zhuǎn)換為可執(zhí)行文件,是按照MEX技術(shù)要求的格式編寫相應(yīng)的程序,通過(guò)編譯連接,生成擴(kuò)展名為.dll的動(dòng)態(tài)鏈接庫(kù)文件,可以在MATLAB環(huán)境下以函數(shù)的形式直接調(diào)用。一般來(lái)說(shuō),C-MEX 文件的執(zhí)行速度是相同功能的M文件執(zhí)行速率的20~40倍。

MEX文件主要由兩部分組成,它們分工明確,分別用于完成不同的任務(wù)。第一部分稱為計(jì)算功能子程,它包含了所有實(shí)際完成計(jì)算功能的源代碼,用來(lái)完成實(shí)際的計(jì)算工作。第二部分稱為入口子程序,它是計(jì)算子例行程序同MATLAB環(huán)境之間的接口,其作用是在 MATLAB系統(tǒng)與被調(diào)用的外部子程序之間建立通信聯(lián)系。其中入口子程序的名字為mexFunction,其構(gòu)成形式為:void mexFunction(int nlhs,mxA rray 3 plhs[],int nrhs,constmxA rray 3 p rhs[])。其中:nlhsnrhs為整型,分別表示輸出輸入變量的個(gè)數(shù);plhs[]p rhs[]為mxA rray型指針數(shù)組,分別表示輸出輸入變量的地址。MEX文件執(zhí)行流程可用圖1表示。

針對(duì)于盒子覆蓋法中的貪婪著色算法,我們也利用MEX文件編程實(shí)現(xiàn)了此算法來(lái)對(duì)復(fù)雜網(wǎng)絡(luò)分形維數(shù)進(jìn)行計(jì)算。具體利用C―MEX計(jì)算復(fù)雜網(wǎng)絡(luò)分形維數(shù)的過(guò)程如下:

(1) 我們先根據(jù)貪婪著色算法描述,用matlab的M文件實(shí)現(xiàn)

(2) 找出M文件中循環(huán)次數(shù)較多的代碼段

(3) 將這些循環(huán)次數(shù)較多的代碼段轉(zhuǎn)化成相應(yīng)的C-MEX程序,并編譯成相應(yīng)的.dll文件

(4) 將M文件中循環(huán)次數(shù)較多的代碼段用相應(yīng)的.dll代替

(5) 最后對(duì)修改后的程序編譯執(zhí)行

最后我們?cè)贑PU為AMD Athlon(tm) 64 X2 Dual Core Processor 4000+,內(nèi)存為1G的機(jī)器上,分別對(duì)利用M文件和C-MEX文件兩種方式調(diào)用了三組數(shù)據(jù)量不同的數(shù)據(jù),得出的實(shí)驗(yàn)結(jié)果如表1所示。

從表1的結(jié)果,我們可以看到使用C-MEX混合編程后,實(shí)現(xiàn)復(fù)雜網(wǎng)絡(luò)分形維數(shù)計(jì)算算法的執(zhí)行時(shí)間得到了很大程度的提高。這也證明了我們所采用的方法是行之有效的。

3 結(jié)論

復(fù)雜網(wǎng)絡(luò)作為一門重要的交叉性學(xué)科,通過(guò)復(fù)雜網(wǎng)絡(luò)的研究可以發(fā)現(xiàn)人工網(wǎng)絡(luò)和自然世界中存在普遍相似的特征,從而使人們重新認(rèn)識(shí)自然世界的一些特性。通過(guò)研究復(fù)雜網(wǎng)絡(luò)的分形維數(shù),除了探究復(fù)雜網(wǎng)絡(luò)中相似網(wǎng)絡(luò)的維數(shù),還可以探測(cè)網(wǎng)絡(luò)的微觀演化。本文對(duì)復(fù)雜網(wǎng)絡(luò)的分形維數(shù)計(jì)算算法進(jìn)行了探討,并利用C-MEX混合編程的方式實(shí)現(xiàn)了此算法,極大地提高了運(yùn)算速度。

復(fù)雜網(wǎng)絡(luò)論文:基因表達(dá)譜的復(fù)雜網(wǎng)絡(luò)研究

摘要：該文采用復(fù)雜網(wǎng)絡(luò)理論。首先利用分類信息指數(shù)對(duì)數(shù)據(jù)進(jìn)行初步篩選，選出了314個(gè)基因。對(duì)選出的基因分別做腫瘤樣本和正常樣本的相關(guān)系數(shù)矩陣，利用Kruskal算法分別對(duì)兩個(gè)相關(guān)系數(shù)矩陣做最小生成樹(shù)，然后通過(guò)比較選出閾值，建立起節(jié)點(diǎn)間的連邊關(guān)系，得到致病前后的兩個(gè)網(wǎng)絡(luò)。根據(jù)復(fù)雜網(wǎng)絡(luò)中的相關(guān)理論，分別對(duì)腫瘤樣本和正常樣本進(jìn)行社區(qū)劃分，最后通過(guò)觀察兩個(gè)樣本的網(wǎng)絡(luò)系統(tǒng)，分析致病前后基因的變化情況，建議了結(jié)腸癌的特征基因。

關(guān)鍵詞：基因芯片；基因表達(dá)譜；社區(qū)結(jié)構(gòu)；分類信息指數(shù)；最小生成樹(shù)；閾值；復(fù)雜網(wǎng)絡(luò)

癌癥起源于正常組織在物理或化學(xué)致癌物的誘導(dǎo)下，基因組發(fā)生的突變，即基因在結(jié)構(gòu)上發(fā)生堿基對(duì)的組成或排列順序的改變，因而改變了基因原來(lái)的正常分布（即所包含基因的種類和各類基因以該基因轉(zhuǎn)錄的mRNA的多少來(lái)衡量的表達(dá)水平）。所以探討基因分布的改變與癌癥發(fā)生之間的關(guān)系具有深遠(yuǎn)的意義。

復(fù)雜網(wǎng)絡(luò)理論是近年來(lái)發(fā)展起來(lái)的一個(gè)重要的交叉。對(duì)于一個(gè)復(fù)雜的系統(tǒng)，很多時(shí)候我們不能夠單獨(dú)通過(guò)分析系統(tǒng)內(nèi)元組來(lái)反應(yīng)系統(tǒng)性質(zhì)。復(fù)雜系統(tǒng)是由微觀層次上的海量個(gè)體所組成，個(gè)體之間存在著作用。把個(gè)體抽象為網(wǎng)絡(luò)節(jié)點(diǎn)，而個(gè)體之間的相互作用抽象為節(jié)點(diǎn)之間的邊，則復(fù)雜系統(tǒng)就可以用一個(gè)復(fù)雜網(wǎng)絡(luò)來(lái)描述。

本文的實(shí)驗(yàn)數(shù)據(jù)集包含22 個(gè)正常組織樣本和40個(gè)結(jié)腸癌組織樣本，每個(gè)樣本包含 2000個(gè)基因的表達(dá)數(shù)據(jù)。首先對(duì)樣本數(shù)據(jù)進(jìn)行歸一化，另外，數(shù)據(jù)的特征維數(shù)2000，遠(yuǎn)遠(yuǎn)高于樣本個(gè)數(shù)62。因此，有必要對(duì)數(shù)據(jù)進(jìn)行過(guò)濾和降維。我們采用了分類信息指數(shù)方法 (information index to classification, ⅡC)[2]，公式為：

其中，μ1(i)，μ2(i)分別表示第i個(gè)基因在正常組織樣本和結(jié)腸癌組織樣本中的中表達(dá)水平的均值；σ12(i)，σ22(i)分別為該基因表達(dá)水平的標(biāo)準(zhǔn)差。

根據(jù)上式計(jì)算結(jié)腸癌基因表達(dá)數(shù)據(jù)中的2000個(gè)基因的分類信息指數(shù)，大部分基因的分類信息指數(shù)在0到0.2之間，僅有少部分基因的大于 0.2（如圖1）。保留指數(shù)大于 0.2 的314個(gè)基因用于下一步的分析，這樣就大大縮小了基因選擇的特征空間，剔除掉大量“無(wú)關(guān)基因”，大大縮小需要搜索的致癌基因范圍。

另外在撰寫本文的準(zhǔn)備過(guò)程中，我們查閱了大量的有關(guān)文獻(xiàn)。與已有文獻(xiàn)的結(jié)果進(jìn)行比較，發(fā)現(xiàn)所選特征基因中包含了一些已被實(shí)驗(yàn)證實(shí)的與癌癥相關(guān)的重要基因，這些基因在癌癥基因調(diào)控網(wǎng)絡(luò)中起關(guān)鍵作用，一共得到了40個(gè)基因（如表1）。我們要探尋的結(jié)腸癌的特征基因極有可能包含在這40個(gè)基因中，這對(duì)我們后續(xù)的研究具有重要的參考價(jià)值。其中6個(gè)基因在我們根據(jù)分類信息指數(shù)值對(duì)數(shù)據(jù)進(jìn)行篩選的過(guò)程中被剔除了。所以我們選擇剩下的34個(gè)基因作為我們研究的參考（如表1）。

然后分別計(jì)算結(jié)腸癌樣本(cancer)和正常樣本(normal)各個(gè)基因間的相似性，得到相似矩陣。分析這些基因點(diǎn)的聯(lián)系，選擇一個(gè)相似性的閾值來(lái)分別建立復(fù)雜網(wǎng)絡(luò)，用鄰接矩陣表示。（如果相似性大于該閾值的則這兩個(gè)點(diǎn)相連接，在鄰階矩陣中用1表示；反之，如果相似性小于于該閾值的則這兩個(gè)點(diǎn)不連接，在鄰階矩陣中用0表示）。其中關(guān)鍵的步驟是閾值的選取。本文提出的解決策略是，從關(guān)聯(lián)系數(shù)矩陣得到最小生成樹(shù)作為基因之間關(guān)系的骨架，然后再把文獻(xiàn)中發(fā)現(xiàn)的相關(guān)基因之間的關(guān)系考慮進(jìn)來(lái)，得到客觀的閾值。

我們考查結(jié)腸癌基因表達(dá)數(shù)據(jù)中篩選出來(lái)的314個(gè)變化比較明顯的基因，用向量組表示為，

其中T0m,n是第n個(gè)基因在第m個(gè)樣本的基因數(shù)據(jù)，其中N=314，M是樣本個(gè)數(shù)，正常組織樣本個(gè)數(shù)為22，腫瘤組織樣本個(gè)數(shù)為40。相關(guān)系數(shù)矩陣為R：

那么基因間的歐幾里得距離就可以用以下定義的距離矩陣D定量描述：

最小生成樹(shù)是圖論中的基本概念。我們從距離矩陣中抽取出最小生成樹(shù)，用N-1條邊連接所有基因節(jié)點(diǎn)，形成一個(gè)無(wú)圈圖。在形成的最小生成樹(shù)中，要保證所有基因間的距離之和最小，也即相關(guān)系數(shù)之和最大，且是無(wú)圈圖。那么，基因間的其它關(guān)系就被過(guò)濾掉了。原則上來(lái)講，真正直接相關(guān)的基因之間的關(guān)聯(lián)系數(shù)最大，因此可以認(rèn)為最小生成樹(shù)保留了基因之間的真正關(guān)系。因?yàn)橐粋€(gè)基因可以和多個(gè)基因直接相關(guān)，所以很多的關(guān)系被丟掉。丟掉的關(guān)系將在后邊的步驟中被找回。我們采用Kruskal算法來(lái)生成最小生成樹(shù)：

我們用篩選后的314個(gè)基因數(shù)據(jù)（我們對(duì)這314個(gè)基因重新做了編號(hào)，其與原數(shù)據(jù)庫(kù)中的編號(hào)的對(duì)應(yīng)表見(jiàn)附表），對(duì)結(jié)腸癌樣本、正常樣本分別用兩種方法得到了最小生成樹(shù)。兩個(gè)最小生成樹(shù)的節(jié)點(diǎn)也即基因，一定是相同的，且都有314個(gè)節(jié)點(diǎn)，313條邊。圖2給出了正常樣本中得到的最小生成樹(shù)。

如前所述，最小生成樹(shù)給出了基因之間的部分連接，但是很多基因之間的關(guān)系被丟掉。另一方面，文獻(xiàn)中發(fā)現(xiàn)的結(jié)腸癌相關(guān)基因，為我們提供了重要的參考信息，但是這些信息包含著很大的偶然性，也就是噪聲。在此我們將把這兩部分信息整合在一起，得到一個(gè)客觀的構(gòu)建基因關(guān)系網(wǎng)絡(luò)的閾值。

我們首先抽取出如圖2所示的生成樹(shù)。它給我們提供了高可信度的鏈接，不足之處是包含的信息不夠多，一些重要的關(guān)系被忽略了。我們?cè)俑鶕?jù)得病前后兩類樣本信息變化。然而，這里也可能產(chǎn)生噪聲邊。

從上面得到最小生成樹(shù)出發(fā)。整合相關(guān)文獻(xiàn)中已知的腫瘤致病基因，我們收集到34個(gè)這樣的基因。用這34個(gè)基因重復(fù)上面的過(guò)程，得到閾值，腫瘤樣本的記為DDIImin，在正常樣本的生成樹(shù)中記為DNIImin建立網(wǎng)絡(luò)。，它們之間可能直接相連，也可能彼此沒(méi)有直接相連。計(jì)算直接相連的節(jié)點(diǎn)間的距離。在這個(gè)過(guò)程中，我們選取最大的那個(gè)作為閾值，在腫瘤樣本生成樹(shù)中記為DDIImin=0.6239，在正常樣本的生成樹(shù)中記為DNIImin=0.6995。

我們選取DDIImin，DNIImin作為閾值，來(lái)建立網(wǎng)絡(luò)。這樣在一定程度上減少了一些噪聲邊的產(chǎn)生，避免了偶然因素可能引起的閾值選取的不穩(wěn)定性，同時(shí)也恢復(fù)了我們需要的連接。

腫瘤樣本網(wǎng)絡(luò)以及正常樣本網(wǎng)絡(luò)的閾值選定后，利用我們?cè)跀?shù)據(jù)處理中選定的314個(gè)基因建立網(wǎng)絡(luò)。以腫瘤樣本網(wǎng)絡(luò)為例，先算出腫瘤樣本中這314個(gè)基因的相關(guān)系數(shù)矩陣。當(dāng)任意兩個(gè)基因的相關(guān)系數(shù)大于閾值0.6239時(shí)，我們就認(rèn)為這兩個(gè)基因是有相互作用的，在它們之間畫一條邊；當(dāng)任意兩個(gè)基因的相關(guān)系數(shù)小于閾值0.6239時(shí)，我們就認(rèn)為這兩個(gè)基因是沒(méi)有相互作用的，它們之間就沒(méi)有直接的邊相連。這樣我們就得到了腫瘤樣本的基因相互作用網(wǎng)絡(luò)。在相關(guān)系數(shù)矩陣中，把大于0.6239的值改為1，小于0.6239的改為0，主對(duì)角線上元素設(shè)為0，這樣就由相關(guān)系數(shù)矩陣得到了鄰接矩陣MD。鄰接矩陣中的1就表示網(wǎng)絡(luò)中有連邊；鄰接矩陣中的0就表示網(wǎng)絡(luò)中沒(méi)有連邊。

復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)是不均勻的，往往存在很多連接致密的集團(tuán)，在這些集團(tuán)之間只有很少邊形成的松散的連接。這些致密的結(jié)構(gòu)往往與功能有著密切的關(guān)系，因此受到普遍的關(guān)注。當(dāng)前普遍采用的劃分社區(qū)的方法是Newman-Girvan算法。

社區(qū)劃分反映基因間的功能關(guān)系，而在網(wǎng)絡(luò)模塊中，可以發(fā)現(xiàn)網(wǎng)絡(luò)發(fā)生了明顯的改變。首先我們畫出正常樣本網(wǎng)絡(luò)，用Newman-Girvan的劃分算法對(duì)得到的網(wǎng)絡(luò)進(jìn)行分塊。當(dāng)把正常樣本網(wǎng)分成14個(gè)社區(qū)時(shí)，得到的聚類系數(shù)最大，為Q=0.596（如表2），這樣就把網(wǎng)絡(luò)分成了14個(gè)大的功能模塊。如圖3所示，即為正常樣本網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)（每種顏色代表一個(gè)社區(qū)）?？梢钥闯觯鱾€(gè)社區(qū)結(jié)構(gòu)中的節(jié)點(diǎn)數(shù)目分布并不均勻，并且存在很多孤立節(jié)點(diǎn)。社區(qū)內(nèi)節(jié)點(diǎn)間的連接比較緊密，而不同社區(qū)間的連接比較稀疏。

同樣用Newman-Girvan的劃分算法，我們畫出腫瘤樣本的網(wǎng)絡(luò)，把腫瘤樣本網(wǎng)分成了13社區(qū)（如圖4）。此時(shí)得到的聚類系數(shù)最大，為Q=0.630（如表3）?？梢钥闯?，腫瘤樣本網(wǎng)絡(luò)的各個(gè)社區(qū)結(jié)構(gòu)中的節(jié)點(diǎn)數(shù)目分布也是并不均勻，并且同樣存在很多孤立節(jié)點(diǎn)。社區(qū)內(nèi)節(jié)點(diǎn)間的連接比較緊密，而不同社區(qū)間的連接比較稀少。

對(duì)于兩個(gè)網(wǎng)絡(luò)，我們計(jì)算出每個(gè)節(jié)點(diǎn)的度（degree）。我們發(fā)現(xiàn)，，，其中DDmax、DNmax分別表示腫瘤樣本、正常樣本的鄰接矩陣中節(jié)點(diǎn)的最大度，DDmin、DNmin分別表示腫瘤樣本、正常樣本的鄰接矩陣中節(jié)點(diǎn)的最小度。說(shuō)明網(wǎng)絡(luò)中的有些點(diǎn)與其他點(diǎn)的相互作用強(qiáng)度發(fā)生了明顯的變化。反應(yīng)到網(wǎng)絡(luò)結(jié)構(gòu)中，可以用平均度加以粗略說(shuō)明，其中腫瘤樣本網(wǎng)絡(luò)的平均度為9.36，正常樣本網(wǎng)絡(luò)的平均度為5.28。在腫瘤樣本網(wǎng)絡(luò)中每個(gè)基因平均與周圍9.36個(gè)基因有相互作用，在正常樣本網(wǎng)中每個(gè)基因平均與周圍5.28個(gè)基因有相互作用。

分析度的變化。通過(guò)兩個(gè)網(wǎng)絡(luò)的度序列做差，我們就能夠找到每個(gè)節(jié)點(diǎn)度的變化情況。表4即為度變化比較大的前十個(gè)節(jié)點(diǎn)。

同時(shí)我們對(duì)每個(gè)節(jié)點(diǎn)度的變化值做平均，得到度變化的平均值為7.0637。其中大于這個(gè)平均變化度的節(jié)點(diǎn)有89個(gè)，小于這個(gè)平均變化度的節(jié)點(diǎn)有255個(gè)。

我們認(rèn)為特征基因在這些度變化比較大的節(jié)點(diǎn)中的可能性很大。度變化超過(guò)平均值的節(jié)點(diǎn)與我們查閱的的文獻(xiàn)中得出個(gè)34個(gè)特征基因相比對(duì)，其中有15個(gè)基因是它們所共同擁有的（如表5），我們認(rèn)為這15個(gè)基因應(yīng)該是對(duì)我們尋找結(jié)腸癌特征基因非常重要的基因。

接下來(lái)對(duì)我們得到了15個(gè)重要的基因節(jié)點(diǎn)，在網(wǎng)絡(luò)中分析它們。在上一步過(guò)程中，我們比較了文獻(xiàn)中得出的，且度變化較大的15個(gè)重要節(jié)點(diǎn)。這15個(gè)基因在腫瘤特征過(guò)程中起了很重要的作用。注意到我們選取的這15個(gè)基因最大的度變化值是33，但還有7個(gè)節(jié)點(diǎn)的度變化值超過(guò)了33，卻并不在我們查閱的文獻(xiàn)的結(jié)論中，我們認(rèn)為有必要在網(wǎng)絡(luò)中進(jìn)一步對(duì)這些點(diǎn)進(jìn)行分析。這7個(gè)基因節(jié)點(diǎn)分別是（如表6）：

表6

其中，度變化是同一節(jié)點(diǎn)在腫瘤樣本網(wǎng)絡(luò)與正常樣本網(wǎng)絡(luò)中，該節(jié)點(diǎn)在兩個(gè)網(wǎng)絡(luò)中度的變化值；分類信息指數(shù)編號(hào)是指該信息指數(shù)在所有信息指數(shù)中從大到小排列時(shí)的次序，我們選取的314個(gè)基因是分類信息指數(shù)IIC＞0.2的基因，也即分類信息指數(shù)編號(hào)前314個(gè)基因。通過(guò)上面的表格我們可以看出，這些基因的分類信息指數(shù)都比較大。通常地，樣本們會(huì)去研究IIC大的點(diǎn)，分類信息指數(shù)編號(hào)偏后的那些基因極易在分析的過(guò)程中被忽略掉?，F(xiàn)在我們發(fā)現(xiàn)，這些點(diǎn)在兩個(gè)網(wǎng)絡(luò)中度的變化值很大，也即癌變前后這些基因在網(wǎng)絡(luò)中與其它基因的相互作用有了很大的變化。接下來(lái)，我們將這7個(gè)基因和另外15個(gè)基因分別放回正常樣本和腫瘤樣本的網(wǎng)絡(luò)中去分析它們的變化。如圖5，圖6。

圖5為我們找到的15個(gè)重要基因在正常樣本中的相對(duì)位置。不同的顏色表示不同的社區(qū)。同時(shí)把度變化最大的7個(gè)節(jié)點(diǎn)（156，87，300，139，169，61，34）也放進(jìn)了網(wǎng)絡(luò)中。

圖6為我們找到的15個(gè)重要基因在腫瘤樣本中的相對(duì)位置。不同的顏色表示不同的社區(qū)。同時(shí)把度變化最大的7個(gè)節(jié)點(diǎn)（156，87，300，139，169，61，34）也放進(jìn)了網(wǎng)絡(luò)中。

從圖5中可以觀察出，在正常樣本網(wǎng)絡(luò)中，度變化最大的7個(gè)節(jié)點(diǎn)分別分布在4個(gè)社區(qū)中，且僅有一個(gè)節(jié)點(diǎn)與其它節(jié)點(diǎn)相連（節(jié)點(diǎn)61―節(jié)點(diǎn)68）。這說(shuō)明7個(gè)節(jié)點(diǎn)在正常樣本網(wǎng)絡(luò)中沒(méi)有明顯的相互作用。而通過(guò)觀察圖6，我們的發(fā)現(xiàn)在腫瘤樣本網(wǎng)絡(luò)中，度變化最大的7個(gè)節(jié)點(diǎn)同時(shí)分布在同一個(gè)社區(qū)中，且這7個(gè)節(jié)點(diǎn)與我們找到的15個(gè)重要基因節(jié)點(diǎn)中的9個(gè)節(jié)點(diǎn)（分別為68、180、155、270、213、198、207、2、297）也在同一社區(qū)中（圖6中藍(lán)色表示的社區(qū)），并相連。我們有一個(gè)大膽的猜想，結(jié)腸癌的特征基因就分布在藍(lán)色所表示的社區(qū)中。藍(lán)色社區(qū)中的這16個(gè)節(jié)點(diǎn)所代表的基因分別為M22382，T96873，U09564，H08393，J02854，T62947，M59040，H20709，X62048，及M94556，T70062，L28010，M37583，H89087，H64807，T65740，從功能上看，這些基因?qū)Y(jié)腸癌的癌變過(guò)程發(fā)揮了重要的作用。在正常樣本網(wǎng)絡(luò)中，這些點(diǎn)分布的比較分散，而在腫瘤樣本網(wǎng)絡(luò)中，這些點(diǎn)集中到了同一社區(qū)中，說(shuō)明癌變后這些基因之間的相互作用加強(qiáng)。所以這16個(gè)基因就是我們要尋找的結(jié)腸癌的特征基因。另外，除了這些在同一社區(qū)的節(jié)點(diǎn)之外，還有一些散節(jié)點(diǎn)落在各個(gè)不同的社區(qū)中，其中分為兩種情況，一種是該基因位于兩個(gè)社區(qū)的連接點(diǎn)處，如節(jié)點(diǎn)58（T60155），它是主動(dòng)脈平滑肌肌動(dòng)蛋白，而有研究表明肌動(dòng)蛋白參與DNA轉(zhuǎn)錄，所以T60155是我們所尋找的結(jié)腸癌的特征基因。另一種是某社區(qū)內(nèi)部的節(jié)點(diǎn)，如節(jié)點(diǎn)83（T51571）,130（H43887），219（L41559）,248（M36634），參照這些基因的功能對(duì)基因的癌變并沒(méi)有起到?jīng)Q定性的作用。并且這幾個(gè)點(diǎn)的度變化值也不是很大，所以，可能是被誤選入的，應(yīng)該被排除掉。綜上，本文運(yùn)用復(fù)雜網(wǎng)絡(luò)的方法，通過(guò)社區(qū)模塊的劃分，找出17個(gè)結(jié)腸癌的特征基因。

本文首先通過(guò)分類信息指數(shù)這一指標(biāo)對(duì)數(shù)據(jù)做了初步處理，篩選出314個(gè)基因節(jié)點(diǎn)，剔除了大量的無(wú)關(guān)基因，對(duì)數(shù)據(jù)進(jìn)行過(guò)濾和降維。并以此分別構(gòu)建網(wǎng)絡(luò)模型。生成網(wǎng)絡(luò)之后，通過(guò)Newman-Girvan方法對(duì)我們的網(wǎng)絡(luò)模型劃分社區(qū)和評(píng)價(jià)，無(wú)論是腫瘤樣本網(wǎng)絡(luò)還是正常樣本網(wǎng)絡(luò)都是很好的社區(qū)結(jié)構(gòu)。我們利用度變化值和參考我們查閱文獻(xiàn)中得出的結(jié)論，挑選出了22個(gè)基因，其中排除掉5個(gè)基因后，得出了我們的結(jié)論，即結(jié)腸癌的特征基因有17個(gè)。

本文問(wèn)題研究還有待于進(jìn)一步加深完善，比如沒(méi)有考慮到基因篩選后提出的變化不大的點(diǎn)。另外，我們對(duì)于生物醫(yī)學(xué)方面的專業(yè)知識(shí)比較欠缺，在對(duì)模塊進(jìn)行分析的時(shí)候，對(duì)模塊的功能分析不夠精確。這需要我們以后的繼續(xù)努力和學(xué)習(xí)。

復(fù)雜網(wǎng)絡(luò)論文:復(fù)雜金融網(wǎng)絡(luò)的自相似性研究

摘要：以股票為節(jié)點(diǎn)，選取適當(dāng)閾值量化股票收益率序列間相關(guān)關(guān)系從而構(gòu)建復(fù)雜金融網(wǎng)絡(luò)?；趶?fù)雜網(wǎng)絡(luò)的理論，討論金融網(wǎng)絡(luò)的度分布、平均最短路徑和聚集系數(shù)，發(fā)現(xiàn)面向金融時(shí)間序列的股票網(wǎng)絡(luò)具有小世界效應(yīng)，無(wú)標(biāo)度特性和一個(gè)很重要的特性―自相似性。該文用兩種方法分析了網(wǎng)絡(luò)的自相似性：一是提出用網(wǎng)絡(luò)節(jié)點(diǎn)的度構(gòu)造Hurst指數(shù)，定量分析金融網(wǎng)絡(luò)的自相似性；二是金融網(wǎng)絡(luò)的平均路徑長(zhǎng)度和聚集系數(shù)定性地分析了復(fù)雜網(wǎng)絡(luò)的自相似性。

關(guān)鍵詞：金融市場(chǎng)；復(fù)雜網(wǎng)絡(luò)；無(wú)標(biāo)度；自相似

證券市場(chǎng)素有經(jīng)濟(jì)晴雨表之稱。證券市場(chǎng)由于受企業(yè)經(jīng)濟(jì)效益，居民收入水平，投資者的心態(tài)等諸多因素影響，所以它是一個(gè)涵蓋大量信息的復(fù)雜系統(tǒng)。近年來(lái)以復(fù)雜網(wǎng)絡(luò)角度理解和分析證券市場(chǎng)，構(gòu)建金融網(wǎng)絡(luò)的方法層出不窮。Boginski [1]等研究了美國(guó)證券市場(chǎng)6546支股票，發(fā)現(xiàn)股票相關(guān)性呈現(xiàn)無(wú)標(biāo)度性。莊新田[2]等基于相關(guān)系數(shù)構(gòu)建以上海證券交易所持續(xù)交易的股票為節(jié)點(diǎn)的復(fù)雜網(wǎng)絡(luò)，討論上海證券市場(chǎng)的股票價(jià)格波動(dòng)，魯巍巍[3]等對(duì)滬深A(yù)股構(gòu)建復(fù)雜網(wǎng)絡(luò)，計(jì)算網(wǎng)絡(luò)的聚集系數(shù)，吸引率，討論不同行業(yè)的聚合強(qiáng)度及其對(duì)滬深A(yù)股市場(chǎng)股價(jià)波動(dòng)的影響，這些研究都是基于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征：節(jié)點(diǎn)度分布、平均路徑長(zhǎng)度、聚集系數(shù)、吸收率等，都從網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的影響程度方面考慮，對(duì)于復(fù)雜金融網(wǎng)絡(luò)的另一特性――自相似性并無(wú)研究。

復(fù)雜網(wǎng)絡(luò)的自相似性是指網(wǎng)絡(luò)局部和整體在某些特征上相似。對(duì)于固定網(wǎng)絡(luò)自相似性的研究一般是利用節(jié)點(diǎn)內(nèi)部互動(dòng)性來(lái)探測(cè)網(wǎng)絡(luò)的演化過(guò)程。自相似系數(shù)的測(cè)量方法是由 C.M.Song與S.Havlin[4]提出利用重構(gòu)化測(cè)量，以及R.Guimera,L.Danon[5]提出利用郵件系統(tǒng)測(cè)量社區(qū)結(jié)構(gòu)的相似性，他們也用這些方法描述了一些現(xiàn)實(shí)網(wǎng)絡(luò)的自相似性[4]。

1 復(fù)雜金融網(wǎng)絡(luò)建模

1.1 數(shù)據(jù)來(lái)源

筆者隨機(jī)抽取從2007年9月28日至2010年2月26日滬深A(yù)股的500只股票作為研究對(duì)象。根據(jù)每只股票月數(shù)據(jù)的開(kāi)盤價(jià)、收盤價(jià)、最高價(jià)和最低價(jià)平均值計(jì)算股票的對(duì)數(shù)收益率，然后用對(duì)數(shù)收益率序列建立相關(guān)關(guān)系，通過(guò)相關(guān)關(guān)系數(shù)值化研究復(fù)雜金融網(wǎng)絡(luò)的拓?fù)涮卣鱗6]。

1.2 復(fù)雜金融網(wǎng)絡(luò)建模

以滬深A(yù)股為節(jié)點(diǎn)，股票相互影響關(guān)系為連邊構(gòu)建無(wú)權(quán)無(wú)向網(wǎng)絡(luò)。設(shè)股票i在第t時(shí)刻的平均價(jià)為xi(t)，xi(t)為股票i在t時(shí)刻開(kāi)盤價(jià)，收盤價(jià)，最高價(jià)和最低價(jià)的平均值。

為股票i對(duì)數(shù)收益率。定義股票i和股票j的相關(guān)系數(shù)為：

其中E(yi)表示股票i在n期的平均收益率，

由定義知：ρij的值域?yàn)閇-1，1]。若ρij=1，表示股票i和股票j完全正相關(guān)，表現(xiàn)為同向增長(zhǎng)或降落；若ρij=－1，表示股票i和股票j完全負(fù)相關(guān)，表現(xiàn)為反向變化；若ρij=0，股票i和股票j完全不相關(guān)。計(jì)算n只股票對(duì)數(shù)收益率的相關(guān)系數(shù)，得到一個(gè)n×n階對(duì)稱相關(guān)系數(shù)矩陣p。選取合適的閾值，將系數(shù)矩陣p進(jìn)行量化，得到一個(gè)只有0和1的稀疏矩陣，此矩陣便作為金融網(wǎng)絡(luò)的鄰接矩陣。

1.3 復(fù)雜金融網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征

1.3.1 節(jié)點(diǎn)度分布

節(jié)點(diǎn)度是指連接節(jié)點(diǎn)的邊數(shù)，節(jié)點(diǎn)度分布是指一個(gè)任意選擇節(jié)點(diǎn)恰好度數(shù)為k的概率，也等于網(wǎng)絡(luò)中節(jié)點(diǎn)度數(shù)為k的節(jié)點(diǎn)數(shù)占網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)百分比，用分布函數(shù)p(k)來(lái)表示。

1.3.2 平均最短路徑長(zhǎng)度

若一個(gè)包含n個(gè)節(jié)點(diǎn)的無(wú)向網(wǎng)絡(luò)，，其中dij為節(jié)點(diǎn)i和節(jié)點(diǎn)j的最短距離，也是節(jié)點(diǎn)i,j最短路徑所經(jīng)過(guò)的邊數(shù)?？紤]到每個(gè)節(jié)點(diǎn)到期自身的距離為0，無(wú)關(guān)聯(lián)節(jié)點(diǎn)的距離為無(wú)窮大，此時(shí)存在問(wèn)題，所以對(duì)進(jìn)行修改，得到“調(diào)和平均”最短路徑長(zhǎng)度。在股票網(wǎng)絡(luò)中，平均最短路徑長(zhǎng)度是任意兩只股票相關(guān)中介數(shù)量的平均值，反映網(wǎng)絡(luò)的大小和分離程度。

1.3.3 聚集系數(shù)

考慮節(jié)點(diǎn)i，它通過(guò)ki條邊和其他ki個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)相連接，則它們之間最多有ki(ki－1)/2條邊連接，但ki個(gè)節(jié)點(diǎn)實(shí)際有Ei條邊，所以節(jié)點(diǎn)i的聚集系數(shù)ci，，網(wǎng)絡(luò)的平均聚集系數(shù)為。聚集是用來(lái)刻畫網(wǎng)絡(luò)的小集團(tuán)形態(tài)，說(shuō)明鄰近集團(tuán)在相關(guān)性意義上的凝聚程度。

2 復(fù)雜金融網(wǎng)絡(luò)的自相似性研究

相識(shí)性是現(xiàn)實(shí)世界客觀存在的一種現(xiàn)象，描述相識(shí)性的方法一般分為兩種：一種是將對(duì)象看作為某k個(gè)維特征空間的點(diǎn)，對(duì)象的相似由點(diǎn)與點(diǎn)間的距離來(lái)確定，另一種衡量相似性方法是比較對(duì)象之間的一般特征和一些典型特征。自相似性是一種特殊的相似，是對(duì)象本身的一種特性，是對(duì)象局部和整體相似。

雖然C.M.Song等用重構(gòu)化能測(cè)量網(wǎng)絡(luò)的自相似性，但此時(shí)網(wǎng)絡(luò)只能是固定結(jié)點(diǎn)的網(wǎng)絡(luò)，而現(xiàn)實(shí)生活中的網(wǎng)絡(luò)是動(dòng)態(tài)增長(zhǎng)的過(guò)程，如社會(huì)網(wǎng)中每個(gè)人認(rèn)識(shí)的朋友數(shù)在不斷地增加，隨著市場(chǎng)經(jīng)濟(jì)的完善，上市公司數(shù)量越來(lái)越多，在證券交易所交易的股票數(shù)量也在不斷的更新和變化。鑒于這些動(dòng)態(tài)變化的網(wǎng)絡(luò)，本文分別采用以下兩種方法來(lái)研究復(fù)雜金融網(wǎng)絡(luò)的自相似性

2.1 基于R/S分析的金融網(wǎng)絡(luò)自相似性分析

設(shè)網(wǎng)絡(luò)為動(dòng)態(tài)增長(zhǎng)的，網(wǎng)絡(luò)節(jié)點(diǎn)不斷地增長(zhǎng)記為n1,n2,…ni，計(jì)算節(jié)點(diǎn)在ni時(shí)度分布的累積極差R(k)和標(biāo)準(zhǔn)差S(k)。

設(shè)x(k)為網(wǎng)絡(luò)節(jié)點(diǎn)是ni時(shí)各節(jié)點(diǎn)的度數(shù)，的均值，也為網(wǎng)絡(luò)的平均度數(shù)。

累積極差R(k)：R(k)=max x(k,ni)-min x((k,ni)

標(biāo)準(zhǔn)差S(k)：，則關(guān)系式為，

R/S為重標(biāo)極差，H為Hurst指數(shù)，所以

具體計(jì)算：以ln ni為自變量，lnR/S為因變量采用最小二乘進(jìn)行線性擬合，所得直線的斜率即為H的估計(jì)值

復(fù)雜網(wǎng)絡(luò)自相似性與Hurst指數(shù)的關(guān)系[6]

若0≤H

若H=0.5， 說(shuō)明復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)是互相獨(dú)立的，度分布是隨機(jī)的。

若0.5

2.2 基于容量維數(shù)的自相似性分析

基于分形思想，用半徑為r的尺子去測(cè)長(zhǎng)度為l的尺子，所需尺子個(gè)數(shù)為

用半徑為r的小圓去覆蓋面積為S的圓，所需小圓個(gè)數(shù)為

用半徑為r的小球去覆蓋體積為V的球，所需小球個(gè)數(shù)為

以此類推可用半徑為r的客體去覆蓋被測(cè)對(duì)象，所需個(gè)數(shù)N(r)的值與r的取值關(guān)系表示為，

定義D為相似容量維數(shù)，取對(duì)數(shù)得相似容量維數(shù)[7]

本文計(jì)算平均最短路徑長(zhǎng)度和聚集系數(shù)的D來(lái)分析復(fù)雜金融網(wǎng)絡(luò)自相似性

3 實(shí)證分析

由于本文是分析動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)的自相似性，所以用不同數(shù)量的股票來(lái)構(gòu)造網(wǎng)絡(luò)。

1） 分別用200，250，300，350，400，450，500不等數(shù)量的股票構(gòu)造金融網(wǎng)絡(luò)，然后基于R/S分析用各網(wǎng)絡(luò)節(jié)點(diǎn)度分布來(lái)求Hurst指數(shù)，在matlab編程基礎(chǔ)上得到H=0.823，可知復(fù)雜金融網(wǎng)絡(luò)具有自相似性。取閾值為0.85，構(gòu)建股票網(wǎng)絡(luò)并計(jì)算各網(wǎng)絡(luò)的平均最短路徑長(zhǎng)度和聚集系數(shù)。

實(shí)證研究發(fā)現(xiàn)在網(wǎng)絡(luò)平均度數(shù)緩慢增長(zhǎng)時(shí)，網(wǎng)絡(luò)平均路徑長(zhǎng)度和聚集系數(shù)呈現(xiàn)相似的變化趨勢(shì)，這也是網(wǎng)絡(luò)拓?fù)涮匦宰韵嗨菩员憩F(xiàn)。

2） 選用200,250,300,350,400,450,500只股票分別構(gòu)造金融網(wǎng)絡(luò)，用比較分析法分析金融網(wǎng)絡(luò)的自相似性。

比較300，400，500只股票時(shí)相關(guān)系數(shù)的概率分布，然后采用修正法[3]求相關(guān)系數(shù)的概率分布。文獻(xiàn)[3]提出采用修正法求相關(guān)系數(shù)矩陣，來(lái)消除時(shí)間因素的影響。但筆者認(rèn)為不能做修正，盡量保持原有信息，這才能反應(yīng)真實(shí)的市場(chǎng)環(huán)境。因?yàn)槭紫茸C券股票市場(chǎng)存在在投機(jī)行為，趨利性等很容易造成追殺跌漲的“羊群效應(yīng)”，其次證券市場(chǎng)受到經(jīng)濟(jì)周期和行業(yè)因素的影響，而每個(gè)行業(yè)都要經(jīng)歷幼稚期、成長(zhǎng)期、成熟期、衰退期的發(fā)展演變過(guò)程，這個(gè)過(guò)程成為行業(yè)生命周期，再次證券市場(chǎng)還受到產(chǎn)業(yè)政策等影響。筆者用修正法[3]對(duì)300,400,500只股票構(gòu)建的網(wǎng)絡(luò)進(jìn)行了修正，得到圖3~圖4。

顯然修正后的相關(guān)系數(shù)的概率密度是正態(tài)分布，符合強(qiáng)勢(shì)有效市場(chǎng)的假設(shè)，但中國(guó)證券市場(chǎng)目前狀況是弱勢(shì)有效市場(chǎng)，證券價(jià)格只能反映歷史信息，還存在內(nèi)幕信息等，所以本文不對(duì)收益序列做任何修改。

在閾值為0.85時(shí)各股票網(wǎng)絡(luò)都表現(xiàn)出很好的無(wú)標(biāo)度特性（如表1所示）：(最小二乘法)。

給出在閾值為0.85時(shí)節(jié)點(diǎn)為300、400、500的度分布圖1。

以500只股票構(gòu)造的網(wǎng)絡(luò)為整個(gè)復(fù)雜網(wǎng)絡(luò)，300只和400只都為局部小網(wǎng)絡(luò)，得到容量相似維數(shù)。

從表2中可以看出Dl,Dc都比較相近，所以得動(dòng)態(tài)的網(wǎng)絡(luò)也具有自相似性。

4 結(jié)束語(yǔ)

本文基于復(fù)雜網(wǎng)絡(luò)的理論分析了金融市場(chǎng)的網(wǎng)絡(luò)特性―小世界效應(yīng)和無(wú)標(biāo)度特性。無(wú)標(biāo)度則表示網(wǎng)絡(luò)節(jié)點(diǎn)分布不均勻，網(wǎng)絡(luò)中有地位比較重要的“中心點(diǎn)”，可知股票市場(chǎng)存在影響力比較大的股票或是行業(yè)。實(shí)證研究結(jié)果得出，金融網(wǎng)絡(luò)的冪律指數(shù)大概為1，這與莊新田[2]等人得出上海證券市場(chǎng)網(wǎng)絡(luò)的冪律指數(shù)為0.8219和0.7930差異不大。本文還著重介紹了兩種方法分析金融網(wǎng)絡(luò)的自相似性，這說(shuō)明金融市場(chǎng)變化趨勢(shì)有一部分依賴于過(guò)去，到底依賴程度有多少，就需看整個(gè)金融市場(chǎng)自相似程度，這便成了下一步的研究?jī)?nèi)容。

復(fù)雜網(wǎng)絡(luò)論文:復(fù)雜網(wǎng)絡(luò)下的綜合視頻會(huì)議服務(wù)

面對(duì)越來(lái)越復(fù)雜的網(wǎng)絡(luò)環(huán)境及應(yīng)用,今天的企業(yè)用戶需要的已經(jīng)不僅僅是一個(gè)傳統(tǒng)意義上的產(chǎn)品或者系統(tǒng),他們需要自己的IT應(yīng)用發(fā)揮更大的價(jià)值,實(shí)現(xiàn)與客戶之間的交互、員工生產(chǎn)力的優(yōu)化以及企業(yè)資源的整合等,并通過(guò)這些方面的整合提升企業(yè)的運(yùn)營(yíng)效率。視頻會(huì)議作為提高溝通效率的有效方式,滿足了人們?nèi)轿坏慕涣餍枨?因而在近年來(lái)取得了飛速的發(fā)展。

目前,國(guó)外從事視頻會(huì)議系統(tǒng)研制、生產(chǎn)的大公司大多已經(jīng)進(jìn)入中國(guó)市場(chǎng),國(guó)內(nèi)也有越來(lái)越多的企業(yè)積極參與到市場(chǎng)競(jìng)爭(zhēng)中來(lái),在競(jìng)爭(zhēng)越來(lái)越激烈的情況下,視頻會(huì)議系統(tǒng)供應(yīng)商必須充分發(fā)揮自身的優(yōu)勢(shì),才能搶占更大的市場(chǎng)份額。北京盛維新世紀(jì)網(wǎng)絡(luò)通信技術(shù)有限公司是一家專注于網(wǎng)絡(luò)多媒體通訊軟件開(kāi)發(fā)及服務(wù)的高新技術(shù)企業(yè)。作為全球少數(shù)真正全面掌握多媒體通訊核心技術(shù)的企業(yè),盛維公司在過(guò)去幾年中密切關(guān)注用戶的使用需求,并在其Cenwave多媒體通訊軟件平臺(tái)上開(kāi)發(fā)出網(wǎng)絡(luò)視頻會(huì)議系統(tǒng)、網(wǎng)絡(luò)直播系統(tǒng)、網(wǎng)絡(luò)實(shí)時(shí)課堂、多方電話會(huì)議等多種視頻應(yīng)用產(chǎn)品。

全面靈活的解決方案

由于我國(guó)存在比較復(fù)雜的運(yùn)營(yíng)商網(wǎng)絡(luò)環(huán)境,企業(yè)的出口網(wǎng)絡(luò)一般較窄,為了確保用戶在任何情況下都能夠成功召開(kāi)遠(yuǎn)程會(huì)議,盛維公司為用戶準(zhǔn)備了一整套遠(yuǎn)程會(huì)議綜合解決方案,可以為客戶提供基于不同終端、多種實(shí)現(xiàn)方式融合的、系統(tǒng)化的視頻服務(wù)支持。北京盛維新世紀(jì)通信技術(shù)有限公司總裁魏松祥表示:“我們正在向用戶交付一個(gè)真正兼容的平臺(tái),能夠兼容不同網(wǎng)絡(luò)、不同種類的終端設(shè)備,實(shí)現(xiàn)語(yǔ)音、視頻、數(shù)據(jù)的全面整合。讓用戶可以在任何時(shí)間、任何地點(diǎn)、和任何人進(jìn)行多媒體的溝通和交流,實(shí)現(xiàn)協(xié)同辦公?！?

相比較市場(chǎng)上其他服務(wù)商提供的解決方案,盛維遠(yuǎn)程會(huì)議綜合解決方案全面涵蓋了軟件視頻會(huì)議系統(tǒng)、硬件視頻會(huì)議終端、軟硬混合視頻會(huì)議系統(tǒng)、MCU租用、電話會(huì)議租用、網(wǎng)絡(luò)會(huì)議租用等各種產(chǎn)品與服務(wù),并能夠根據(jù)客戶的需求提供這一系列產(chǎn)品與服務(wù)的組合,真正做到實(shí)現(xiàn)客戶各種形式、各種應(yīng)用環(huán)境下“成功召開(kāi)遠(yuǎn)程會(huì)議”的目標(biāo)。

魏松祥告訴記者,在盛維提供的純軟件高清視頻會(huì)議解決方案中,用戶只需通過(guò)普通的PC機(jī)、麥克風(fēng)、攝像頭就能夠輕松在互聯(lián)網(wǎng)上召開(kāi)網(wǎng)絡(luò)會(huì)議。對(duì)于關(guān)注成本的中小企業(yè)用戶來(lái)說(shuō),盛維軟件高清視頻會(huì)議解決方案可以讓它們以最小成本實(shí)現(xiàn)遠(yuǎn)程視頻會(huì)議的召開(kāi)。而基于硬件的高清視頻會(huì)議終端主要是為了滿足大中型企業(yè)客戶的應(yīng)用需求,系統(tǒng)采用了高集成度、嵌入式的設(shè)計(jì)模式,是一款體積小巧、外形美觀、穩(wěn)定可靠的硬件會(huì)議終端。

此外,為了加快網(wǎng)絡(luò)視頻會(huì)議在中小型企業(yè)市場(chǎng)的普及,盛維以顛覆性的思維推出了網(wǎng)絡(luò)視頻會(huì)議租用服務(wù),為企業(yè)提供了低風(fēng)險(xiǎn)、低投入、實(shí)施簡(jiǎn)單的視頻應(yīng)用服務(wù)。在這種服務(wù)模式下,一切網(wǎng)絡(luò)基礎(chǔ)設(shè)施、軟件平臺(tái)、硬件平臺(tái)的建設(shè)和維護(hù)工作都由盛維公司提供,當(dāng)用戶需要使用網(wǎng)絡(luò)視頻會(huì)議時(shí),只需向盛維申請(qǐng)開(kāi)通網(wǎng)絡(luò)會(huì)議服務(wù),獲得登錄賬號(hào)就可以召開(kāi)遠(yuǎn)程網(wǎng)絡(luò)視頻會(huì)議。這種獨(dú)創(chuàng)性的租用服務(wù)模式,使得企業(yè)無(wú)需購(gòu)買任何系統(tǒng)軟件、硬件設(shè)備,無(wú)需租用昂貴的服務(wù)器帶寬,也無(wú)需專業(yè)IT人員維護(hù)就可以輕松召開(kāi)遠(yuǎn)程視頻會(huì)議,真正做到幫助企業(yè)降低運(yùn)營(yíng)成本,提高工作效率。

覆蓋全球的運(yùn)營(yíng)網(wǎng)絡(luò)

多媒體視訊服務(wù)需要堅(jiān)實(shí)可靠的網(wǎng)絡(luò)來(lái)支撐。在全球化的時(shí)代,用戶的溝通對(duì)象可能在全國(guó)乃至世界各地。一個(gè)網(wǎng)絡(luò)會(huì)議運(yùn)營(yíng)網(wǎng)絡(luò)不但需要能充分覆蓋國(guó)內(nèi),也要能較好覆蓋世界各地。盛維在發(fā)展過(guò)程中,逐步建立起一個(gè)覆蓋面廣、通信質(zhì)量可靠的面向全球用戶的網(wǎng)絡(luò)會(huì)議運(yùn)營(yíng)網(wǎng)絡(luò),通過(guò)這個(gè)網(wǎng)絡(luò)平臺(tái)可以保證高清視頻會(huì)議系統(tǒng)的穩(wěn)定運(yùn)行。

盛維網(wǎng)絡(luò)會(huì)議運(yùn)營(yíng)網(wǎng)絡(luò)為租用盛維網(wǎng)絡(luò)會(huì)議的客戶提供了一個(gè)高速的專用網(wǎng)絡(luò),確保用戶在這個(gè)平臺(tái)上能召開(kāi)高質(zhì)量的網(wǎng)絡(luò)會(huì)議。同時(shí)盛維還與全球各地的電信運(yùn)營(yíng)商建立了緊密合作關(guān)系,把電話網(wǎng)成功對(duì)接到這個(gè)運(yùn)營(yíng)網(wǎng)絡(luò)上。用戶能以極低廉的資費(fèi)召開(kāi)電話會(huì)議,或者實(shí)現(xiàn)電話會(huì)議與網(wǎng)絡(luò)視頻會(huì)議的混合使用。

魏松祥表示,盛維運(yùn)營(yíng)網(wǎng)目前已經(jīng)覆蓋了全國(guó)所有地區(qū),在主要骨干網(wǎng)上部署了上百臺(tái)服務(wù)器,總帶寬達(dá)到將近2Gbps。同時(shí),盛維公司在亞太地區(qū)、北美與歐洲也部署了眾多服務(wù)器,其運(yùn)營(yíng)網(wǎng)絡(luò)能全面覆蓋亞洲、北美以及歐洲等地。此外,為了確保用戶在盛維運(yùn)營(yíng)網(wǎng)上的通信安全保密,盛維公司采用了嚴(yán)格的安全策略以及256位數(shù)據(jù)加密算法,并且有專業(yè)運(yùn)維團(tuán)隊(duì)7×24監(jiān)控服務(wù)器與網(wǎng)絡(luò)。

憑借出色的技術(shù)能力,盛維系列產(chǎn)品目前已應(yīng)用政府、軍隊(duì)、教育、醫(yī)療、金融、能源、IT等多個(gè)行業(yè)。在國(guó)內(nèi)教育行業(yè),更是取得市場(chǎng)占有率60%的業(yè)績(jī)。魏松祥告訴記者:“每天全球有數(shù)萬(wàn)用戶在使用我們的產(chǎn)品及服務(wù),并且已有上百家客戶使用我們提供的產(chǎn)品成功召開(kāi)1000人以上大規(guī)模會(huì)議或遠(yuǎn)程培訓(xùn)?！睉{借以上出色的表現(xiàn),在2009年6月,盛維公司一舉榮獲第十三屆中國(guó)國(guó)際軟件博覽會(huì)“獻(xiàn)禮新中國(guó)成立60周年?中國(guó)軟件行業(yè)最具成長(zhǎng)力企業(yè)獎(jiǎng)”。

可以說(shuō),在工業(yè)化與信息化日益融合的大趨勢(shì)下,盛維公司給企業(yè)信息化選型創(chuàng)造了有利的條件,降低了企業(yè)視頻應(yīng)用的門檻。某種意義上講,盛維公司正在改變傳統(tǒng)多媒體通訊軟件銷售的模式,為企業(yè)提供了低風(fēng)險(xiǎn)、低投入、實(shí)施簡(jiǎn)單的信息化方案,使企業(yè)通過(guò)互聯(lián)網(wǎng)便可以享受到相應(yīng)的軟件和維護(hù)服務(wù),切實(shí)做到了幫助企業(yè)降低運(yùn)營(yíng)成本,提高工作效率。

復(fù)雜網(wǎng)絡(luò)論文:基于復(fù)雜網(wǎng)絡(luò)的風(fēng)險(xiǎn)傳播模型及有效算法

摘 要：提出一種基于復(fù)雜網(wǎng)絡(luò)的風(fēng)險(xiǎn)傳播模型及有效算法，通過(guò)結(jié)合復(fù)雜網(wǎng)絡(luò)中傳播蔓延現(xiàn)象的推廣模型，將風(fēng)險(xiǎn)傳播模型劃分為兩種：主動(dòng)型風(fēng)險(xiǎn)傳播模型與被動(dòng)型風(fēng)險(xiǎn)傳播模型。并對(duì)已有風(fēng)險(xiǎn)傳播算法進(jìn)行改進(jìn)，實(shí)驗(yàn)表明，該模型及算法能健全風(fēng)險(xiǎn)傳播機(jī)制，提高傳播速度與精確度。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；推廣模型；風(fēng)險(xiǎn)傳播

1 引 言

隨著網(wǎng)絡(luò)安全問(wèn)題的日益突出，風(fēng)險(xiǎn)評(píng)估越來(lái)越受到人們的重視。風(fēng)險(xiǎn)評(píng)估一般分為靜態(tài)評(píng)估和動(dòng)態(tài)評(píng)估兩種，前者評(píng)估體系比較完善，評(píng)估精確性程度較高，但缺點(diǎn)是評(píng)估周期過(guò)長(zhǎng)，評(píng)估模型可能隨著時(shí)間的推移而不能適用，不能反映網(wǎng)絡(luò)的實(shí)時(shí)信息；后者評(píng)估能根據(jù)網(wǎng)絡(luò)狀況適時(shí)的做出風(fēng)險(xiǎn)估計(jì)，能及時(shí)反映網(wǎng)絡(luò)風(fēng)險(xiǎn)的動(dòng)態(tài)變化，性能好于靜態(tài)評(píng)估[1，2]。而針對(duì)動(dòng)態(tài)風(fēng)險(xiǎn)評(píng)估的研究有：基于免疫的網(wǎng)絡(luò)安全風(fēng)險(xiǎn)檢測(cè)的模型[3，4]，是一種基于入侵時(shí)的檢測(cè)模型；基于隱馬爾可夫模型的網(wǎng)絡(luò)風(fēng)險(xiǎn)評(píng)估方法研究[5，6]；基于貝葉斯模型的網(wǎng)絡(luò)風(fēng)險(xiǎn)動(dòng)態(tài)評(píng)估方法[7，8]， 可以對(duì)網(wǎng)絡(luò)的總體風(fēng)險(xiǎn)和局部要素可能引起風(fēng)險(xiǎn)的程度進(jìn)行評(píng)估。以上文獻(xiàn)對(duì)網(wǎng)絡(luò)入侵檢測(cè)研究較為深入，但側(cè)重于對(duì)攻擊的動(dòng)態(tài)評(píng)估，未能考慮已有風(fēng)險(xiǎn)如何擴(kuò)散與轉(zhuǎn)移。針對(duì)網(wǎng)絡(luò)風(fēng)險(xiǎn)傳播，張永錚等提出了用于評(píng)估網(wǎng)絡(luò)信息系統(tǒng)的風(fēng)險(xiǎn)傳播模型[9]和一種求解網(wǎng)絡(luò)風(fēng)險(xiǎn)傳播問(wèn)題的近似算法[10]，對(duì)已有風(fēng)險(xiǎn)在網(wǎng)絡(luò)中的傳播進(jìn)行研究，但其傳播模型與算法存在一些缺點(diǎn)：首先，模型中僅考慮了風(fēng)險(xiǎn)傳播模型，未能考慮風(fēng)險(xiǎn)引入模型；其次，一個(gè)部件上可能存在多個(gè)弱點(diǎn)，則該部件對(duì)另一部件的同一方向的可信訪問(wèn)路徑可多于一種，則部件不能在有向圖中被視為圖節(jié)點(diǎn)。第三，最小入度的部件感染風(fēng)險(xiǎn)的概率較低，因此其作為風(fēng)險(xiǎn)源的概率不高。第四，若入度最小的部件已經(jīng)感染風(fēng)險(xiǎn)，其出度不一定是最大的，正如流感爆發(fā)在人口密集的地區(qū)一樣，則其風(fēng)險(xiǎn)不能立即傳播出去，存在滯后性，時(shí)效性欠佳。

本文在針對(duì)網(wǎng)絡(luò)風(fēng)險(xiǎn)傳播問(wèn)題，結(jié)合復(fù)雜網(wǎng)絡(luò)中傳播蔓延現(xiàn)象的推廣模型 [11，12]，提出了一種網(wǎng)絡(luò)風(fēng)險(xiǎn)傳播模型及相關(guān)定義，并改進(jìn)了風(fēng)險(xiǎn)傳播算法。

2 推廣模型下的風(fēng)險(xiǎn)傳播

網(wǎng)絡(luò)信息的動(dòng)態(tài)風(fēng)險(xiǎn)不僅僅表現(xiàn)為一般意義的風(fēng)險(xiǎn)，其傳播可能會(huì)對(duì)社會(huì)造成不可估量的損失，如病毒的傳播造成的跨域風(fēng)險(xiǎn)、有害信息的傳播造成的社會(huì)風(fēng)險(xiǎn)等。為此我們將借鑒復(fù)雜網(wǎng)絡(luò)的傳播機(jī)理和分析的方法，研究網(wǎng)絡(luò)風(fēng)險(xiǎn)傳播模型。

按照復(fù)雜網(wǎng)絡(luò)的傳播蔓延現(xiàn)象的推廣模型[11，12]：假設(shè)網(wǎng)絡(luò)中有N個(gè)個(gè)體，每個(gè)個(gè)體是三種狀態(tài)的中的一種：易染態(tài)S，感染態(tài)I和移除態(tài)R，在時(shí)刻t，個(gè)體i隨機(jī)的與個(gè)體j相連，若i∈S，j∈I，則個(gè)體i以概率p得到一個(gè)正劑量di（t′），這里di（t′）都服從分布函數(shù)f（d）。每個(gè)個(gè)體都保留著過(guò)去T時(shí)期中所接受的總的劑量

在本文中，暫不考慮網(wǎng)絡(luò)風(fēng)險(xiǎn)移除狀態(tài)，即僅考慮風(fēng)險(xiǎn)在整個(gè)網(wǎng)絡(luò)中如何轉(zhuǎn)移，而未考慮網(wǎng)絡(luò)風(fēng)險(xiǎn)傳播后所造成情況的如何消除。因此上述推廣模型應(yīng)用于風(fēng)險(xiǎn)傳播如下：

計(jì)算技術(shù)與自動(dòng)化2016年6月

第35卷第2期呂元海等：基于復(fù)雜網(wǎng)絡(luò)的風(fēng)險(xiǎn)傳播模型及有效算法

每一時(shí)刻t，風(fēng)險(xiǎn)結(jié)點(diǎn)j對(duì)其直連結(jié)點(diǎn)i每發(fā)動(dòng)一次攻擊，就會(huì)從被攻擊結(jié)點(diǎn)i中獲取一定的信息劑量di（t），則在過(guò)去T時(shí)期中風(fēng)險(xiǎn)結(jié)點(diǎn)獲取被攻擊結(jié)點(diǎn)的信息總劑量為：

3 風(fēng)險(xiǎn)傳播模型

3.1 相關(guān)定義

定義1.結(jié)點(diǎn)：指網(wǎng)絡(luò)系統(tǒng)中任意一臺(tái)網(wǎng)絡(luò)設(shè)備上任意可能被利用的最小單元。其中已經(jīng)被利用的稱為風(fēng)險(xiǎn)結(jié)點(diǎn)，而尚未被利用的稱為非風(fēng)險(xiǎn)結(jié)點(diǎn)。

定義2.有向路徑：結(jié)點(diǎn)A訪問(wèn)結(jié)點(diǎn)B時(shí)，形成的從A指向B的單向訪問(wèn)關(guān)系。這里所說(shuō)的單向訪問(wèn)關(guān)系是指合法或非法的、由主動(dòng)發(fā)起方指向被訪問(wèn)方的訪問(wèn)，而不代表實(shí)際信息傳輸?shù)穆窂剑驗(yàn)閲?yán)格的講，任何兩個(gè)相連結(jié)點(diǎn)之間的鏈路都是雙向的。有向路徑概率即為結(jié)點(diǎn)訪問(wèn)概率。

定義3.風(fēng)險(xiǎn)傳出：指風(fēng)險(xiǎn)結(jié)點(diǎn)對(duì)其所訪問(wèn)的任一結(jié)點(diǎn)造成的損失或影響。

定義4.風(fēng)險(xiǎn)引入：指非風(fēng)險(xiǎn)結(jié)點(diǎn)訪問(wèn)風(fēng)險(xiǎn)結(jié)點(diǎn)時(shí)，由于存在實(shí)際信息的交換而受到該風(fēng)險(xiǎn)結(jié)點(diǎn)的影響。

這里舉例說(shuō)明一下定義3、4，某病毒利用空氣（相當(dāng)于網(wǎng)絡(luò)中的信息交換鏈路）進(jìn)行傳播，當(dāng)病體A主動(dòng)接觸易染體B時(shí)，A將病毒傳播給B，其中A主動(dòng)接觸B即為A訪問(wèn)B，病毒傳播方向?yàn)锳到B；反之當(dāng)易染體B主動(dòng)接觸病體A，也會(huì)被感染，同樣病毒傳播方向?yàn)锳至B，但為B訪問(wèn)A。

定義5.風(fēng)險(xiǎn)傳出公式：設(shè)結(jié)點(diǎn)n被成功利用的概率為Pn，被利用后對(duì)網(wǎng)絡(luò)系統(tǒng)的危害程度為Wn，利用至該結(jié)點(diǎn)的有向路徑概率為Pmn，其中m為主動(dòng)訪問(wèn)n的風(fēng)險(xiǎn)結(jié)點(diǎn)，則對(duì)結(jié)點(diǎn)n而言，產(chǎn)生的風(fēng)險(xiǎn)為Riskn=Pmn×Pn×Wn。

定義6.風(fēng)險(xiǎn)引入公式：設(shè)結(jié)點(diǎn)n為非風(fēng)險(xiǎn)結(jié)點(diǎn)，該結(jié)點(diǎn)成功訪問(wèn)風(fēng)險(xiǎn)結(jié)點(diǎn)m的概率為Pm，利用至結(jié)點(diǎn)m的有向路徑概率為Pnm，由結(jié)點(diǎn)n發(fā)出至結(jié)點(diǎn)m的有用消息權(quán)重及概率分別為Unm、pnm，由結(jié)點(diǎn)m發(fā)出至結(jié)點(diǎn)n的有害消息權(quán)重及概率分別為Hmn、pmn，則對(duì)結(jié)點(diǎn)n而言，引入的風(fēng)險(xiǎn)為Riskn=Pnm×Pm×（Unm×pnm+Hmn×pmn）。

定義7.風(fēng)險(xiǎn)網(wǎng)絡(luò)：借鑒張永錚等對(duì)風(fēng)險(xiǎn)網(wǎng)絡(luò)[4]定義，把一個(gè)能夠描述各結(jié)點(diǎn)風(fēng)險(xiǎn)分布與有向路徑的網(wǎng)絡(luò)稱為風(fēng)險(xiǎn)網(wǎng)絡(luò)。風(fēng)險(xiǎn)分布為網(wǎng)絡(luò)系統(tǒng)各個(gè)設(shè)備中結(jié)點(diǎn)攜帶風(fēng)險(xiǎn)的分布情況，為內(nèi)在風(fēng)險(xiǎn)；有向路徑即為各結(jié)點(diǎn)之間的訪問(wèn)方向，為外來(lái)風(fēng)險(xiǎn)的傳出與被引入提供可能。

3.2 風(fēng)險(xiǎn)傳播模型

1.主動(dòng)型風(fēng)險(xiǎn)傳播模型：也稱為主動(dòng)型風(fēng)險(xiǎn)傳出，即利用風(fēng)險(xiǎn)結(jié)點(diǎn)已存在的風(fēng)險(xiǎn)對(duì)其直連結(jié)點(diǎn)進(jìn)行主動(dòng)訪問(wèn)（包括非法攻擊或可信訪問(wèn)，下同），產(chǎn)生風(fēng)險(xiǎn)擴(kuò)散（即風(fēng)險(xiǎn)傳出）。如圖1（a）所示，結(jié)點(diǎn)A為風(fēng)險(xiǎn)源結(jié)點(diǎn)，存在至結(jié)點(diǎn)B、C、D、E的四條有向路徑，設(shè)結(jié)點(diǎn)A風(fēng)險(xiǎn)結(jié)點(diǎn)，至結(jié)點(diǎn)B、C、D、E的有向路徑概率為PAJ，（J=B，C，D，E），各結(jié)點(diǎn)自身被成功訪問(wèn)的概率為PJ，（J=B，C，D，E）[8]，則結(jié)點(diǎn)A以概率PAJ×PJ（J=B，C，D，E）引起其出度所連結(jié)點(diǎn)發(fā)生風(fēng)險(xiǎn)，如圖1（b）所示。

在實(shí)際網(wǎng)絡(luò)中，路徑傳播概率可由兩結(jié)點(diǎn)的所有可能路徑計(jì)算得出，而結(jié)點(diǎn)被成功攻擊的概率則有風(fēng)險(xiǎn)傳播推廣模型計(jì)算得出。

4 最大出度算法

針對(duì)最小入度最近鄰算法[5]的不足，本文設(shè)計(jì)了一種能更好反映網(wǎng)絡(luò)風(fēng)險(xiǎn)動(dòng)態(tài)特征的算法――最大出度算法，又分為針對(duì)主動(dòng)型風(fēng)險(xiǎn)傳播模型的最大出度算法和針對(duì)被動(dòng)型風(fēng)險(xiǎn)傳播模型的最大出度算法。

4.1 風(fēng)險(xiǎn)源結(jié)點(diǎn)最大出度算法

Step1：計(jì)算未被處理過(guò)的風(fēng)險(xiǎn)結(jié)點(diǎn)出度值numofoutdegree。

Step2：優(yōu)先選擇最大出度的結(jié)點(diǎn)，利用圖1所示算法將其風(fēng)險(xiǎn)值沿其出度傳播給相鄰結(jié)點(diǎn)，風(fēng)險(xiǎn)計(jì)算方法見(jiàn)定義5。

Step3：傳播風(fēng)險(xiǎn)后將該結(jié)點(diǎn)標(biāo)記為color=red。

Step4：重復(fù)Step1、Step2、Step3，直至所有風(fēng)險(xiǎn)結(jié)點(diǎn)全部被標(biāo)記。

4.2 零入度非風(fēng)險(xiǎn)源最大出度算法

嚴(yán)格的講，零入度的結(jié)點(diǎn)是不存在的，因此最小入度最近鄰算法關(guān)于零入度的概念未指明其時(shí)間范疇，在本文中，零入度的結(jié)點(diǎn)是指在某時(shí)間段內(nèi)不接受訪問(wèn)的結(jié)點(diǎn)。

Step A：將網(wǎng)絡(luò)結(jié)點(diǎn)中所有零入度的非風(fēng)險(xiǎn)源結(jié)點(diǎn)標(biāo)記為color=green。

Step B：計(jì)算未被處理過(guò)的零入度的非風(fēng)險(xiǎn)源的出度值numofoutdegree。

Step C：優(yōu)先選擇最大出度結(jié)點(diǎn)，并判斷其出度中有無(wú)風(fēng)險(xiǎn)結(jié)點(diǎn)，若有則選擇其出度所連結(jié)點(diǎn)中風(fēng)險(xiǎn)值最大的一個(gè)作為引入風(fēng)險(xiǎn)源，以概率引入風(fēng)險(xiǎn)，風(fēng)險(xiǎn)計(jì)算方法見(jiàn)定義6，將該結(jié)點(diǎn)標(biāo)記為color=pink，斷開(kāi)與引入風(fēng)險(xiǎn)源的有向鏈接；若無(wú)，則重新選擇結(jié)點(diǎn)，對(duì)該結(jié)點(diǎn)不進(jìn)行任何處理直到再次滿足條件。

Step D：引入風(fēng)險(xiǎn)后，該結(jié)點(diǎn)已為風(fēng)險(xiǎn)結(jié)點(diǎn)，如果滿足最大出度的條件，則跳轉(zhuǎn)至最大出度算法的Step2繼續(xù)風(fēng)險(xiǎn)傳播。如果暫不滿足最大出度的條件，則跳轉(zhuǎn)至Step A順序執(zhí)行。

4.3 一般非風(fēng)險(xiǎn)源風(fēng)險(xiǎn)引入

網(wǎng)絡(luò)結(jié)點(diǎn)的風(fēng)險(xiǎn)在傳播最后往往會(huì)出現(xiàn)如圖3所示的情況：結(jié)點(diǎn)A、B、C為非風(fēng)險(xiǎn)源結(jié)點(diǎn)，D、E為風(fēng)險(xiǎn)結(jié)點(diǎn)且RiskD>RiskE，按照文[5]的理論，則其程序在圖3情況下停止運(yùn)行，為了解決這一問(wèn)題，引入如下算法：

Step a：計(jì)算非風(fēng)險(xiǎn)源結(jié)點(diǎn)的出度值numofoutdegree。

Step b：優(yōu)先選擇出度最大的結(jié)點(diǎn)，若其出度所連接結(jié)點(diǎn)中存在風(fēng)險(xiǎn)結(jié)點(diǎn)，則選擇風(fēng)險(xiǎn)值最大的一個(gè)結(jié)點(diǎn)作為風(fēng)險(xiǎn)引入源并斷開(kāi)與該風(fēng)險(xiǎn)引入源的有向鏈路，該結(jié)點(diǎn)被標(biāo)記為color=pink；若不存在，則重新選擇。

Step c：引入風(fēng)險(xiǎn)后，該結(jié)點(diǎn)已為風(fēng)險(xiǎn)結(jié)點(diǎn)，跳至Step b繼續(xù)執(zhí)行，直至又出現(xiàn)圖3情況，則跳轉(zhuǎn)至Step a繼續(xù)執(zhí)行，直至風(fēng)險(xiǎn)傳播完畢。

說(shuō)明：網(wǎng)絡(luò)結(jié)點(diǎn)被初始化為風(fēng)險(xiǎn)結(jié)點(diǎn)（color=pink）和安全可信結(jié)點(diǎn)（color=green）后，運(yùn)行風(fēng)險(xiǎn)源最大出度算法和零入度非風(fēng)險(xiǎn)源最大出度算法時(shí)，兩者發(fā)執(zhí)行，不存在先后次序，而一般非風(fēng)險(xiǎn)源風(fēng)險(xiǎn)引入只是在出現(xiàn)如圖3情況下才使用的算法，是為了防止風(fēng)險(xiǎn)傳播中忽略此類風(fēng)險(xiǎn)引入導(dǎo)致風(fēng)險(xiǎn)誤差較大的情況。

5 算法性能比較

5.1 風(fēng)險(xiǎn)傳播機(jī)制比較

最小入度最近鄰傳播算法[5]雖然能夠?qū)W(wǎng)絡(luò)風(fēng)險(xiǎn)傳播給出比較精確的結(jié)論，但其在理論上有一定的缺陷，如圖4所示，假設(shè)結(jié)點(diǎn)1、2為風(fēng)險(xiǎn)結(jié)點(diǎn)，按照最小入度最近鄰傳播算法，結(jié)點(diǎn)1為入度最小的滿足條件的風(fēng)險(xiǎn)結(jié)點(diǎn)，則其以概率使結(jié)點(diǎn)2、4產(chǎn)生風(fēng)險(xiǎn)，同時(shí)將自己標(biāo)記為已處理，如圖5（a）所示，然后結(jié)點(diǎn)2又滿足傳播條件，并以概率使結(jié)點(diǎn)3、5、6產(chǎn)生風(fēng)險(xiǎn)，并被標(biāo)記為已處理，如圖5（b）所示，兩步共計(jì)感染四個(gè)結(jié)點(diǎn)，但其卻是在第二步才將風(fēng)險(xiǎn)傳給結(jié)點(diǎn)6，因而其時(shí)效性欠佳。而按照風(fēng)險(xiǎn)源最大出度算法，則優(yōu)先選擇結(jié)點(diǎn)2，使其攜帶的風(fēng)險(xiǎn)迅速被傳播給結(jié)點(diǎn)3、5、6，如圖6（a）所示，再次結(jié)點(diǎn)6滿足傳播條件，并將風(fēng)險(xiǎn)傳播給其出度所連的四個(gè)結(jié)點(diǎn)，如圖6（b）所示，兩步共計(jì)感染七個(gè)結(jié)點(diǎn)，多于最小入度最近鄰傳播算法的新感染結(jié)點(diǎn)，并且其時(shí)效性優(yōu)勢(shì)隨著網(wǎng)絡(luò)結(jié)點(diǎn)的復(fù)雜化而凸顯，更容易滿足動(dòng)態(tài)網(wǎng)絡(luò)風(fēng)險(xiǎn)評(píng)估的要求。

此外，零入度的非風(fēng)險(xiǎn)源結(jié)點(diǎn)不會(huì)傳出風(fēng)險(xiǎn)[5]，因此應(yīng)在風(fēng)險(xiǎn)傳播之前對(duì)其進(jìn)行處理：斷開(kāi)此類結(jié)點(diǎn)的所有出度，如圖7所示，結(jié)點(diǎn)9被認(rèn)為不會(huì)對(duì)結(jié)點(diǎn)2及尤其是結(jié)點(diǎn)10造成風(fēng)險(xiǎn)傳播，因此可以斷開(kāi)其所有出度。但本論文認(rèn)為結(jié)點(diǎn)9雖不會(huì)對(duì)結(jié)點(diǎn)10造成直接的風(fēng)險(xiǎn)傳播，但是它可能會(huì)從結(jié)點(diǎn)2引入風(fēng)險(xiǎn)，從而使自己變?yōu)轱L(fēng)險(xiǎn)結(jié)點(diǎn)，進(jìn)而對(duì)結(jié)點(diǎn)10造成風(fēng)險(xiǎn)傳播，如圖8所示。

5.2 實(shí)驗(yàn)結(jié)果對(duì)比

本實(shí)驗(yàn)實(shí)驗(yàn)環(huán)境為Microsoft Windows XP Professional，Intel（R） Pentium（R） CPU 1.8GHz，512M RAM。仿真工具為NetLogo 4.0.4、Matlab 7.0.0.19920（R14）。

共同參數(shù)：總結(jié)點(diǎn)為200，平均度為10，風(fēng)險(xiǎn)結(jié)點(diǎn)不超過(guò)所有結(jié)點(diǎn)入度之和，結(jié)點(diǎn)危害性參數(shù)W=1，風(fēng)險(xiǎn)結(jié)點(diǎn)初始風(fēng)險(xiǎn)值為1，路徑傳播概率服從[0，0.5] 上的均勻分布。

本文參數(shù)：結(jié)點(diǎn)被成功訪問(wèn)概率P可利用推廣模型計(jì)算，其中推廣模型的參數(shù)p=0.5，f（d）=δ（d-1），g（d*）=δ（d*-3），采用最大出度算法進(jìn)行傳播。

文[5]參數(shù)：概率權(quán)p（x）=0.5，采用最小入度最近鄰算法進(jìn)行傳播。

6 結(jié) 論

實(shí)驗(yàn)表明：本文方法則是風(fēng)險(xiǎn)呈非線性變化，并且開(kāi)始變化較快，最后變化緩慢，即在一定的精確度容許的范圍內(nèi)，對(duì)風(fēng)險(xiǎn)進(jìn)行任意時(shí)刻的抽樣，本文的風(fēng)險(xiǎn)值更接近真實(shí)風(fēng)險(xiǎn)，因而動(dòng)態(tài)性能更好。另外考慮的非風(fēng)險(xiǎn)源結(jié)點(diǎn)的風(fēng)險(xiǎn)引入，使風(fēng)險(xiǎn)值被忽略的部分被重新計(jì)算在內(nèi)，提高了風(fēng)險(xiǎn)精確度。

復(fù)雜網(wǎng)絡(luò)論文:基于復(fù)雜網(wǎng)絡(luò)的車載自組織網(wǎng)絡(luò)抗毀性分析

摘要：針對(duì)車載自組織網(wǎng)絡(luò)（VANET）的抗毀性問(wèn)題，分析了其在隨意攻擊和蓄意攻擊下網(wǎng)絡(luò)的抗毀性特征。首先，提出以最大連通度、連通分支平均規(guī)模、臨界點(diǎn)移除比例及網(wǎng)絡(luò)效率為評(píng)價(jià)指標(biāo)的VANET拓?fù)淇箽詤?shù)；然后，基于帶有車輛換道功能的智能駕駛員模型，應(yīng)用VanetMobisim仿真軟件建立VANET；最后，通過(guò)仿真實(shí)驗(yàn)分析了網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)、通信半徑以及攻擊模式對(duì)VANET抗毀性的影響。實(shí)驗(yàn)結(jié)果表明由于車輛節(jié)點(diǎn)度分布的不均勻性，VANET對(duì)隨意攻擊具有較強(qiáng)的抗毀性，而在蓄意攻擊下顯得比較脆弱；基于節(jié)點(diǎn)介數(shù)的蓄意攻擊對(duì)網(wǎng)絡(luò)的破壞更快、更強(qiáng)。這些規(guī)律為優(yōu)化VANET拓?fù)淇刂?、網(wǎng)絡(luò)協(xié)議開(kāi)發(fā)和網(wǎng)絡(luò)管理提供新的指導(dǎo)。

關(guān)鍵詞：

車載自組織網(wǎng)絡(luò)；復(fù)雜網(wǎng)絡(luò)；抗毀性；隨意攻擊；蓄意攻擊；仿真

0引言

移動(dòng)Ad Hoc網(wǎng)絡(luò)（Mobile Ad Hoc NETwork， MANET）是一種自組織無(wú)線網(wǎng)絡(luò)，由于它不需要基礎(chǔ)設(shè)施支持，因此網(wǎng)絡(luò)部署快速，擴(kuò)展方便，使得它被廣泛應(yīng)用于軍事、救災(zāi)、商業(yè)等各領(lǐng)域。近年來(lái)，城市車輛與日俱增，移動(dòng)網(wǎng)絡(luò)技術(shù)日益突破，車輛自組織網(wǎng)絡(luò)（Vehicle Ad Hoc NETwork， VANET）[1]作為一種特殊的MANET網(wǎng)絡(luò)也快速引起高度重視。在VANET中，在一定的區(qū)域內(nèi)使用無(wú)線網(wǎng)絡(luò)通信技術(shù)將車輛與車輛以及車輛與固定基礎(chǔ)設(shè)施連接在一起，從而一個(gè)車輛間多跳通信網(wǎng)絡(luò)在現(xiàn)有道路上被動(dòng)態(tài)、快速地構(gòu)建，且具有自組織、分布式控制的特點(diǎn)，因此，VANET在交通方面具有良好的應(yīng)用前景，如信息預(yù)警、行車安全、車輛之間通信及車輛Internet訪問(wèn)等。

VANET既具M(jìn)ANET網(wǎng)絡(luò)的特點(diǎn)，如拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化、自組織無(wú)中心、低帶寬等，又有自己的特點(diǎn)，比如快速移動(dòng)性、拓?fù)渥兓l繁、間歇連通性、網(wǎng)絡(luò)規(guī)模大、充足的能量供應(yīng)等[2]。在VANET中，由于車輛的高速運(yùn)動(dòng)，網(wǎng)絡(luò)拓?fù)潆S之變化，對(duì)網(wǎng)絡(luò)性能造成直接影響，因此如果能夠掌握VANET拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)特性，可以設(shè)計(jì)高效的拓?fù)淇刂扑惴ǎ瑑?yōu)化網(wǎng)絡(luò)連通性，使網(wǎng)絡(luò)能夠持續(xù)穩(wěn)定提供可靠的服務(wù)。抗毀性是評(píng)價(jià)網(wǎng)絡(luò)拓?fù)涮卣鞯闹饕笜?biāo)之一，通過(guò)抗毀性的研究可以發(fā)現(xiàn)網(wǎng)絡(luò)中的安全隱患和薄弱環(huán)節(jié)，從而采取一系列有效的措施來(lái)提高網(wǎng)絡(luò)的抗毀性，優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，保證網(wǎng)絡(luò)的穩(wěn)定的通信能力，這對(duì)拓?fù)鋭?dòng)態(tài)變化的VANET協(xié)議開(kāi)發(fā)和網(wǎng)絡(luò)管理有著重要的意義。

目前，國(guó)內(nèi)外對(duì)Ad Hoc網(wǎng)絡(luò)的抗毀性研究較多。比如文獻(xiàn)[3]研究了網(wǎng)絡(luò)抗毀性受節(jié)點(diǎn)行為的影響，通過(guò)建立節(jié)點(diǎn)行為模型及分析三維網(wǎng)絡(luò)連通性得到了三維MANET網(wǎng)絡(luò)抗毀性的一種定量分析方法；同時(shí)仿真檢驗(yàn)了它的有效性和合理性。文獻(xiàn)[4]引入自然連通度為抗毀性度量指標(biāo)，建立了能耗的移動(dòng)Ad Hoc網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)抗毀性綜合測(cè)度模型，并確定了基于網(wǎng)絡(luò)拓?fù)淇箽缘淖顑?yōu)發(fā)射半徑。Azni等[5]根據(jù)相關(guān)節(jié)點(diǎn)的行為建立了k相關(guān)抗毀性模型，通過(guò)仿真分析了Ad Hoc網(wǎng)絡(luò)的全局抗毀性。文獻(xiàn)[6]中有針對(duì)性地分別從失效成因、測(cè)度、提升策略與故障檢測(cè)和修復(fù)等4個(gè)方面對(duì)無(wú)線傳感器網(wǎng)絡(luò)抗毀性的研究進(jìn)行歸納和分類，著重探討了基于網(wǎng)絡(luò)重構(gòu)和拓?fù)溲莼奥酚煽刂频臒o(wú)線傳感器網(wǎng)絡(luò)抗毀性優(yōu)化策略。

目前，對(duì)VANET拓?fù)浣Y(jié)構(gòu)的研究主要是基于復(fù)雜網(wǎng)絡(luò)理論分析其網(wǎng)絡(luò)的度分布、聚類系數(shù)、路徑長(zhǎng)度等。文獻(xiàn)[7]以多Agent微觀交通仿真器（Multiagent Microscopic Traffic Simulator， MMTS）為仿真工具，研究了瑞士城市蘇黎世交通網(wǎng)絡(luò)的瞬時(shí)特性，研究結(jié)果表明網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)服從參數(shù)冪律分布；通信半徑越大，最大集團(tuán)的值越大，集團(tuán)的數(shù)目越少；VANET不存在小世界特性。文獻(xiàn)[8]中利用4000多輛出租車收集的實(shí)時(shí)數(shù)據(jù)，分析了城市環(huán)境下車輛自組網(wǎng)的度分布、聚類系數(shù)、特征路徑長(zhǎng)度等拓?fù)涮匦?，建立了一種車輛自組網(wǎng)的網(wǎng)絡(luò)模型，通過(guò)仿真驗(yàn)證了所建模型的有效性。文獻(xiàn)[9]以城市道路交通仿真軟件（Simulation of Urban Mobility，SUMO）為仿真工具研究了德國(guó)科隆的交通網(wǎng)絡(luò)的瞬時(shí)拓?fù)浣Y(jié)構(gòu)，其主要刻畫參數(shù)包括最大連通分支、度及介數(shù)中心性等，分析結(jié)果表明車載自組織網(wǎng)不具有小世界特性。文獻(xiàn)[10]應(yīng)用Barabasi和Albert提出的BA（BarabasiAlbert）無(wú)標(biāo)度網(wǎng)絡(luò)對(duì)VANET拓?fù)溥M(jìn)行建模分析，認(rèn)為VANET具有小世界特性。文獻(xiàn)[11]利用車輛全球定位系統(tǒng)（Global Positioning System， GPS）數(shù)據(jù)分析了VANET拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)演化特征。據(jù)研究所知，對(duì)VANET拓?fù)浣Y(jié)構(gòu)抗毀性的研究甚少，僅有文獻(xiàn)[12]對(duì)VANET的抗毀性作了初步研究，但是該文認(rèn)為VANET是無(wú)標(biāo)度網(wǎng)絡(luò)，然后用無(wú)標(biāo)度網(wǎng)絡(luò)模型產(chǎn)生VANET，事實(shí)上，這樣生成的VANET就是一個(gè)無(wú)標(biāo)度網(wǎng)絡(luò)，與現(xiàn)實(shí)環(huán)境的VANET相差太遠(yuǎn)，幾乎沒(méi)有考慮VANET的任何特征，比如節(jié)點(diǎn)移動(dòng)性、節(jié)點(diǎn)移動(dòng)受到道路限制等，因此該文本質(zhì)上是研究了無(wú)標(biāo)度網(wǎng)絡(luò)的抗毀性，并非VANET的抗毀性。

抗毀性是VANET拓?fù)浣Y(jié)構(gòu)的重要特性之一，它代表網(wǎng)絡(luò)在某種極端攻擊或錯(cuò)誤條件下其服務(wù)能力下降的程度。由于真實(shí)、公開(kāi)的VANET的trace比較少，而且能夠獲得的一些真實(shí)trace存在一些問(wèn)題，比如GPS數(shù)據(jù)不完整、時(shí)間粒度、數(shù)據(jù)精度不夠等，使得用真實(shí)VANET移動(dòng)數(shù)據(jù)研究抗毀性存在一定困難，因此，本文通過(guò)VanetMobiSim車輛仿真軟件，深入分析VANET的抗毀性特征，為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的優(yōu)化提供指導(dǎo)。

1VANET抗毀性研究方法及測(cè)度

1.1抗毀性研究方法

目前，抗毀性的主要研究方法是用不同的方式對(duì)網(wǎng)絡(luò)進(jìn)行攻擊，用相應(yīng)的測(cè)度指標(biāo)對(duì)網(wǎng)絡(luò)的抗毀性進(jìn)行分析。網(wǎng)絡(luò)攻擊策略是指采取何種方式刪除網(wǎng)絡(luò)中的節(jié)點(diǎn)或邊，在現(xiàn)有研究中主要應(yīng)用Albert等[13]Albert提出的文獻(xiàn)，與文獻(xiàn)13的作者不匹配，請(qǐng)作相應(yīng)調(diào)整，以便保持一致；要注意論文在正文中的依次引用順序。提出的隨意攻擊（Random Attacks or Failure）和蓄意攻擊（Intentional Attacks）兩種方式。隨意攻擊通常是指隨機(jī)選擇網(wǎng)絡(luò)的一個(gè)節(jié)點(diǎn)或邊進(jìn)行攻擊，然后再隨意攻擊其余節(jié)點(diǎn)中的一個(gè)節(jié)點(diǎn)或邊，直至將網(wǎng)絡(luò)中所有節(jié)點(diǎn)全部攻擊完為止。蓄意攻擊又稱為選擇性攻擊，選擇重要的節(jié)點(diǎn)或邊作為攻擊對(duì)象，一般用度和介數(shù)度量節(jié)點(diǎn)和邊的重要性。具體攻擊過(guò)程為：首先選取網(wǎng)絡(luò)中度或介數(shù)最大的節(jié)點(diǎn)或邊作為第一攻擊目標(biāo)，攻擊完以后重新計(jì)算網(wǎng)絡(luò)各節(jié)點(diǎn)或邊的度量等級(jí)，依舊對(duì)度量等級(jí)最高的節(jié)點(diǎn)或邊進(jìn)行攻擊，重復(fù)該過(guò)程，直到網(wǎng)絡(luò)中所有的節(jié)點(diǎn)全部被攻擊完為止。

1.2節(jié)點(diǎn)重要度評(píng)估方法

蓄意攻擊選擇重要節(jié)點(diǎn)或邊進(jìn)行攻擊，評(píng)估網(wǎng)絡(luò)中節(jié)點(diǎn)或邊重要性的方法很多，本質(zhì)都源于圖論及基于圖論的數(shù)據(jù)挖掘。本文用度和介數(shù)評(píng)估車輛節(jié)點(diǎn)的重要性。

定義1節(jié)點(diǎn)的度。在網(wǎng)絡(luò)中，節(jié)點(diǎn)vi的鄰邊數(shù)目ki稱為該節(jié)點(diǎn)vi的度。網(wǎng)絡(luò)的平均度為：

k=1N∑Ni=1ki（1）

直觀上看，一個(gè)節(jié)點(diǎn)的度越大，該節(jié)點(diǎn)越重要。

定義2節(jié)點(diǎn)的介數(shù)。節(jié)點(diǎn)vi的介數(shù)Bi就是網(wǎng)絡(luò)中所有最短路徑中經(jīng)過(guò)該節(jié)點(diǎn)的數(shù)量比例之和，即：

Bi=∑j，k∈V， j≠kNjk（i）Njk（2）

其中：Njk表示節(jié)點(diǎn)vj和節(jié)點(diǎn)vk之間的最短路徑條數(shù)；Njk（i）表示節(jié)點(diǎn)vj和節(jié)點(diǎn)vk之間的最短路徑路過(guò)節(jié)點(diǎn)vi的條數(shù)。介數(shù)是一個(gè)全局特征量，反映節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的作用和影響力。在VANET中，若一個(gè)節(jié)點(diǎn)的介數(shù)越大，則表明它在網(wǎng)絡(luò)中交換的信息流越大，可視為網(wǎng)絡(luò)中的核心節(jié)點(diǎn)，也意味著它更容易擁塞，成為網(wǎng)絡(luò)的瓶頸。

1.3VANET抗毀性測(cè)度

設(shè)G=（V，E）為VANET的拓?fù)鋱D，其中V={v1，v2，…，vN}是網(wǎng)絡(luò)節(jié)點(diǎn)的集合，E={e1，e2，…，ek}是網(wǎng)絡(luò)邊的集合，節(jié)點(diǎn)數(shù)定義為N=V。定義子圖Ci=G（Vi，Ei）為含節(jié)點(diǎn)vi連通分支，設(shè)m（G）=max1≤i≤nV（Ci）表示圖G的所有連通分支中頂點(diǎn)數(shù)最多的那個(gè)連通分支的節(jié)點(diǎn)數(shù)，則節(jié)點(diǎn)數(shù)最多的連通分支為最大連通分支。

定義3最大連通度S。將網(wǎng)絡(luò)中的最大連通分支中節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)中總的節(jié)點(diǎn)數(shù)的比值稱為最大連通度，即：

S=m（G）/N（3）

那么0

定義4連通分支平均規(guī)模s。當(dāng)VAENT受到攻擊后，網(wǎng)絡(luò)被分割為若干連通分支，連通分支平均規(guī)模定義為去掉最大連通分支后其他連通分支的平均節(jié)點(diǎn)數(shù)，即：

s=（∑ni=1V（Ci）-m（G））/（n-1）（4）

顯然0

定義5臨界點(diǎn)移除比例fc。當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)受到攻擊后，網(wǎng)絡(luò)處于崩潰邊緣時(shí)，網(wǎng)絡(luò)中被攻擊的節(jié)點(diǎn)數(shù)占總節(jié)點(diǎn)數(shù)的比例，稱為臨界點(diǎn)移除比例，記為fc。

網(wǎng)絡(luò)在某種攻擊模式下，百分比f(wàn)的節(jié)點(diǎn)被移除，當(dāng)f超過(guò)一定閾值，即f≥fc當(dāng)在“=fc”時(shí)，屬于哪種情形，需明確。時(shí)，網(wǎng)絡(luò)分割成許多小的非連通分支；當(dāng)f

設(shè)網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)vi與vj之間的距離dij為連接這兩個(gè)節(jié)點(diǎn)的最短路徑上的邊數(shù)。VANET由于車輛的高速移動(dòng)、拓?fù)渥兓l繁，使得網(wǎng)絡(luò)間歇連通，因此存在dij=∞。而且當(dāng)網(wǎng)絡(luò)受到攻擊時(shí)，網(wǎng)絡(luò)的連通性也將發(fā)生改變，網(wǎng)絡(luò)被破壞到一定程度時(shí)，會(huì)產(chǎn)生孤立節(jié)點(diǎn)，此時(shí)會(huì)存在dij=∞，因此，文獻(xiàn)[13]提出用網(wǎng)絡(luò)全局效率來(lái)描述非全連通網(wǎng)絡(luò)的連通性。

定義6全局效率E。定義網(wǎng)絡(luò)全局效率為：

E=1N（N-1）∑i， j∈V，i≠j1dij（5）

顯然，網(wǎng)絡(luò)全局效率越大，網(wǎng)絡(luò)連通性越好。

2仿真實(shí)驗(yàn)

2.1VANET仿真環(huán)境

本文采用VanetMobiSim[14]軟件建立VANET環(huán)境，移動(dòng)模型采用帶有車道變換的智能駕駛員模型（Intelligent Driver Model with Lane Changes， IDMLC）[15]。該模型是一種微觀交通流模型，是在IDM的基礎(chǔ)上增加了車輛在十字路口的管理及車輛換道功能的智能移動(dòng)模型，使得其更加符合真實(shí)的交通場(chǎng)景。仿真實(shí)驗(yàn)中，網(wǎng)絡(luò)節(jié)點(diǎn)即為運(yùn)動(dòng)的車輛，可以獲取任意時(shí)刻任意車輛的位置、速度、加速度、所處車道等瞬時(shí)信息。IDMLC移動(dòng)模型中車輛長(zhǎng)度為5m，加速度a和減速度b分別為0.6m/s2和0.9m/s2，禮貌參數(shù)p為0.5，其他參數(shù)設(shè)置如表1所示。

2.2VANET抗毀性分析

下面分析在不同攻擊模式下VANET的抗毀性，為了在圖中便于區(qū)分不同攻擊模型，用符號(hào)Failure、RD和RB分別表示隨意攻擊、基于節(jié)點(diǎn)度的蓄意攻擊和基于節(jié)點(diǎn)介數(shù)的蓄意攻擊。圖1為網(wǎng)絡(luò)中車輛數(shù)為200、不同通信半徑時(shí)，VANET受到Failure、RD和RB等三種攻擊時(shí)網(wǎng)絡(luò)最大連通度的變化趨勢(shì)。由圖1可知，當(dāng)通信半徑r=200m， f=0時(shí)，S=0.3630，即初始網(wǎng)絡(luò)連通性較差。在攻擊過(guò)程中當(dāng)最大連通度低于0.1000時(shí)，視網(wǎng)絡(luò)基本癱瘓。在隨意攻擊下，當(dāng)S為0.0911時(shí)，臨界點(diǎn)移除比例fc=53.42%；在RD攻擊下，當(dāng)S為0.0616， fc=28.77%；在RB攻擊下，當(dāng)S為0.0890時(shí)， fc=20.55%。當(dāng)r=400m， f=0時(shí)，S=0.9521，初始網(wǎng)絡(luò)近乎全連通（網(wǎng)絡(luò)全連通時(shí)S=1）。在隨意攻擊下，當(dāng)S為0.0747時(shí)， fc=82.19%；在RD攻擊下，當(dāng)S為0.0822時(shí)， fc=57.53%；在RB攻擊下，當(dāng)S為0.0959時(shí)， fc=36.99%。這一方面說(shuō)明了通信半徑越大，VANET連通性越好，臨界點(diǎn)移除比例fc越大，抗毀性越強(qiáng)；另一方面，當(dāng)通信半徑相同時(shí)，隨意攻擊的臨界點(diǎn)移除比例fc的值均大于蓄意攻擊模式的，因此VANET有較強(qiáng)的魯棒性，且在蓄意攻擊下，由于將重要節(jié)點(diǎn)移除后網(wǎng)絡(luò)迅速分割為多個(gè)連通分支，S先呈現(xiàn)迅速大幅度下降、然后緩慢下降趨勢(shì)，即VANET又具有脆弱性。這種既魯棒又脆弱的抗毀特征是VANET中車輛度分布不均勻所致。

圖2為網(wǎng)絡(luò)中車輛數(shù)為200、不同通信半徑時(shí)，VANET受到Failure、RD和RB三種攻擊時(shí)的網(wǎng)絡(luò)連通分支平均規(guī)模。由圖2可知，當(dāng)通信半徑較?。ㄈ鐁=200m）時(shí)，初始網(wǎng)絡(luò)連通性較差，三種攻擊策略下連通分支平均規(guī)模s均隨移除節(jié)點(diǎn)比例的增加而逐漸減小。當(dāng)通信半徑較大時(shí)，網(wǎng)絡(luò)初始連通性較好，則s隨去除節(jié)點(diǎn)比例的變化趨勢(shì)都是先變大后變小。當(dāng)通信半徑r=400m時(shí)，在遭受隨意攻擊時(shí)，s在閾值f=0.8220處開(kāi)始緩慢變小，在遭受蓄意（RB、RD）攻擊時(shí)，s分別在閾值f=0.4521和f=0.2055處開(kāi)始變小。連通分支平均規(guī)模s之所以在閾值之前會(huì)變大，是由于隨著節(jié)點(diǎn)被移除，網(wǎng)絡(luò)總體連通程度變得越來(lái)越松散。在閾值之后會(huì)變小，是因?yàn)榫W(wǎng)絡(luò)在大量節(jié)點(diǎn)失效時(shí)被分割成互不連通的多個(gè)較小的分支，當(dāng)節(jié)點(diǎn)被全部移除時(shí)，網(wǎng)絡(luò)則會(huì)消失。通過(guò)計(jì)算，在r=300m時(shí)，VANET在Failure、RD和RB三種攻擊下連通分支平均規(guī)模s的方差分別為2.0306，2.4913和9.0228，即Failure攻擊下s的波動(dòng)最小，RB的波動(dòng)最大，當(dāng)通信半徑發(fā)生變化時(shí)，也有類似的結(jié)論。這也說(shuō)明了VANET既魯棒又脆弱的特征。

圖3分別為網(wǎng)絡(luò)中車輛數(shù)為200、不同通信半徑時(shí)，VANET受到Failure、RD和RB三種攻擊時(shí)網(wǎng)絡(luò)全局效率的變化趨勢(shì)。由圖3可知，通信半徑越大，VANET效率越高；同時(shí)，隨意攻擊模式下的網(wǎng)絡(luò)效率均高于蓄意攻擊的。

另外，比較圖1～3中最大連通度、臨界點(diǎn)移除比例、連通分支平均規(guī)模和網(wǎng)絡(luò)效率等抗毀性測(cè)度的值，可知對(duì)于蓄意攻擊的兩種策略，RB模式的攻擊效能要強(qiáng)于RD模式。

下面研究車輛密度對(duì)VANET抗毀性的影響。圖4～6為r=400m時(shí)不同車輛密度的VANET采取Failure、RD和RB攻擊策略時(shí)表現(xiàn)出的抗毀性差異。從圖4～6中分析得到：在通信半徑一定時(shí)，車輛密度越大，VANET連通性越好，抗毀性越強(qiáng)，但是當(dāng)網(wǎng)絡(luò)達(dá)到全連通時(shí)，車輛密度對(duì)VANET抗毀性影響不大，因此，在VANET拓?fù)淇刂茣r(shí)，可以根據(jù)實(shí)際道路、地形、路邊單元（RoadSide Unit， RSU）的配置等情況，對(duì)車輛通信半徑和車輛密度進(jìn)行優(yōu)化設(shè)置，使得網(wǎng)絡(luò)能夠保持良好的連通性。

3結(jié)語(yǔ)

在VANET中，抗毀性對(duì)于分析整個(gè)網(wǎng)絡(luò)性能來(lái)說(shuō)十分重要，尤其是在增強(qiáng)安全性方面的應(yīng)用。本文基于IDMLC移動(dòng)模型對(duì)車載自組織網(wǎng)絡(luò)的抗毀性特征作了研究，仿真結(jié)果表明，VANETs既有魯棒性又有脆弱性；通信半徑和車輛密度越大，VANETs抗毀性越好，但當(dāng)網(wǎng)絡(luò)全連通時(shí)，車輛密度對(duì)抗毀性影響很小。由于蓄意攻擊（RD、RB）對(duì)網(wǎng)絡(luò)破壞性強(qiáng)，因此，如何在拓?fù)淇刂茣r(shí)優(yōu)化網(wǎng)絡(luò)通信半徑、車輛密度及路邊基礎(chǔ)設(shè)施配置等參數(shù)，使得網(wǎng)絡(luò)中各個(gè)車輛節(jié)點(diǎn)保持相對(duì)均衡地位，從而提高VANETs抗毀性，這將是后續(xù)的研究工作。另外，本文只研究了VANET的瞬時(shí)拓?fù)浣Y(jié)構(gòu)及其抗毀性，然而，VANET的重要特征之一是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的實(shí)時(shí)變化，其動(dòng)態(tài)抗毀性特征也是接下來(lái)工作之一。

復(fù)雜網(wǎng)絡(luò)論文:基于復(fù)雜網(wǎng)絡(luò)理論的電網(wǎng)主導(dǎo)節(jié)點(diǎn)選擇

摘 要：隨著電網(wǎng)規(guī)模日益增大，對(duì)其進(jìn)行電壓控制越發(fā)困難。為了更好的對(duì)其進(jìn)行電網(wǎng)優(yōu)化控制，集中選取電網(wǎng)中的主導(dǎo)節(jié)點(diǎn)作為無(wú)功補(bǔ)償點(diǎn)成為關(guān)鍵。為此文章提出基于復(fù)雜網(wǎng)絡(luò)理論的主導(dǎo)節(jié)點(diǎn)選擇方法，并通過(guò)IEEE-39節(jié)點(diǎn)系統(tǒng)進(jìn)行仿真校驗(yàn)。

關(guān)鍵詞：電網(wǎng)；電網(wǎng)控制；主導(dǎo)節(jié)點(diǎn)，復(fù)雜網(wǎng)絡(luò)理論

前言

自從1999年Baraba和Albert發(fā)現(xiàn)了無(wú)標(biāo)度網(wǎng)絡(luò)特性，揭示出復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)中包含的結(jié)構(gòu)特征與各種動(dòng)力學(xué)特征之間的關(guān)系，突破了單純的規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)模型的束縛后，復(fù)雜網(wǎng)絡(luò)理論的研究就上了一個(gè)新的臺(tái)階[1]。而電網(wǎng)可以抽象成一個(gè)復(fù)雜網(wǎng)絡(luò)，具有復(fù)雜網(wǎng)絡(luò)的一般特征，可運(yùn)用復(fù)雜網(wǎng)絡(luò)理論來(lái)進(jìn)行分析。文章引入復(fù)雜網(wǎng)絡(luò)理論中的程度中心性指標(biāo)與靈敏度矩陣相結(jié)合來(lái)衡量節(jié)點(diǎn)在電網(wǎng)系統(tǒng)中的重要程度。

1 主導(dǎo)節(jié)點(diǎn)選擇方法

1.1 靈敏度矩陣的介紹

電網(wǎng)中的主導(dǎo)節(jié)點(diǎn)不僅要能進(jìn)行電壓調(diào)控，同時(shí)也應(yīng)該具有反映其節(jié)點(diǎn)電壓水平的能力。因此，在已有文獻(xiàn)中大部分都是通過(guò)構(gòu)建成考慮可觀性與可控性的目標(biāo)函數(shù)來(lái)進(jìn)行主導(dǎo)節(jié)點(diǎn)選擇[2-3]。該矩陣是關(guān)于無(wú)功注入變化對(duì)電壓變化的靈敏度，其性質(zhì)能反映電網(wǎng)間無(wú)功、電壓間聯(lián)系的疏密程度。電網(wǎng)節(jié)點(diǎn)i的靈敏度目標(biāo)函數(shù)定義為：

式中，m，j分別為區(qū)域內(nèi)所有負(fù)荷節(jié)點(diǎn)的編號(hào)和無(wú)功電源節(jié)點(diǎn)的編號(hào)；Se為分區(qū)內(nèi)所有負(fù)荷節(jié)點(diǎn)合集，Sg為分區(qū)內(nèi)所有無(wú)功電源節(jié)點(diǎn)合集?？捎^性指標(biāo)？琢im和可控性指標(biāo)？茁ij均由潮流計(jì)算收斂后的雅克比矩陣求得。

1.2 程度中心性指標(biāo)介紹

程度中心性指標(biāo)是社團(tuán)中節(jié)點(diǎn)在其所屬群體內(nèi)的重要程度進(jìn)行判別依據(jù)之一[4]，其定義為：

式中，di（n）為電網(wǎng)第n個(gè)節(jié)點(diǎn)與電網(wǎng)內(nèi)其他節(jié)點(diǎn)關(guān)系權(quán)重和，gi為電網(wǎng)內(nèi)所有節(jié)點(diǎn)之間權(quán)重和。

按目標(biāo)函數(shù)（1）計(jì)算出電網(wǎng)節(jié)點(diǎn)具有較大的靈敏度，但在實(shí)際電網(wǎng)中求出的節(jié)點(diǎn)可能處于電網(wǎng)區(qū)域末端位置，那么該節(jié)點(diǎn)就不適合作為電網(wǎng)主導(dǎo)節(jié)點(diǎn)。因此本文提出基于程度中心性指標(biāo)改進(jìn)目標(biāo)函數(shù)，改進(jìn)的目標(biāo)函數(shù)表達(dá)式如下：

為了驗(yàn)證基于復(fù)雜網(wǎng)絡(luò)理論中程度中心性指標(biāo)的電網(wǎng)主導(dǎo)選擇方法的可行性，文章將利用Matlab仿真軟件對(duì)IEEE-39節(jié)點(diǎn)標(biāo)準(zhǔn)測(cè)試系統(tǒng)進(jìn)行仿真分析。

2 算例分析

根據(jù)潮流計(jì)算收斂后的雅克比矩陣求出了？琢im矩陣和？茁ij矩陣，但這兩矩陣數(shù)量值不在同一個(gè)數(shù)量級(jí)上，因此需對(duì)其進(jìn)行標(biāo)準(zhǔn)化計(jì)算。根據(jù)式（3）求出節(jié)點(diǎn)的目標(biāo)函數(shù)值，文章只列出最大的3個(gè)節(jié)點(diǎn)，其值如表1所示。

由表1可以看出，所選主導(dǎo)節(jié)點(diǎn)在區(qū)域內(nèi)部大致處于中心位置，有利于對(duì)電網(wǎng)區(qū)域中末端位置的節(jié)點(diǎn)電壓水平進(jìn)行調(diào)控，能更好的實(shí)現(xiàn)電壓無(wú)功控制。

3 結(jié)束語(yǔ)

文章基于復(fù)雜網(wǎng)絡(luò)理論提出了一種新的主導(dǎo)節(jié)點(diǎn)選擇方法。并在IEEE-39節(jié)點(diǎn)標(biāo)準(zhǔn)測(cè)試系統(tǒng)上進(jìn)行了仿真驗(yàn)證，所得到的主導(dǎo)節(jié)點(diǎn)綜合考慮了電網(wǎng)的地理結(jié)構(gòu)與靈敏度矩陣，從而提高了主導(dǎo)節(jié)點(diǎn)選擇的準(zhǔn)確度。