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

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

基于復(fù)雜網(wǎng)絡(luò)理論的計算機網(wǎng)絡(luò)拓撲分析

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

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

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

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

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

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

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

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

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

二、Internet網(wǎng)絡(luò)的拓撲分析

（一）Internet拓撲的特點

近些年來對于Internet拓撲的研究，最重要的成果是對于Internet拓撲節(jié)點度的冪律分布。這種分布在規(guī)模不同的網(wǎng)絡(luò)拓撲中表現(xiàn)出一定的穩(wěn)定性，也就是指，在規(guī)模不同的Internet拓撲中，它們的節(jié)點度表現(xiàn)出一種冪律分布，即：

P（k）=k-β

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

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

（二）基于復(fù)雜網(wǎng)絡(luò)理論的Internet網(wǎng)絡(luò)拓撲模型的構(gòu)建

在世人發(fā)現(xiàn)Internet網(wǎng)絡(luò)節(jié)點度具有冪律分布的規(guī)律之后，Internet網(wǎng)絡(luò)拓撲模型的構(gòu)建產(chǎn)生巨大的轉(zhuǎn)變。大家更多的選擇從優(yōu)先連接和生長等這一網(wǎng)絡(luò)拓撲規(guī)律入手進行Internet網(wǎng)絡(luò)的拓撲建模，其主要是為了讓符合現(xiàn)實Internet拓撲性質(zhì)的模型通過一些簡單規(guī)則的演化讓其自動地產(chǎn)生出來。可利用優(yōu)先連接來對新節(jié)點加入網(wǎng)絡(luò)的過程進行描述還比較粗糙，首先是因為新節(jié)點在加入之前，對網(wǎng)絡(luò)全局的信息進行了解和把握具有很大的難度，其次一個原因是單一的優(yōu)先連接不能夠描述復(fù)雜的加入決策過程，而且在全網(wǎng)中容易形成少量的集散節(jié)點。所以要建立更加符合現(xiàn)實Internet拓撲特征的網(wǎng)絡(luò)模型則需要考慮更完善的加入規(guī)則。

現(xiàn)在對于構(gòu)建Internet模型主要是依據(jù)自治域級和路由器級，但由于Internet網(wǎng)絡(luò)拓撲特性在不同層次和不同規(guī)模中表現(xiàn)出某種本質(zhì)上的相似性，所以，本拓撲模型的構(gòu)建都適應(yīng)于這兩個級。此模型主要的規(guī)則是前面提到的通過生長和局部優(yōu)先連接，來形成Internet拓撲模型，這種形成機制就好像一個層次化比較強的選舉過程，如下圖所示：

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

三、結(jié)束語

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

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

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

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

一、引言

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

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

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

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

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

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

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

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

5.復(fù)雜計算機網(wǎng)絡(luò)拓撲圖狀態(tài)分析理論甚少。

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

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

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

三、復(fù)雜性理論

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

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

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

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

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

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

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

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

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

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

在網(wǎng)絡(luò)拓撲行為研究方面，研究成果表明實際的計算機網(wǎng)絡(luò)并不是一個隨機網(wǎng)絡(luò)系統(tǒng)，而是一種具有小世界特征和無尺度特征的復(fù)雜網(wǎng)絡(luò)，其節(jié)點度服從冪律分。欲研究計算機網(wǎng)絡(luò)的拓撲行為，就必須先著手建立有效的網(wǎng)絡(luò)拓撲模型，隨著學(xué)者深入研究，提出了比如WS模型、BA模型、局部演化模型等網(wǎng)絡(luò)拓撲演化模型，及針對網(wǎng)絡(luò)的魯棒和脆弱性，提出的HOT模型等。

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

五、展望

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

在計算機網(wǎng)絡(luò)拓撲機構(gòu)研究方面，網(wǎng)絡(luò)拓撲演化行為具有動力學(xué)、非線性、自組織性等，而將復(fù)雜性理論的自組織學(xué)、混沌學(xué)、分形學(xué)、拓撲學(xué)等領(lǐng)域研究成果引入計算機網(wǎng)絡(luò)拓撲研究尚不充分，且更具具體的實際計算機網(wǎng)絡(luò)特點結(jié)合復(fù)雜性理論進行研究也尚待探索。同樣，在計算機網(wǎng)絡(luò)流量行為研究方面，針對網(wǎng)絡(luò)流量的混沌、自相似等特性，結(jié)合混沌理論、分形理論等，全面闡述網(wǎng)絡(luò)流量行為的特點動態(tài)變化形式，并對計算機網(wǎng)絡(luò)流量進行有效建模，支持其特征參數(shù)，為給出有效的控制方法奠定基礎(chǔ)、以及為計算機網(wǎng)絡(luò)安全防范、穩(wěn)定運行等方面提供理論前提。

六、結(jié)論

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

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

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

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

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

近年來，國內(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ò)在時間、空間上都具有動態(tài)復(fù)雜，網(wǎng)絡(luò)行為也很復(fù)雜。

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

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

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

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

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

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

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

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

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

2.3 度分布(Degree Distribution)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 BA模型的演化過程

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

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

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

4 小結(jié)與展望

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

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

另外，演化網(wǎng)絡(luò)拓撲的解析方法仍不完善。目前的多數(shù)網(wǎng)絡(luò)模型是通過數(shù)值計算和近似的分析方法來建立的，即先以隨機的方式生成網(wǎng)絡(luò)，然后對度分布給出解析計算，而對其它主要參數(shù)僅給出模擬結(jié)果。由于模擬的結(jié)果帶有很大的隨機性，所以這種做對于網(wǎng)絡(luò)拓撲特性方面的嚴格理解還發(fā)展得遠遠不夠。

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

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

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

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

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

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

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

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

NB≈lB-dB (1)

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

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

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

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

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

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

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

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

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

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

(5) i=i+1

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

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

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

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

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

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

MEX文件主要由兩部分組成,它們分工明確,分別用于完成不同的任務(wù)。第一部分稱為計算功能子程,它包含了所有實際完成計算功能的源代碼,用來完成實際的計算工作。第二部分稱為入口子程序,它是計算子例行程序同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為整型,分別表示輸出輸入變量的個數(shù);plhs[]p rhs[]為mxA rray型指針數(shù)組,分別表示輸出輸入變量的地址。MEX文件執(zhí)行流程可用圖1表示。

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

(1) 我們先根據(jù)貪婪著色算法描述,用matlab的M文件實現(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) 最后對修改后的程序編譯執(zhí)行

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

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

3 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)是不均勻的，往往存在很多連接致密的集團，在這些集團之間只有很少邊形成的松散的連接。這些致密的結(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的劃分算法對得到的網(wǎng)絡(luò)進行分塊。當(dāng)把正常樣本網(wǎng)分成14個社區(qū)時，得到的聚類系數(shù)最大，為Q=0.596（如表2），這樣就把網(wǎng)絡(luò)分成了14個大的功能模塊。如圖3所示，即為正常樣本網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)（每種顏色代表一個社區(qū)）?？梢钥闯?，各個社區(qū)結(jié)構(gòu)中的節(jié)點數(shù)目分布并不均勻，并且存在很多孤立節(jié)點。社區(qū)內(nèi)節(jié)點間的連接比較緊密，而不同社區(qū)間的連接比較稀疏。

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

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

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

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

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

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

表6

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

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

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

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

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

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

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

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

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

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

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

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

1.1 數(shù)據(jù)來源

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

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

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

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

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

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

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

1.3.1 節(jié)點度分布

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

1.3.2 平均最短路徑長度

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

1.3.3 聚集系數(shù)

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

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

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

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

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

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

設(shè)x(k)為網(wǎng)絡(luò)節(jié)點是ni時各節(jié)點的度數(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ù)，所以

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

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

若0≤H

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

若0.5

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

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

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

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

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

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

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

3 實證分析

由于本文是分析動態(tài)復(fù)雜網(wǎng)絡(luò)的自相似性，所以用不同數(shù)量的股票來構(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é)點度分布來求Hurst指數(shù)，在matlab編程基礎(chǔ)上得到H=0.823，可知復(fù)雜金融網(wǎng)絡(luò)具有自相似性。取閾值為0.85，構(gòu)建股票網(wǎng)絡(luò)并計算各網(wǎng)絡(luò)的平均最短路徑長度和聚集系數(shù)。

實證研究發(fā)現(xiàn)在網(wǎng)絡(luò)平均度數(shù)緩慢增長時，網(wǎng)絡(luò)平均路徑長度和聚集系數(shù)呈現(xiàn)相似的變化趨勢，這也是網(wǎng)絡(luò)拓撲特性自相似性表現(xiàn)。

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

全面靈活的解決方案

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

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

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

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

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

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

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

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

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

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

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

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

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

1 引 言

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

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

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

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

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

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

計算技術(shù)與自動化2016年6月

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

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

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

3.1 相關(guān)定義

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

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

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

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

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

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

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

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

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

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

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

4 最大出度算法

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

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

Step1：計算未被處理過的風(fēng)險結(jié)點出度值numofoutdegree。

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

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

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

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

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

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

Step B：計算未被處理過的零入度的非風(fēng)險源的出度值numofoutdegree。

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

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

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

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

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

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

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

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

5 算法性能比較

5.1 風(fēng)險傳播機制比較

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

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

5.2 實驗結(jié)果對比

本實驗實驗環(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é)點為200，平均度為10，風(fēng)險結(jié)點不超過所有結(jié)點入度之和，結(jié)點危害性參數(shù)W=1，風(fēng)險結(jié)點初始風(fēng)險值為1，路徑傳播概率服從[0，0.5] 上的均勻分布。

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

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

6 結(jié) 論

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

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

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

關(guān)鍵詞：

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

0引言

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

VANET既具MANET網(wǎng)絡(luò)的特點，如拓撲結(jié)構(gòu)動態(tài)變化、自組織無中心、低帶寬等，又有自己的特點，比如快速移動性、拓撲變化頻繁、間歇連通性、網(wǎng)絡(luò)規(guī)模大、充足的能量供應(yīng)等[2]。在VANET中，由于車輛的高速運動，網(wǎng)絡(luò)拓撲隨之變化，對網(wǎng)絡(luò)性能造成直接影響，因此如果能夠掌握VANET拓撲結(jié)構(gòu)的動態(tài)特性，可以設(shè)計高效的拓撲控制算法，優(yōu)化網(wǎng)絡(luò)連通性，使網(wǎng)絡(luò)能夠持續(xù)穩(wěn)定提供可靠的服務(wù)。抗毀性是評價網(wǎng)絡(luò)拓撲特征的主要指標(biāo)之一，通過抗毀性的研究可以發(fā)現(xiàn)網(wǎng)絡(luò)中的安全隱患和薄弱環(huán)節(jié)，從而采取一系列有效的措施來提高網(wǎng)絡(luò)的抗毀性，優(yōu)化網(wǎng)絡(luò)拓撲結(jié)構(gòu)，保證網(wǎng)絡(luò)的穩(wěn)定的通信能力，這對拓撲動態(tài)變化的VANET協(xié)議開發(fā)和網(wǎng)絡(luò)管理有著重要的意義。

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

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

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

1VANET抗毀性研究方法及測度

1.1抗毀性研究方法

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

1.2節(jié)點重要度評估方法

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

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

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

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

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

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

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

1.3VANET抗毀性測度

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

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

S=m（G）/N（3）

那么0

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

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

顯然0

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

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

設(shè)網(wǎng)絡(luò)中任意兩個節(jié)點vi與vj之間的距離dij為連接這兩個節(jié)點的最短路徑上的邊數(shù)。VANET由于車輛的高速移動、拓撲變化頻繁，使得網(wǎng)絡(luò)間歇連通，因此存在dij=∞。而且當(dāng)網(wǎng)絡(luò)受到攻擊時，網(wǎng)絡(luò)的連通性也將發(fā)生改變，網(wǎng)絡(luò)被破壞到一定程度時，會產(chǎn)生孤立節(jié)點，此時會存在dij=∞，因此，文獻[13]提出用網(wǎng)絡(luò)全局效率來描述非全連通網(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仿真實驗

2.1VANET仿真環(huán)境

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

2.2VANET抗毀性分析

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

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

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

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

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

3結(jié)語

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

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

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

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

前言

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

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

1.1 靈敏度矩陣的介紹

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

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

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

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

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

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

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

2 算例分析

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

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

3 結(jié)束語

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