時間：2022-05-08 04:30:59
序論：在您撰寫復雜網(wǎng)絡論文時，參考他人的優(yōu)秀作品可以開闊視野，小編為您整理的1篇范文，希望這些建議能夠激發(fā)您的創(chuàng)作熱情，引導您走向新的創(chuàng)作高度。
摘要：復雜網(wǎng)絡是指具有無標度、小世界、吸引子、自相似、自組織中部分或者所有性質的網(wǎng)絡。在現(xiàn)實世界中，許多復雜的系統(tǒng)基本上都能以網(wǎng)絡來進行描述，而現(xiàn)實中的那些復雜的系統(tǒng)則可以以“復雜網(wǎng)絡”來稱之，比如社會網(wǎng)、交通網(wǎng)、電力網(wǎng)、萬維網(wǎng)、因特網(wǎng)等等都可以稱之為復雜網(wǎng)絡。本文主要通過對復雜網(wǎng)絡理論的介紹，從而對計算機Internet網(wǎng)進行分析，對Internet網(wǎng)這一復雜系統(tǒng)進行探究，揭示Internet拓撲現(xiàn)象的特性、規(guī)律及動因。
關鍵詞：復雜網(wǎng)絡；計算機網(wǎng)絡；網(wǎng)絡拓撲
在現(xiàn)實世界中，許多復雜的系統(tǒng)基本上都能以網(wǎng)絡來進行描述，而現(xiàn)實中的那些復雜的系統(tǒng)則可以以“復雜網(wǎng)絡”來稱之，比如社會網(wǎng)、交通網(wǎng)、電力網(wǎng)、萬維網(wǎng)、因特網(wǎng)等等都可以稱之為復雜網(wǎng)絡。在這些復雜系統(tǒng)中，那些現(xiàn)實中的實體往往通過復雜網(wǎng)絡的節(jié)點來表示，實體跟節(jié)點相對應，節(jié)點之間的連線（即邊）則對應于實體與實體之間的關系。而Internet網(wǎng)絡自從誕生開始，其一直沿著更優(yōu)、更高級、更復雜的路徑演化和發(fā)展著，現(xiàn)在Internet網(wǎng)絡已經(jīng)成為一個開放的、無中心控制的、異構的、分布式的極其復雜的網(wǎng)絡系統(tǒng)。其復雜性主要表現(xiàn)在：第一，Internet網(wǎng)絡結構日益復雜。Internet網(wǎng)絡的規(guī)模在不斷的擴大，網(wǎng)絡中的節(jié)點不斷加入和退出，各個節(jié)點以及它們之間的鏈路時常發(fā)生失效，鏈路也經(jīng)常出現(xiàn)方向和權重的變化。第二，網(wǎng)絡中節(jié)點日益復雜化。各節(jié)點越來越具有復雜非線性行為的動力學系統(tǒng)。第三，復雜因素之間的彼此影響。各個節(jié)點之間或者數(shù)據(jù)包流和節(jié)點之間出現(xiàn)了非線性的作用及其各個用戶之間的競爭和合作等等都是彼此的影響因素。
一、復雜網(wǎng)絡理論簡介
復雜網(wǎng)絡是指具有無標度、小世界、吸引子、自相似、自組織中部分或者所有性質的網(wǎng)絡。復雜網(wǎng)絡理論的主要內(nèi)容有：網(wǎng)絡的演化特征、演化規(guī)律、演化動力學機制、演化的統(tǒng)計規(guī)律以及網(wǎng)絡的模型特質、形成機制、幾何性質、結構穩(wěn)定性等。在自然科學中，復雜網(wǎng)絡研究的最為基本的內(nèi)容包括：度、相關性、集聚程度、最短距離、介數(shù)以及它們的分布特征。
復雜網(wǎng)絡系統(tǒng)一般有著下面幾個特征：
（1）小世界。復雜網(wǎng)絡通過簡單的描述對許多復雜的現(xiàn)實網(wǎng)絡進行了解釋，認為不管規(guī)模多大的網(wǎng)絡，其任意兩個節(jié)點都是由一條路徑連接的事實。它闡釋無論什么世界都是通過相互關系非常小的無數(shù)個節(jié)點所連接起來的。比如，在現(xiàn)實的社會網(wǎng)中，每個人的生活圈很小，人跟人認識的數(shù)目非常少，但是這個社會卻是由無數(shù)個關系所組成的，通過一條關系，可以找到跟你相距很遠的無關系的陌生人。就好像麥克盧漢所講的，地球將越來越小，是一個小的地球村，即一個小世界。
（2）集群性。復雜網(wǎng)絡會越來越具有集群性。比如，在現(xiàn)實的社會網(wǎng)絡中，每個人都有自己的朋友圈、熟人圈，在這個圈子里，每位成員都可能跟其他成員認識。集群性就是指網(wǎng)絡具有一種內(nèi)聚的傾向，即在一個大網(wǎng)絡中，會分布著許多個彼此聯(lián)系的積聚小網(wǎng)絡。比如一個朋友圈往往會通過某種關系跟另一個朋友圈聯(lián)系著。
（3）冪律的度分布。度是指網(wǎng)絡中的節(jié)點及其節(jié)點關系的數(shù)量；度的相關性是指各個節(jié)點之間的聯(lián)系緊密程度；介數(shù)是指網(wǎng)絡中所有最短路徑經(jīng)過某一節(jié)點的數(shù)量，即有一節(jié)點A，在網(wǎng)絡中，所有經(jīng)過A的數(shù)量，它反映的是節(jié)點A的影響力。無標度網(wǎng)絡的特征主要集中反映了集聚的集中性?？傊?，復雜網(wǎng)絡的主要特征有：無標度性、小世界效應、節(jié)點度的冪律分布。
二、Internet網(wǎng)絡的拓撲分析
（一）Internet拓撲的特點
近些年來對于Internet拓撲的研究，最重要的成果是對于Internet拓撲節(jié)點度的冪律分布。這種分布在規(guī)模不同的網(wǎng)絡拓撲中表現(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作為一個復雜網(wǎng)絡，從其通信網(wǎng)絡的優(yōu)化目的來說，其實現(xiàn)節(jié)點間平均距離最小化、網(wǎng)絡邊數(shù)最小化是其拓撲優(yōu)化的主要目標。即未來通信網(wǎng)絡的趨勢就是小世界網(wǎng)絡?？墒荌nternet網(wǎng)絡所覆蓋的范圍非常巨大，具有全球性，其拓撲結構的發(fā)展還面臨著許多技術上的問題。所以，對于Internet網(wǎng)絡拓撲結構的優(yōu)化目標的實現(xiàn)有點不大可能。但是話又說回來，盡管Internet的發(fā)展并不能實現(xiàn)拓撲設計的整體優(yōu)化，它的小世界、較少邊、高聚集等特性足以表明其還是具有小范圍優(yōu)化的特點，這些特點的產(chǎn)生可表現(xiàn)出其一些規(guī)律，即Internet網(wǎng)絡具有優(yōu)先連接和生長的規(guī)律。生長表示的是Internet具有動態(tài)增長的特性，所以Internet的拓撲結構也是一個動態(tài)的過程。優(yōu)先連接規(guī)律表示新節(jié)點進入Internet網(wǎng)絡的規(guī)則，即在新節(jié)點加入網(wǎng)絡時會選擇擁有較大連接數(shù)的節(jié)點進行連接。
（二）基于復雜網(wǎng)絡理論的Internet網(wǎng)絡拓撲模型的構建
在世人發(fā)現(xiàn)Internet網(wǎng)絡節(jié)點度具有冪律分布的規(guī)律之后，Internet網(wǎng)絡拓撲模型的構建產(chǎn)生巨大的轉變。大家更多的選擇從優(yōu)先連接和生長等這一網(wǎng)絡拓撲規(guī)律入手進行Internet網(wǎng)絡的拓撲建模，其主要是為了讓符合現(xiàn)實Internet拓撲性質的模型通過一些簡單規(guī)則的演化讓其自動地產(chǎn)生出來?？衫脙?yōu)先連接來對新節(jié)點加入網(wǎng)絡的過程進行描述還比較粗糙，首先是因為新節(jié)點在加入之前，對網(wǎng)絡全局的信息進行了解和把握具有很大的難度，其次一個原因是單一的優(yōu)先連接不能夠描述復雜的加入決策過程，而且在全網(wǎng)中容易形成少量的集散節(jié)點。所以要建立更加符合現(xiàn)實Internet拓撲特征的網(wǎng)絡模型則需要考慮更完善的加入規(guī)則。
現(xiàn)在對于構建Internet模型主要是依據(jù)自治域級和路由器級，但由于Internet網(wǎng)絡拓撲特性在不同層次和不同規(guī)模中表現(xiàn)出某種本質上的相似性，所以，本拓撲模型的構建都適應于這兩個級。此模型主要的規(guī)則是前面提到的通過生長和局部優(yōu)先連接，來形成Internet拓撲模型，這種形成機制就好像一個層次化比較強的選舉過程，如下圖所示：
此模型首先假設在一個平面中分布著n個節(jié)點，并存在著一個離散的均勻走動的時鐘，這些節(jié)點都清楚自己是何時進入網(wǎng)絡的，這些節(jié)點進入網(wǎng)絡的時刻分布是從零時刻開始至具體某一特定時刻內(nèi)的隨機分布。每個節(jié)點進入網(wǎng)絡前后的動作就是接收和發(fā)送消息及依據(jù)所接收的消息產(chǎn)生響應。發(fā)送和接收的消息中包括了自己的優(yōu)先度以及消息傳達的范圍等內(nèi)容。并且這些節(jié)點優(yōu)先度將對其消息傳送的范圍即輻射半徑產(chǎn)生直接的影響。在節(jié)點接收消息之后往往是按照消息源的優(yōu)先度來確定其是否跟發(fā)送消息的節(jié)點建立連接，若所接收到的許多消息源節(jié)點存在相近的優(yōu)先度，其將會隨機地選擇一個消息源節(jié)點進行連接。通過這種規(guī)則進行不斷的演化和發(fā)展，將會得出上圖的結果。其中a圖表示Internet網(wǎng)絡形成的初始階段，那時僅僅只有一小部分節(jié)點進行活動，每個節(jié)點度都比較小，其發(fā)送和接收消息的范圍還比較小，所以這些節(jié)點往往只跟自己相鄰的節(jié)點進行連接。而隨著時間的不斷推進，節(jié)點度的不斷增加，各個節(jié)點的消息所能到達的距離越來越遠，即所形成的連接會越來越大、越來越多。在局部區(qū)域勝出的節(jié)點代表整個區(qū)域參與更大范圍的競爭，以致形成更大區(qū)域的代表。這個過程將持續(xù)下去，直到網(wǎng)絡中形成幾個較大的聚集中心。如圖（b）、（c）所示，這種自組織的層次網(wǎng)絡并不具有預先設置的層次數(shù)。這就是Internet網(wǎng)絡拓撲結構的形成模型，是一種消息自組織和傳遞接收的模型。
三、結束語
綜上所述，復雜網(wǎng)絡理論最主要的特性是無標度性、小世界效應、節(jié)點度的冪律分布。Internet網(wǎng)絡延續(xù)著這些性質，在其拓撲結構構建和形成中表現(xiàn)出來，具體所形成的拓撲規(guī)則是：Internet網(wǎng)絡中節(jié)點的生長性和優(yōu)先連接。通過其不斷的生長以及生長出的節(jié)點的優(yōu)先連接，從而促使網(wǎng)絡拓撲是一種消息自組織和傳遞的過程。
摘要：在信息時代的大背景下，計算機網(wǎng)絡行為越來越復雜，傳統(tǒng)的研究計算機網(wǎng)絡行為的方法已難適應大規(guī)模的計算機網(wǎng)絡。為更好地管理和控制復雜的計算機網(wǎng)絡，提高網(wǎng)絡服務的質量，將復雜性理論應用于計算機網(wǎng)絡行為的研究，探索出一種復雜網(wǎng)絡行為研究新方法。分析計算機網(wǎng)絡行為研究的傳統(tǒng)方法之不足，闡明復雜性理論應用于計算機網(wǎng)絡行為研究的有效性，并概述其發(fā)展現(xiàn)狀，以及指明其廣泛的應用前景。
關鍵詞：計算機網(wǎng)絡；網(wǎng)絡行為；復雜性理論
一、引言
當今的計算機網(wǎng)絡異常復雜，運行時的動態(tài)變化規(guī)律成超分布、超并行、超復雜性質。計算機網(wǎng)絡行為研究的對象正是這種動態(tài)變化規(guī)律，具體研究對象有：拓撲結構的動態(tài)變化、傳輸性能動態(tài)演化、網(wǎng)絡安全、故障診斷、以及動態(tài)網(wǎng)絡流量等。建立或優(yōu)化出具有更高性能的計算機網(wǎng)絡，在巨量用戶的情況下，依然能保證高質量服務。故，研究計算機網(wǎng)絡行為具有重要的意義。
傳統(tǒng)的計算機網(wǎng)絡行為分析方法的基礎理論大多為“還原論”思想，一定程度不適合當今復雜計算機網(wǎng)絡行為研究的發(fā)展需求?；趥鹘y(tǒng)計算機網(wǎng)絡行為研究方法的缺陷，將復雜性理論應用于計算機網(wǎng)絡行為研究之中，為探索復雜網(wǎng)絡行為研究方法提供新思路。復雜性理論是一種基于非線性、動態(tài)、復雜系統(tǒng)的理論，其是解決系統(tǒng)整體性的新方法。故在研究計算機網(wǎng)絡宏觀行為特性時，復雜性理論有其巨大優(yōu)勢。
二、傳統(tǒng)計算機網(wǎng)絡行為研究
傳統(tǒng)的計算機網(wǎng)絡行為分析方法的基礎理論大多為“還原論”思想，一定程度不能較全面地當今復雜計算機網(wǎng)絡行為研究的發(fā)展需求，其局限主要表現(xiàn)在以下幾個方面：
1.傳統(tǒng)的計算機網(wǎng)絡中的采樣和測量理論已不適用于現(xiàn)在復雜背景下的計算機網(wǎng)絡。
2.復雜計算機網(wǎng)絡中的宏觀可靠性的研究甚少。
3.復雜計算機網(wǎng)絡中的安全行和宏觀安全監(jiān)控理論缺乏。
4.傳統(tǒng)的陣列新能評估理論不能處理長程相關條件下的性能評估。
5.復雜計算機網(wǎng)絡拓撲圖狀態(tài)分析理論甚少。
6.復雜計算機網(wǎng)絡中時常發(fā)生異常大流量，對這種顯現(xiàn)的研究和處理理論甚少，而傳統(tǒng)的Poisson和Markov理論不能準確刻畫，故，需要新的數(shù)學理論對其進行研究。
7.研究復雜計算機網(wǎng)絡中的流量實時測量和監(jiān)控理論較少。
然而，現(xiàn)今的計算機網(wǎng)絡發(fā)展迅猛，已經(jīng)深入人們生活的各個領域，故，探索新的方法，來研究復雜計算機網(wǎng)絡行的方法，以提高網(wǎng)絡服務質量，因此其具有重要的理論意義和實用價值。
三、復雜性理論
復雜性理論被譽為“二十一世紀的科學”，作為一種介于相對論和量子力學之間的新科學研究工具。
將復雜性理論應用于現(xiàn)今的復雜計算機網(wǎng)絡行為研究之中，可從計算機網(wǎng)絡系統(tǒng)的宏觀上研究和分析其網(wǎng)絡行為特性，該領域的研究能突破傳統(tǒng)算法的一些局限，更好地建設出和優(yōu)化現(xiàn)今的計算機網(wǎng)絡結構，保證服務質量。
復雜性理論主要包括：混沌學、分形學、自組織學、以及復雜網(wǎng)絡學等，是一種新型的交叉科學：
1.混沌是非線性系統(tǒng)中，貌似隨機運動的復雜現(xiàn)象，各個科學領域，包括計算機網(wǎng)絡中，存在大量的混沌現(xiàn)象，其主要特征包括有界性、遍歷性、不可預測性、分為性、普適性等。
2.分形所描述的一個粗糙或零碎的幾何形狀，可以分成多個部分，且每一部分都是體縮小尺寸的形狀，即自相似性。由于其由非線性、非平衡過程所產(chǎn)生，故其具有非周期、無規(guī)則的自相似特征。
3.自組織是一種系統(tǒng)的自我調(diào)節(jié)的過程，為整個系統(tǒng)自我生存、尋求適應性、創(chuàng)造性的行為。各種內(nèi)在因素相互影響，使復雜系統(tǒng)能夠自動地變換成“自組織臨界狀態(tài)”，此時，系統(tǒng)的時空動力學行為不再具有特征時間和特征空間尺度，而是時空關聯(lián)（滿足冪定律分布），如果越過該臨界狀態(tài)，系統(tǒng)會產(chǎn)生復雜的相變現(xiàn)象。
復雜計算機網(wǎng)絡行為的復雜性是宏觀的，包括行為復雜、功能復雜、結構復雜等各個方面。而復雜性理論的自組織性、臨界性、自相似性、非線性等鮮明特征正好符合研究復雜計算機網(wǎng)絡行為的各種特征。
四、計算機網(wǎng)絡行為的復雜性理論發(fā)展
由于復雜性理論的特性適用于研究復雜計算機網(wǎng)絡行為，故國內(nèi)外很多學者對將復雜性理論應用于網(wǎng)絡行為研究感興趣，并取得了一些成果。
在計算機網(wǎng)絡流量行為研究方面，WE Leland等人于1994年發(fā)現(xiàn)實際的計算機網(wǎng)絡流量符合自相似特性，而并不符合傳統(tǒng)的poisson分步布，這表明傳統(tǒng)的poisson、馬爾科夫流、自回歸等分析手段不在適用，后來進過大量學者深入研究，建立了一系列流量模型，比如報酬模型、無限源Poisson模型、MMPP模型、On/Off模型等。
在網(wǎng)絡拓撲行為研究方面，研究成果表明實際的計算機網(wǎng)絡并不是一個隨機網(wǎng)絡系統(tǒng)，而是一種具有小世界特征和無尺度特征的復雜網(wǎng)絡，其節(jié)點度服從冪律分。欲研究計算機網(wǎng)絡的拓撲行為，就必須先著手建立有效的網(wǎng)絡拓撲模型，隨著學者深入研究，提出了比如WS模型、BA模型、局部演化模型等網(wǎng)絡拓撲演化模型，及針對網(wǎng)絡的魯棒和脆弱性，提出的HOT模型等。
在將混沌學引入到計算機網(wǎng)絡行為研究中的方面，研究發(fā)現(xiàn)計算機網(wǎng)絡中普遍存在一種貌似隨機的現(xiàn)象，其具有混沌的各種特性。為引導這種混沌現(xiàn)象向好的方面發(fā)展，學者陳關榮等人在詳細分析了計算機網(wǎng)絡流量控制系統(tǒng)中的混沌現(xiàn)象之后，將將混沌控制方法引入到網(wǎng)絡流量控制當中，另外，國內(nèi)外一些學者探索試將混沌最大Lyapunov指數(shù)、以及相空間重構技術引入到計算機網(wǎng)絡流量行為研究和分析領域，獲得了一些成果。
五、展望
將復雜性理論引入計算機網(wǎng)絡行為研究，雖然取得了豐碩的成果，但也存在一些尚待解決的問題。現(xiàn)今的計算機網(wǎng)絡越來越復雜、有其符合復雜性理論的特性，且復雜性理論的研究比較成熟。
在計算機網(wǎng)絡拓撲機構研究方面，網(wǎng)絡拓撲演化行為具有動力學、非線性、自組織性等，而將復雜性理論的自組織學、混沌學、分形學、拓撲學等領域研究成果引入計算機網(wǎng)絡拓撲研究尚不充分，且更具具體的實際計算機網(wǎng)絡特點結合復雜性理論進行研究也尚待探索。同樣，在計算機網(wǎng)絡流量行為研究方面，針對網(wǎng)絡流量的混沌、自相似等特性，結合混沌理論、分形理論等，全面闡述網(wǎng)絡流量行為的特點動態(tài)變化形式，并對計算機網(wǎng)絡流量進行有效建模，支持其特征參數(shù)，為給出有效的控制方法奠定基礎、以及為計算機網(wǎng)絡安全防范、穩(wěn)定運行等方面提供理論前提。
六、結論
21世紀的信息化將給人來帶來巨大財富，計算機網(wǎng)絡行為的研究具有重要的價值，而計算機網(wǎng)絡行為研究中的復雜性理論研究將為其提供一種新方法。在此，針對實際計算機網(wǎng)絡的復雜性特點，總結了傳統(tǒng)網(wǎng)絡行為分析方法的缺陷，并綜述了計算機網(wǎng)絡行為研究中的復雜性理論研究現(xiàn)狀，指明其在管理和控制復雜計算機網(wǎng)絡方和提高網(wǎng)絡服務的質量方面取得的效果，總結了復雜性理論應用于計算機網(wǎng)絡行為研究的有效性，并闡述該理論研究的重要意義，以及其廣闊的發(fā)展前景和應用潛力。
摘要：從復雜網(wǎng)絡的三個主要度量特征量：平均路徑長度、聚集系數(shù)、度分布的角度分別介紹了復雜網(wǎng)絡中最主要的三種網(wǎng)絡模型,即隨機網(wǎng)絡模型、小世界網(wǎng)絡模型和無標度網(wǎng)絡模型，并提出了進一步研究的一些方向。
關鍵詞：復雜網(wǎng)絡；隨機網(wǎng)絡；小世界網(wǎng)絡；無標度網(wǎng)絡
1 復雜網(wǎng)絡研究概況
近年來，國內(nèi)外掀起了研究復雜網(wǎng)絡的熱潮。復雜網(wǎng)絡之所以復雜，不僅在于網(wǎng)絡規(guī)模的巨大，網(wǎng)絡結構的復雜，而且網(wǎng)絡在時間、空間上都具有動態(tài)復雜，網(wǎng)絡行為也很復雜。
現(xiàn)實世界中的許多系統(tǒng)都可以用復雜網(wǎng)絡來描述，如社會網(wǎng)絡中的科研合作網(wǎng)，信息網(wǎng)絡中的萬維網(wǎng)、科研引用網(wǎng)，技術網(wǎng)絡中的因特網(wǎng)、電力網(wǎng)等。網(wǎng)絡節(jié)點為系統(tǒng)元素，邊為元素間的互相作用，例如，在社會網(wǎng)絡中，節(jié)點表示個人、組織機構或國家，邊表示他(它)們之間的社會聯(lián)系。現(xiàn)實網(wǎng)絡系統(tǒng)的復雜性主要體現(xiàn)在三個方面[1]：首先，網(wǎng)絡的結構非常復雜，對網(wǎng)絡節(jié)點間的連接，至今仍沒有很清晰的概念;其次，網(wǎng)絡是不斷演化的，網(wǎng)絡節(jié)點不斷地增加，節(jié)點之間的連接在不斷地增長，而且連接之間存在著多樣性;第三，網(wǎng)絡的動力學具有復雜性，每個節(jié)點本身可以是非線性系統(tǒng)，具有分岔和混沌等非線性動力學行為而且在不停地變化。
由于現(xiàn)實世界網(wǎng)絡的規(guī)模大，節(jié)點間相互作用復雜，其拓撲結構基本上未知或未曾探索。兩百多年來，人們對描述真實系統(tǒng)拓撲結構的研究經(jīng)歷了三個階段。在最初的一百多年里，科學家們認為真實系統(tǒng)要素之間的關系可以用一些規(guī)則的結構表示，例如二維平面上的歐幾里德格網(wǎng);從20世紀50年代末到90年代末，無明確設計原則的大規(guī)模網(wǎng)絡主要用簡單而易于被多數(shù)人接受的隨機網(wǎng)絡來描述，隨機圖的思想主宰復雜網(wǎng)絡研究達四十年之久;直到最近幾年，科學家們發(fā)現(xiàn)大量的真實網(wǎng)絡既不是規(guī)則網(wǎng)絡，也不是隨機網(wǎng)絡，而是具有與前兩者皆不同的統(tǒng)計特性的網(wǎng)絡，其中最有影響的是小世界網(wǎng)絡和無標度網(wǎng)絡。這兩種網(wǎng)絡的發(fā)現(xiàn)，掀起了復雜網(wǎng)絡的研究熱潮。
2 復雜網(wǎng)絡主要特征度量
2.1 平均路徑長度(Average Path Length ,APL)
平均路徑長度是網(wǎng)絡中一個重要的特征度量，它指網(wǎng)絡中所有節(jié)點對之間的平均最短距離。這里節(jié)點間的距離指的是從一節(jié)點到另一節(jié)點所要經(jīng)歷的邊的最小數(shù)目，其中所有節(jié)點對之間的最大距離稱為網(wǎng)絡的直徑。平均路徑長度和直徑衡量的是網(wǎng)絡的傳輸性能與效率。
對于無方向無權重網(wǎng)絡，連接點i和點j的連線的數(shù)目即稱為路徑長度。點i和點j之間的最短路徑是連接這兩點的最短的路長,其長度是點i和點j之間的距離dij。若圖帶權重，可以使用同樣的定義，但是要考慮到權重。計算dij的平均值，稱為平均路徑長度：。這樣的定義存在的問題是如果在網(wǎng)絡中存在不連通的節(jié)點，則平均最短距離將發(fā)散。為此Latora和Marhciorlli[2]提出了一種稱為全局效率的相關測量量：。
2.2 聚集系數(shù)(簇系數(shù)Cluster Coefficient)
集聚系數(shù)，它衡量的是網(wǎng)絡的集團化程度，是網(wǎng)絡的另一個重要參數(shù)。簇系數(shù)的概念有其深刻的社會根源。對社會網(wǎng)絡而言，集團化形態(tài)是其一個重要特征，集團表示網(wǎng)絡中的朋友圈或熟人圈，集團中的成員往往相互熟悉，為衡量這種群集現(xiàn)象，科學家們提出了聚集系數(shù)的概念。
通常用到了兩種聚集系數(shù)。Barrat和Wegiht[3]提出了對于無向無權重的網(wǎng)絡的如下定義：C=3NA/N3 。 其中NA是網(wǎng)絡中三角形的數(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)絡的一個重要統(tǒng)計特征。這里的度也稱為連通度，節(jié)點的度指的是與該節(jié)點連接的邊數(shù)。度在不同的網(wǎng)絡中所代表的含義也不同，在社會網(wǎng)絡中，度可以表示個體的影響力和重要程度，度越大的個體，其影響力就越大，在整個組織中的作用也就越大，反之亦然。度分布則表示節(jié)點度的概率分布函數(shù)P(k)，它指的是節(jié)點有k條邊連接的概率。在目前的研究中，兩種度分布較為常見：一是指數(shù)度分布，即P(k)隨著k的增大以指數(shù)形式衰減；另一種分布是冪律分布，即P(k)~k-γ，其中γ稱為度指數(shù)，不同γ的網(wǎng)絡，其動力學性質也不同。另外，度分布還有其它形式，如星型網(wǎng)絡的度分布是兩點分布，規(guī)則網(wǎng)絡的度分布為單點分布。
3 復雜網(wǎng)絡模型
3.1 隨機網(wǎng)絡模型
20世紀50年代末期，匈牙利數(shù)學家Paul Erds和Alfred Rény首次將隨機性引入網(wǎng)絡的研究，提出了著名的隨機網(wǎng)絡模型，簡稱ER模型。他們指出可以用兩種方法建立隨機網(wǎng)絡一種方法是給定N個節(jié)點，從(N(N-1))/2條可能的邊中連接E條邊，忽略重邊情況;另一種方法是給定N個節(jié)點，每一對節(jié)點以概率p進行連接，所得到的圖是一個隨機圖。
隨機網(wǎng)絡的基本特性可以歸納如下:
1) 隨機網(wǎng)絡的平均度為：
2) 隨機網(wǎng)絡的聚集系數(shù)：由于網(wǎng)絡中任何兩個節(jié)點之間的連接都是等概率的，因此對于某個節(jié)點i，其鄰接點之間連接的概率也是p，所以隨機網(wǎng)絡的簇系數(shù)
網(wǎng)絡的平均最短距離隨網(wǎng)絡規(guī)模的增加呈對數(shù)增長。
3) 隨機網(wǎng)絡的平均最短距離可以進行如下估計：考慮隨機網(wǎng)絡的平均度(k)，對于任意一個節(jié)點，其一階鄰接點的數(shù)目為(k)，二階鄰接點的數(shù)目為(k)2，依此類推，當l步后達到網(wǎng)絡的總節(jié)點數(shù)目N，有N=N=(k)l，所以lland~lnN/ln((k))可以看出，隨機網(wǎng)絡的平均最短距離隨網(wǎng)絡規(guī)模的增加呈對數(shù)增長。
4) 隨機網(wǎng)絡的度分布：給定一個連接概率為p的隨機圖，對于任意節(jié)點i，其度ki遵循二項式分布:當網(wǎng)絡規(guī)模N很大時，網(wǎng)絡的度分布接近泊松分布，即 。由于隨機網(wǎng)絡中節(jié)點之間的連接是等概率的，因此大多數(shù)節(jié)點的度都在均值(k)附近，網(wǎng)絡中沒有度特別大的節(jié)點.隨機網(wǎng)絡的特征是網(wǎng)絡的簇系數(shù)較小，平均最短距離也較小。
3.2 小世界網(wǎng)絡模型
1998年Watts和Strogatz[4]在ER模型基礎上對比真實網(wǎng)絡提出了小世界模型(WS), WS模型構造過程如下：
1) 開始于規(guī)則圖形。初始有數(shù)目固定的N個節(jié)點，每個節(jié)點有k個臨近節(jié)點，構成一個規(guī)則的一維圓環(huán)。
2) 隨機化。以概率p對圓環(huán)中的每一條邊重新連接。這個過程中要求不能自身連接和重復連接。例如圖1[5]所示，p=0對應于規(guī)則圖，p=1對應于隨機圖；當前研究的熱點是p在0到1之間的WS網(wǎng)絡的性質。
圖1 中間為小世界模型(左圖為規(guī)則圖,右圖為隨機圖)
WS網(wǎng)絡的主要性質為：
a) 平均路徑。圖1中被隨機選擇又重新連結后的線稱為捷徑，它對整個網(wǎng)絡的平均路徑有著很大影響。分析表明：當p>=2/(NK)，即在保證系統(tǒng)中至少出現(xiàn)一條捷徑的情況下，系統(tǒng)的平均路徑開始下降。即使是相當少的捷徑也能夠顯著地減小網(wǎng)絡的平均路徑長度。這是因為每出現(xiàn)一條捷徑，它對整個系統(tǒng)的影響是非線性的，它不僅影響到被這條線直接連著的兩點，也影響到了這兩點的最近鄰、次近鄰，以及次次近鄰等。
b) WS網(wǎng)絡的聚集系數(shù)。由初始固定的節(jié)點數(shù)可計算出P=0時規(guī)則網(wǎng)絡的集群系數(shù)為C(0), C(0)取決于網(wǎng)絡結構而與尺寸N無關，因此有相對較大的值。隨著邊按一定的概率P隨機化，集群系數(shù)在C(0)的附近變化。
c) 度分布。WS模型是介于規(guī)則網(wǎng)絡和隨機網(wǎng)絡之間的模型，P=0時規(guī)則網(wǎng)絡的度分布是中心點位于K=k的δ函數(shù)，P=1時隨機網(wǎng)絡是Poisson分布，在K=k點達到極大值。P從0變化到1的過程中，原來δ函數(shù)形式的度分布逐漸拓寬最終形成 Poisson分布。
3.3 無標度網(wǎng)絡模型
上世紀末，Albert 等在對互聯(lián)網(wǎng)的研究中發(fā)現(xiàn)了無標度網(wǎng)絡(scale-free network)，開辟了人們對于復雜網(wǎng)絡系統(tǒng)認識的新天地。他們發(fā)現(xiàn)，互聯(lián)網(wǎng)實際上是由少數(shù)高連接性的頁面組織起來的，80%以上頁面的連結數(shù)不到4 個。然而只占節(jié)點總數(shù)不到萬分之一的極少數(shù)節(jié)點，卻有1000個以上的連結。這種網(wǎng)頁的連接分布遵循所謂的“冪次定律”：任何一個節(jié)點擁有k 條連接的概率，與1/ k 成正比，這就是無標度網(wǎng)絡。其后幾年中，各行各業(yè)的研究者們在許多不同的領域中，都發(fā)現(xiàn)了無標度網(wǎng)絡。從生態(tài)系統(tǒng)到人際關系，從食物鏈到代謝系統(tǒng)，處處可以看到無標度網(wǎng)絡。
無標度網(wǎng)絡最顯著特征是度分布屬于冪分布。其表現(xiàn)出的特性是：大多數(shù)的節(jié)點只與一兩個少數(shù)節(jié)點相連接，但有少數(shù)節(jié)點卻被大量的連接。無標度模型一般用來分析網(wǎng)絡的動態(tài)特性，揭示大型復雜網(wǎng)絡的拓撲結構。
基于“成長性”和“擇優(yōu)連接”這兩種機制，Albert等在深入分析了ER 模型之后，于1999年提出了BA 模型[6-7]，從理論上解釋了無標度網(wǎng)絡的現(xiàn)象。它比較準確地把握了現(xiàn)實世界中網(wǎng)絡最基本的特點，較好地解釋了無標度網(wǎng)絡的形成機制。
BA模型是第一個增長的網(wǎng)絡模型，其算法如下：
1) 增長：在初始時刻，假定系統(tǒng)中已有少量（m0個）節(jié)點，在以后的每一個時間間隔中，新增一個度為 的點(m≤m0)，并將這m條邊連接到網(wǎng)絡中已經(jīng)存在的m個不同的節(jié)點上。
2) 擇優(yōu)連接：當在網(wǎng)絡中選擇節(jié)點與新增節(jié)點連接時，假定被選擇的節(jié)點v與新節(jié)點連接的概率?蒹(ki)和節(jié)點 的度成正比，即。經(jīng)過t個時間間隔后，便會形成一個有N=m0+t個節(jié)點、 條邊的網(wǎng)絡。圖2顯示m=m0=2時的BA模型的演化過程。初始網(wǎng)絡有兩個節(jié)點，每次新增加的一個節(jié)點按優(yōu)先連接機制與網(wǎng)絡中已存在的兩個節(jié)點相連。
圖2 BA模型的演化過程
a) 度分布。BA模型生成的網(wǎng)絡的度分布是無標度的，因為網(wǎng)絡中的每一個節(jié)點有k條邊的概率p(k)~2m2l-3，如圖3所示。
b) 平均路徑長度。BA無標度網(wǎng)絡的平均路徑長度為，這表明該網(wǎng)絡也具有小世界特性。
c) 聚類系數(shù)。BA無標度網(wǎng)絡的聚類系數(shù)和網(wǎng)絡大小有關，近似成一種冪率分布。
4 小結與展望
綜上所述，以前，用規(guī)則網(wǎng)絡和隨機網(wǎng)絡理論來描述真實系統(tǒng)的拓撲結構，這只反映了眾多系統(tǒng)的兩種極端情況，不能很好地描述多數(shù)現(xiàn)實系統(tǒng)。近幾年來，以小世界網(wǎng)絡與無標度網(wǎng)絡為核心的復雜網(wǎng)絡領域的最新成果反映了大多數(shù)復雜系統(tǒng)的基本特性，使得對復雜系統(tǒng)建模的研究取得了實質性的突破。復雜網(wǎng)絡的模型研究雖然己取得很大進展，但仍然存在一些問題。
例如，小世界效應新的產(chǎn)生機制有待進一步研究。以WS模型為代表的小世界網(wǎng)絡模型很好地展示了小世界的特性，但現(xiàn)實系統(tǒng)中的小世界網(wǎng)絡異常豐富，理論上，有多少種現(xiàn)實網(wǎng)絡就有多少種生成機制。因此，研究小世界網(wǎng)絡形成的新機制，揭示產(chǎn)生小世界特性的多樣性和新途徑，是十分有意義的。
另外，演化網(wǎng)絡拓撲的解析方法仍不完善。目前的多數(shù)網(wǎng)絡模型是通過數(shù)值計算和近似的分析方法來建立的，即先以隨機的方式生成網(wǎng)絡，然后對度分布給出解析計算，而對其它主要參數(shù)僅給出模擬結果。由于模擬的結果帶有很大的隨機性，所以這種做對于網(wǎng)絡拓撲特性方面的嚴格理解還發(fā)展得遠遠不夠。
總之，復雜網(wǎng)絡的發(fā)展給了我們一種看待世界研究世界的新方法，隨著其研究工作的進一步開展，定能給我們帶來新的驚喜。
摘要:復雜網(wǎng)絡是最近幾年流行的新興學科之一。通過復雜網(wǎng)絡的研究可以發(fā)現(xiàn)人工網(wǎng)絡和自然世界中共同存在的一些普遍特征。復雜網(wǎng)絡的分形與自相似是復雜網(wǎng)絡在演化成小網(wǎng)絡時整體和部分、部分與部分之間呈現(xiàn)出來的某種相似性,通過對復雜網(wǎng)絡進行分形維數(shù)的計算來達到探測網(wǎng)絡的微觀演化過程非常重要。本文對計算分形維數(shù)的盒子覆蓋法進行了算法上的改進,同時在具體實現(xiàn)算法時采用了Matlab與C的接口程序C-MEX,有效地提高了運算速度!
關鍵詞:復雜網(wǎng)絡;分形維數(shù);C-MEX
隨著20世紀末Watts-Strogatz的小世界網(wǎng)絡模型和Barabasi-Albert的無尺度網(wǎng)絡模型的提出,復雜網(wǎng)絡的研究取得快速的發(fā)展。經(jīng)過十幾年的蓬勃發(fā)展,復雜網(wǎng)絡已成為最近幾年流行的新興學科之一,已不同程度的應用于工程技術、經(jīng)濟、醫(yī)藥、生物等領域。
復雜網(wǎng)絡是當前重要的一門交叉性學科,通過復雜網(wǎng)絡的研究可以發(fā)現(xiàn)自然世界和人工網(wǎng)絡中存在普遍的特征,如小世界、標度等,從而使人們重新認識自然世界。復雜網(wǎng)絡是從網(wǎng)絡的視角出發(fā),描述和研究的是系統(tǒng)構件如何相互作用而導致系統(tǒng)的宏觀特性與行為。分形與自相似是復雜網(wǎng)絡中的一個重要特性,也是其研究的一個熱點之一。復雜網(wǎng)絡的分形與自相似是復雜網(wǎng)絡在演化成小網(wǎng)絡時,整個過程將始終保持自己特征狀態(tài)的相對穩(wěn)定性,從而使它的整體和部分、部分與部分之間呈現(xiàn)某種相似性。在復雜網(wǎng)絡中,定量地描述這種具有自相似的網(wǎng)絡的參數(shù)就叫做復雜網(wǎng)絡的分形維數(shù)。計算分形維數(shù)最常用方法之一是盒子覆蓋法。本文對計算分形維數(shù)的盒子覆蓋法進行了算法上的改進,同時在具體實現(xiàn)算法時采用了Matlab與C的接口程序C-MEX,有效的提高了計算速度!
1 復雜網(wǎng)絡分形維數(shù)探討
復雜網(wǎng)絡的分形與自相似性研究是利用復雜網(wǎng)絡中節(jié)點內(nèi)部的互動性來探測網(wǎng)絡的微觀演化過程。一個復雜網(wǎng)絡具有分形性是指在對該網(wǎng)絡進行重整化的過程中,若覆蓋整個網(wǎng)絡中的點所需的大小為lB的盒子的最小數(shù)量為NB,NB會隨著lB的增長呈有限指數(shù)的冪律增長,若設冪律指數(shù)為dB,則為dB為該網(wǎng)絡的分形維數(shù)。具體滿足關系模型如式(1):
NB≈lB-dB (1)
盒子覆蓋法是計算復雜網(wǎng)絡分形維數(shù)基本的方法,是應用合適的形式于盒子覆蓋的方式求出一個復雜網(wǎng)絡的分形維數(shù)dB。盒子覆蓋法描述為:對于一個給定的網(wǎng)絡G和盒大小lB,一個盒子是所有任意兩個節(jié)點i和j之間的距離lij小于lB的節(jié)點集合。盒子的最小數(shù)(記為NB)要能完全覆蓋整個網(wǎng)絡。以lB=1為例,那么很明顯NB就為網(wǎng)絡節(jié)點數(shù)N。
盒覆蓋算法的最終目標就是找到一種行之有效的方式計算在給定盒子大小lB的情況下NB的最小值。
盒子覆蓋法也有很多方法可以實現(xiàn),最常用也是最有效的是貪婪著色法,其他的也有如燃燒算法等。本文采用了最常用的貪婪著色法并對其進行了稍微的改進。改進后的貪婪著色算法可以描述如下:
1) 給網(wǎng)絡中的所有節(jié)點分配一個唯一的從1到N的數(shù),每個節(jié)點并沒有著色
2) 對于所有的值lB,分配一個顏色值0給所有1到其他所有節(jié)點,如Ci1=0
3) 將i設為2,重復下面的5個步驟直到i=N
(1) 計算從i到j的所有節(jié)點的小于i的距離lij
(2) 將lB設為1
(3) 對于所有的lij>=lB選擇一種沒有使用的顏色Cjlij,就可以得到對于i的給定的lB的顏色值CilB
(4) 設lB=lB+1,直到lB=lBmax
(5) i=i+1
通過以上的算法只要在復雜網(wǎng)絡中的所有節(jié)點游走一遍,就可以在給定盒子大小lB的情況下計算出NB的最小值,接著就可以利用關系模型公式求出該網(wǎng)絡的分形維數(shù)dB了。
2 利用CMEX文件計算復雜網(wǎng)絡分形維數(shù)
根據(jù)以上的算法描述,我們用matlab具體實現(xiàn)了這個算法。但我們在具體實現(xiàn)的過程中,發(fā)現(xiàn)由于復雜網(wǎng)絡中的數(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)體時,可以編寫相應的C或C ++子程序完成相同的功能,并編譯成 MEX文件,再由MATLAB調(diào)用此MEX文件以提高運行速度。
C-MEX是通過MATLAB的編譯器轉換為可執(zhí)行文件,是按照MEX技術要求的格式編寫相應的程序,通過編譯連接,生成擴展名為.dll的動態(tài)鏈接庫文件,可以在MATLAB環(huán)境下以函數(shù)的形式直接調(diào)用。一般來說,C-MEX 文件的執(zhí)行速度是相同功能的M文件執(zhí)行速率的20~40倍。
MEX文件主要由兩部分組成,它們分工明確,分別用于完成不同的任務。第一部分稱為計算功能子程,它包含了所有實際完成計算功能的源代碼,用來完成實際的計算工作。第二部分稱為入口子程序,它是計算子例行程序同MATLAB環(huán)境之間的接口,其作用是在 MATLAB系統(tǒng)與被調(diào)用的外部子程序之間建立通信聯(lián)系。其中入口子程序的名字為mexFunction,其構成形式為: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)了此算法來對復雜網(wǎng)絡分形維數(shù)進行計算。具體利用C―MEX計算復雜網(wǎng)絡分形維數(shù)的過程如下:
(1) 我們先根據(jù)貪婪著色算法描述,用matlab的M文件實現(xiàn)
(2) 找出M文件中循環(huán)次數(shù)較多的代碼段
(3) 將這些循環(huán)次數(shù)較多的代碼段轉化成相應的C-MEX程序,并編譯成相應的.dll文件
(4) 將M文件中循環(huán)次數(shù)較多的代碼段用相應的.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ù),得出的實驗結果如表1所示。
從表1的結果,我們可以看到使用C-MEX混合編程后,實現(xiàn)復雜網(wǎng)絡分形維數(shù)計算算法的執(zhí)行時間得到了很大程度的提高。這也證明了我們所采用的方法是行之有效的。
3 結論
復雜網(wǎng)絡作為一門重要的交叉性學科,通過復雜網(wǎng)絡的研究可以發(fā)現(xiàn)人工網(wǎng)絡和自然世界中存在普遍相似的特征,從而使人們重新認識自然世界的一些特性。通過研究復雜網(wǎng)絡的分形維數(shù),除了探究復雜網(wǎng)絡中相似網(wǎng)絡的維數(shù),還可以探測網(wǎng)絡的微觀演化。本文對復雜網(wǎng)絡的分形維數(shù)計算算法進行了探討,并利用C-MEX混合編程的方式實現(xiàn)了此算法,極大地提高了運算速度。
摘要：該文采用復雜網(wǎng)絡理論。首先利用分類信息指數(shù)對數(shù)據(jù)進行初步篩選，選出了314個基因。對選出的基因分別做腫瘤樣本和正常樣本的相關系數(shù)矩陣，利用Kruskal算法分別對兩個相關系數(shù)矩陣做最小生成樹，然后通過比較選出閾值，建立起節(jié)點間的連邊關系，得到致病前后的兩個網(wǎng)絡。根據(jù)復雜網(wǎng)絡中的相關理論，分別對腫瘤樣本和正常樣本進行社區(qū)劃分，最后通過觀察兩個樣本的網(wǎng)絡系統(tǒng)，分析致病前后基因的變化情況，建議了結腸癌的特征基因。
關鍵詞：基因芯片；基因表達譜；社區(qū)結構；分類信息指數(shù)；最小生成樹；閾值；復雜網(wǎng)絡
癌癥起源于正常組織在物理或化學致癌物的誘導下，基因組發(fā)生的突變，即基因在結構上發(fā)生堿基對的組成或排列順序的改變，因而改變了基因原來的正常分布（即所包含基因的種類和各類基因以該基因轉錄的mRNA的多少來衡量的表達水平）。所以探討基因分布的改變與癌癥發(fā)生之間的關系具有深遠的意義。
復雜網(wǎng)絡理論是近年來發(fā)展起來的一個重要的交叉。對于一個復雜的系統(tǒng)，很多時候我們不能夠單獨通過分析系統(tǒng)內(nèi)元組來反應系統(tǒng)性質。復雜系統(tǒng)是由微觀層次上的海量個體所組成，個體之間存在著作用。把個體抽象為網(wǎng)絡節(jié)點，而個體之間的相互作用抽象為節(jié)點之間的邊，則復雜系統(tǒng)就可以用一個復雜網(wǎng)絡來描述。
本文的實驗數(shù)據(jù)集包含22 個正常組織樣本和40個結腸癌組織樣本，每個樣本包含 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個基因在正常組織樣本和結腸癌組織樣本中的中表達水平的均值；σ12(i)，σ22(i)分別為該基因表達水平的標準差。
根據(jù)上式計算結腸癌基因表達數(shù)據(jù)中的2000個基因的分類信息指數(shù)，大部分基因的分類信息指數(shù)在0到0.2之間，僅有少部分基因的大于 0.2（如圖1）。保留指數(shù)大于 0.2 的314個基因用于下一步的分析，這樣就大大縮小了基因選擇的特征空間，剔除掉大量“無關基因”，大大縮小需要搜索的致癌基因范圍。
另外在撰寫本文的準備過程中，我們查閱了大量的有關文獻。與已有文獻的結果進行比較，發(fā)現(xiàn)所選特征基因中包含了一些已被實驗證實的與癌癥相關的重要基因，這些基因在癌癥基因調(diào)控網(wǎng)絡中起關鍵作用，一共得到了40個基因（如表1）。我們要探尋的結腸癌的特征基因極有可能包含在這40個基因中，這對我們后續(xù)的研究具有重要的參考價值。其中6個基因在我們根據(jù)分類信息指數(shù)值對數(shù)據(jù)進行篩選的過程中被剔除了。所以我們選擇剩下的34個基因作為我們研究的參考（如表1）。
然后分別計算結腸癌樣本(cancer)和正常樣本(normal)各個基因間的相似性，得到相似矩陣。分析這些基因點的聯(lián)系，選擇一個相似性的閾值來分別建立復雜網(wǎng)絡，用鄰接矩陣表示。（如果相似性大于該閾值的則這兩個點相連接，在鄰階矩陣中用1表示；反之，如果相似性小于于該閾值的則這兩個點不連接，在鄰階矩陣中用0表示）。其中關鍵的步驟是閾值的選取。本文提出的解決策略是，從關聯(lián)系數(shù)矩陣得到最小生成樹作為基因之間關系的骨架，然后再把文獻中發(fā)現(xiàn)的相關基因之間的關系考慮進來，得到客觀的閾值。
我們考查結腸癌基因表達數(shù)據(jù)中篩選出來的314個變化比較明顯的基因，用向量組表示為，
其中T0m,n是第n個基因在第m個樣本的基因數(shù)據(jù)，其中N=314，M是樣本個數(shù)，正常組織樣本個數(shù)為22，腫瘤組織樣本個數(shù)為40。相關系數(shù)矩陣為R：
那么基因間的歐幾里得距離就可以用以下定義的距離矩陣D定量描述：
最小生成樹是圖論中的基本概念。我們從距離矩陣中抽取出最小生成樹，用N-1條邊連接所有基因節(jié)點，形成一個無圈圖。在形成的最小生成樹中，要保證所有基因間的距離之和最小，也即相關系數(shù)之和最大，且是無圈圖。那么，基因間的其它關系就被過濾掉了。原則上來講，真正直接相關的基因之間的關聯(lián)系數(shù)最大，因此可以認為最小生成樹保留了基因之間的真正關系。因為一個基因可以和多個基因直接相關，所以很多的關系被丟掉。丟掉的關系將在后邊的步驟中被找回。我們采用Kruskal算法來生成最小生成樹：
我們用篩選后的314個基因數(shù)據(jù)（我們對這314個基因重新做了編號，其與原數(shù)據(jù)庫中的編號的對應表見附表），對結腸癌樣本、正常樣本分別用兩種方法得到了最小生成樹。兩個最小生成樹的節(jié)點也即基因，一定是相同的，且都有314個節(jié)點，313條邊。圖2給出了正常樣本中得到的最小生成樹。
如前所述，最小生成樹給出了基因之間的部分連接，但是很多基因之間的關系被丟掉。另一方面，文獻中發(fā)現(xiàn)的結腸癌相關基因，為我們提供了重要的參考信息，但是這些信息包含著很大的偶然性，也就是噪聲。在此我們將把這兩部分信息整合在一起，得到一個客觀的構建基因關系網(wǎng)絡的閾值。
我們首先抽取出如圖2所示的生成樹。它給我們提供了高可信度的鏈接，不足之處是包含的信息不夠多，一些重要的關系被忽略了。我們再根據(jù)得病前后兩類樣本信息變化。然而，這里也可能產(chǎn)生噪聲邊。
從上面得到最小生成樹出發(fā)。整合相關文獻中已知的腫瘤致病基因，我們收集到34個這樣的基因。用這34個基因重復上面的過程，得到閾值，腫瘤樣本的記為DDIImin，在正常樣本的生成樹中記為DNIImin建立網(wǎng)絡。，它們之間可能直接相連，也可能彼此沒有直接相連。計算直接相連的節(jié)點間的距離。在這個過程中，我們選取最大的那個作為閾值，在腫瘤樣本生成樹中記為DDIImin=0.6239，在正常樣本的生成樹中記為DNIImin=0.6995。
我們選取DDIImin，DNIImin作為閾值，來建立網(wǎng)絡。這樣在一定程度上減少了一些噪聲邊的產(chǎn)生，避免了偶然因素可能引起的閾值選取的不穩(wěn)定性，同時也恢復了我們需要的連接。
腫瘤樣本網(wǎng)絡以及正常樣本網(wǎng)絡的閾值選定后，利用我們在數(shù)據(jù)處理中選定的314個基因建立網(wǎng)絡。以腫瘤樣本網(wǎng)絡為例，先算出腫瘤樣本中這314個基因的相關系數(shù)矩陣。當任意兩個基因的相關系數(shù)大于閾值0.6239時，我們就認為這兩個基因是有相互作用的，在它們之間畫一條邊；當任意兩個基因的相關系數(shù)小于閾值0.6239時，我們就認為這兩個基因是沒有相互作用的，它們之間就沒有直接的邊相連。這樣我們就得到了腫瘤樣本的基因相互作用網(wǎng)絡。在相關系數(shù)矩陣中，把大于0.6239的值改為1，小于0.6239的改為0，主對角線上元素設為0，這樣就由相關系數(shù)矩陣得到了鄰接矩陣MD。鄰接矩陣中的1就表示網(wǎng)絡中有連邊；鄰接矩陣中的0就表示網(wǎng)絡中沒有連邊。
復雜網(wǎng)絡的結構是不均勻的，往往存在很多連接致密的集團，在這些集團之間只有很少邊形成的松散的連接。這些致密的結構往往與功能有著密切的關系，因此受到普遍的關注。當前普遍采用的劃分社區(qū)的方法是Newman-Girvan算法。
社區(qū)劃分反映基因間的功能關系，而在網(wǎng)絡模塊中，可以發(fā)現(xiàn)網(wǎng)絡發(fā)生了明顯的改變。首先我們畫出正常樣本網(wǎng)絡，用Newman-Girvan的劃分算法對得到的網(wǎng)絡進行分塊。當把正常樣本網(wǎng)分成14個社區(qū)時，得到的聚類系數(shù)最大，為Q=0.596（如表2），這樣就把網(wǎng)絡分成了14個大的功能模塊。如圖3所示，即為正常樣本網(wǎng)絡的社區(qū)結構（每種顏色代表一個社區(qū)）。可以看出，各個社區(qū)結構中的節(jié)點數(shù)目分布并不均勻，并且存在很多孤立節(jié)點。社區(qū)內(nèi)節(jié)點間的連接比較緊密，而不同社區(qū)間的連接比較稀疏。
同樣用Newman-Girvan的劃分算法，我們畫出腫瘤樣本的網(wǎng)絡，把腫瘤樣本網(wǎng)分成了13社區(qū)（如圖4）。此時得到的聚類系數(shù)最大，為Q=0.630（如表3）?？梢钥闯觯[瘤樣本網(wǎng)絡的各個社區(qū)結構中的節(jié)點數(shù)目分布也是并不均勻，并且同樣存在很多孤立節(jié)點。社區(qū)內(nèi)節(jié)點間的連接比較緊密，而不同社區(qū)間的連接比較稀少。
對于兩個網(wǎng)絡，我們計算出每個節(jié)點的度（degree）。我們發(fā)現(xiàn)，，，其中DDmax、DNmax分別表示腫瘤樣本、正常樣本的鄰接矩陣中節(jié)點的最大度，DDmin、DNmin分別表示腫瘤樣本、正常樣本的鄰接矩陣中節(jié)點的最小度。說明網(wǎng)絡中的有些點與其他點的相互作用強度發(fā)生了明顯的變化。反應到網(wǎng)絡結構中，可以用平均度加以粗略說明，其中腫瘤樣本網(wǎng)絡的平均度為9.36，正常樣本網(wǎng)絡的平均度為5.28。在腫瘤樣本網(wǎng)絡中每個基因平均與周圍9.36個基因有相互作用，在正常樣本網(wǎng)中每個基因平均與周圍5.28個基因有相互作用。
分析度的變化。通過兩個網(wǎng)絡的度序列做差，我們就能夠找到每個節(jié)點度的變化情況。表4即為度變化比較大的前十個節(jié)點。
同時我們對每個節(jié)點度的變化值做平均，得到度變化的平均值為7.0637。其中大于這個平均變化度的節(jié)點有89個，小于這個平均變化度的節(jié)點有255個。
我們認為特征基因在這些度變化比較大的節(jié)點中的可能性很大。度變化超過平均值的節(jié)點與我們查閱的的文獻中得出個34個特征基因相比對，其中有15個基因是它們所共同擁有的（如表5），我們認為這15個基因應該是對我們尋找結腸癌特征基因非常重要的基因。
接下來對我們得到了15個重要的基因節(jié)點，在網(wǎng)絡中分析它們。在上一步過程中，我們比較了文獻中得出的，且度變化較大的15個重要節(jié)點。這15個基因在腫瘤特征過程中起了很重要的作用。注意到我們選取的這15個基因最大的度變化值是33，但還有7個節(jié)點的度變化值超過了33，卻并不在我們查閱的文獻的結論中，我們認為有必要在網(wǎng)絡中進一步對這些點進行分析。這7個基因節(jié)點分別是（如表6）：
表6
其中，度變化是同一節(jié)點在腫瘤樣本網(wǎng)絡與正常樣本網(wǎng)絡中，該節(jié)點在兩個網(wǎng)絡中度的變化值；分類信息指數(shù)編號是指該信息指數(shù)在所有信息指數(shù)中從大到小排列時的次序，我們選取的314個基因是分類信息指數(shù)IIC＞0.2的基因，也即分類信息指數(shù)編號前314個基因。通過上面的表格我們可以看出，這些基因的分類信息指數(shù)都比較大。通常地，樣本們會去研究IIC大的點，分類信息指數(shù)編號偏后的那些基因極易在分析的過程中被忽略掉?，F(xiàn)在我們發(fā)現(xiàn)，這些點在兩個網(wǎng)絡中度的變化值很大，也即癌變前后這些基因在網(wǎng)絡中與其它基因的相互作用有了很大的變化。接下來，我們將這7個基因和另外15個基因分別放回正常樣本和腫瘤樣本的網(wǎng)絡中去分析它們的變化。如圖5，圖6。
圖5為我們找到的15個重要基因在正常樣本中的相對位置。不同的顏色表示不同的社區(qū)。同時把度變化最大的7個節(jié)點（156，87，300，139，169，61，34）也放進了網(wǎng)絡中。
圖6為我們找到的15個重要基因在腫瘤樣本中的相對位置。不同的顏色表示不同的社區(qū)。同時把度變化最大的7個節(jié)點（156，87，300，139，169，61，34）也放進了網(wǎng)絡中。
從圖5中可以觀察出，在正常樣本網(wǎng)絡中，度變化最大的7個節(jié)點分別分布在4個社區(qū)中，且僅有一個節(jié)點與其它節(jié)點相連（節(jié)點61―節(jié)點68）。這說明7個節(jié)點在正常樣本網(wǎng)絡中沒有明顯的相互作用。而通過觀察圖6，我們的發(fā)現(xiàn)在腫瘤樣本網(wǎng)絡中，度變化最大的7個節(jié)點同時分布在同一個社區(qū)中，且這7個節(jié)點與我們找到的15個重要基因節(jié)點中的9個節(jié)點（分別為68、180、155、270、213、198、207、2、297）也在同一社區(qū)中（圖6中藍色表示的社區(qū)），并相連。我們有一個大膽的猜想，結腸癌的特征基因就分布在藍色所表示的社區(qū)中。藍色社區(qū)中的這16個節(jié)點所代表的基因分別為M22382，T96873，U09564，H08393，J02854，T62947，M59040，H20709，X62048，及M94556，T70062，L28010，M37583，H89087，H64807，T65740，從功能上看，這些基因對結腸癌的癌變過程發(fā)揮了重要的作用。在正常樣本網(wǎng)絡中，這些點分布的比較分散，而在腫瘤樣本網(wǎng)絡中，這些點集中到了同一社區(qū)中，說明癌變后這些基因之間的相互作用加強。所以這16個基因就是我們要尋找的結腸癌的特征基因。另外，除了這些在同一社區(qū)的節(jié)點之外，還有一些散節(jié)點落在各個不同的社區(qū)中，其中分為兩種情況，一種是該基因位于兩個社區(qū)的連接點處，如節(jié)點58（T60155），它是主動脈平滑肌肌動蛋白，而有研究表明肌動蛋白參與DNA轉錄，所以T60155是我們所尋找的結腸癌的特征基因。另一種是某社區(qū)內(nèi)部的節(jié)點，如節(jié)點83（T51571）,130（H43887），219（L41559）,248（M36634），參照這些基因的功能對基因的癌變并沒有起到?jīng)Q定性的作用。并且這幾個點的度變化值也不是很大，所以，可能是被誤選入的，應該被排除掉。綜上，本文運用復雜網(wǎng)絡的方法，通過社區(qū)模塊的劃分，找出17個結腸癌的特征基因。
本文首先通過分類信息指數(shù)這一指標對數(shù)據(jù)做了初步處理，篩選出314個基因節(jié)點，剔除了大量的無關基因，對數(shù)據(jù)進行過濾和降維。并以此分別構建網(wǎng)絡模型。生成網(wǎng)絡之后，通過Newman-Girvan方法對我們的網(wǎng)絡模型劃分社區(qū)和評價，無論是腫瘤樣本網(wǎng)絡還是正常樣本網(wǎng)絡都是很好的社區(qū)結構。我們利用度變化值和參考我們查閱文獻中得出的結論，挑選出了22個基因，其中排除掉5個基因后，得出了我們的結論，即結腸癌的特征基因有17個。
本文問題研究還有待于進一步加深完善，比如沒有考慮到基因篩選后提出的變化不大的點。另外，我們對于生物醫(yī)學方面的專業(yè)知識比較欠缺，在對模塊進行分析的時候，對模塊的功能分析不夠精確。這需要我們以后的繼續(xù)努力和學習。
摘要：以股票為節(jié)點，選取適當閾值量化股票收益率序列間相關關系從而構建復雜金融網(wǎng)絡?；趶碗s網(wǎng)絡的理論，討論金融網(wǎng)絡的度分布、平均最短路徑和聚集系數(shù)，發(fā)現(xiàn)面向金融時間序列的股票網(wǎng)絡具有小世界效應，無標度特性和一個很重要的特性―自相似性。該文用兩種方法分析了網(wǎng)絡的自相似性：一是提出用網(wǎng)絡節(jié)點的度構造Hurst指數(shù)，定量分析金融網(wǎng)絡的自相似性；二是金融網(wǎng)絡的平均路徑長度和聚集系數(shù)定性地分析了復雜網(wǎng)絡的自相似性。
關鍵詞：金融市場；復雜網(wǎng)絡；無標度；自相似
證券市場素有經(jīng)濟晴雨表之稱。證券市場由于受企業(yè)經(jīng)濟效益，居民收入水平，投資者的心態(tài)等諸多因素影響，所以它是一個涵蓋大量信息的復雜系統(tǒng)。近年來以復雜網(wǎng)絡角度理解和分析證券市場，構建金融網(wǎng)絡的方法層出不窮。Boginski [1]等研究了美國證券市場6546支股票，發(fā)現(xiàn)股票相關性呈現(xiàn)無標度性。莊新田[2]等基于相關系數(shù)構建以上海證券交易所持續(xù)交易的股票為節(jié)點的復雜網(wǎng)絡，討論上海證券市場的股票價格波動，魯巍巍[3]等對滬深A股構建復雜網(wǎng)絡，計算網(wǎng)絡的聚集系數(shù)，吸引率，討論不同行業(yè)的聚合強度及其對滬深A股市場股價波動的影響，這些研究都是基于網(wǎng)絡的拓撲結構特征：節(jié)點度分布、平均路徑長度、聚集系數(shù)、吸收率等，都從網(wǎng)絡節(jié)點對網(wǎng)絡的影響程度方面考慮，對于復雜金融網(wǎng)絡的另一特性――自相似性并無研究。
復雜網(wǎng)絡的自相似性是指網(wǎng)絡局部和整體在某些特征上相似。對于固定網(wǎng)絡自相似性的研究一般是利用節(jié)點內(nèi)部互動性來探測網(wǎng)絡的演化過程。自相似系數(shù)的測量方法是由 C.M.Song與S.Havlin[4]提出利用重構化測量，以及R.Guimera,L.Danon[5]提出利用郵件系統(tǒng)測量社區(qū)結構的相似性，他們也用這些方法描述了一些現(xiàn)實網(wǎng)絡的自相似性[4]。
1 復雜金融網(wǎng)絡建模
1.1 數(shù)據(jù)來源
筆者隨機抽取從2007年9月28日至2010年2月26日滬深A股的500只股票作為研究對象。根據(jù)每只股票月數(shù)據(jù)的開盤價、收盤價、最高價和最低價平均值計算股票的對數(shù)收益率，然后用對數(shù)收益率序列建立相關關系，通過相關關系數(shù)值化研究復雜金融網(wǎng)絡的拓撲特征[6]。
1.2 復雜金融網(wǎng)絡建模
以滬深A股為節(jié)點，股票相互影響關系為連邊構建無權無向網(wǎng)絡。設股票i在第t時刻的平均價為xi(t)，xi(t)為股票i在t時刻開盤價，收盤價，最高價和最低價的平均值。
為股票i對數(shù)收益率。定義股票i和股票j的相關系數(shù)為：
其中E(yi)表示股票i在n期的平均收益率，
由定義知：ρij的值域為[-1，1]。若ρij=1，表示股票i和股票j完全正相關，表現(xiàn)為同向增長或降落；若ρij=－1，表示股票i和股票j完全負相關，表現(xiàn)為反向變化；若ρij=0，股票i和股票j完全不相關。計算n只股票對數(shù)收益率的相關系數(shù)，得到一個n×n階對稱相關系數(shù)矩陣p。選取合適的閾值，將系數(shù)矩陣p進行量化，得到一個只有0和1的稀疏矩陣，此矩陣便作為金融網(wǎng)絡的鄰接矩陣。
1.3 復雜金融網(wǎng)絡的拓撲結構特征
1.3.1 節(jié)點度分布
節(jié)點度是指連接節(jié)點的邊數(shù)，節(jié)點度分布是指一個任意選擇節(jié)點恰好度數(shù)為k的概率，也等于網(wǎng)絡中節(jié)點度數(shù)為k的節(jié)點數(shù)占網(wǎng)絡節(jié)點總數(shù)百分比，用分布函數(shù)p(k)來表示。
1.3.2 平均最短路徑長度
若一個包含n個節(jié)點的無向網(wǎng)絡，，其中dij為節(jié)點i和節(jié)點j的最短距離，也是節(jié)點i,j最短路徑所經(jīng)過的邊數(shù)?？紤]到每個節(jié)點到期自身的距離為0，無關聯(lián)節(jié)點的距離為無窮大，此時存在問題，所以對進行修改，得到“調(diào)和平均”最短路徑長度。在股票網(wǎng)絡中，平均最短路徑長度是任意兩只股票相關中介數(shù)量的平均值，反映網(wǎng)絡的大小和分離程度。
1.3.3 聚集系數(shù)
考慮節(jié)點i，它通過ki條邊和其他ki個網(wǎng)絡節(jié)點相連接，則它們之間最多有ki(ki－1)/2條邊連接，但ki個節(jié)點實際有Ei條邊，所以節(jié)點i的聚集系數(shù)ci，，網(wǎng)絡的平均聚集系數(shù)為。聚集是用來刻畫網(wǎng)絡的小集團形態(tài)，說明鄰近集團在相關性意義上的凝聚程度。
2 復雜金融網(wǎng)絡的自相似性研究
相識性是現(xiàn)實世界客觀存在的一種現(xiàn)象，描述相識性的方法一般分為兩種：一種是將對象看作為某k個維特征空間的點，對象的相似由點與點間的距離來確定，另一種衡量相似性方法是比較對象之間的一般特征和一些典型特征。自相似性是一種特殊的相似，是對象本身的一種特性，是對象局部和整體相似。
雖然C.M.Song等用重構化能測量網(wǎng)絡的自相似性，但此時網(wǎng)絡只能是固定結點的網(wǎng)絡，而現(xiàn)實生活中的網(wǎng)絡是動態(tài)增長的過程，如社會網(wǎng)中每個人認識的朋友數(shù)在不斷地增加，隨著市場經(jīng)濟的完善，上市公司數(shù)量越來越多，在證券交易所交易的股票數(shù)量也在不斷的更新和變化。鑒于這些動態(tài)變化的網(wǎng)絡，本文分別采用以下兩種方法來研究復雜金融網(wǎng)絡的自相似性
2.1 基于R/S分析的金融網(wǎng)絡自相似性分析
設網(wǎng)絡為動態(tài)增長的，網(wǎng)絡節(jié)點不斷地增長記為n1,n2,…ni，計算節(jié)點在ni時度分布的累積極差R(k)和標準差S(k)。
設x(k)為網(wǎng)絡節(jié)點是ni時各節(jié)點的度數(shù)，的均值，也為網(wǎng)絡的平均度數(shù)。
累積極差R(k)：R(k)=max x(k,ni)-min x((k,ni)
標準差S(k)：，則關系式為，
R/S為重標極差，H為Hurst指數(shù)，所以
具體計算：以ln ni為自變量，lnR/S為因變量采用最小二乘進行線性擬合，所得直線的斜率即為H的估計值
復雜網(wǎng)絡自相似性與Hurst指數(shù)的關系[6]
若0≤H
若H=0.5， 說明復雜網(wǎng)絡節(jié)點是互相獨立的，度分布是隨機的。
若0.5
2.2 基于容量維數(shù)的自相似性分析
基于分形思想，用半徑為r的尺子去測長度為l的尺子，所需尺子個數(shù)為
用半徑為r的小圓去覆蓋面積為S的圓，所需小圓個數(shù)為
用半徑為r的小球去覆蓋體積為V的球，所需小球個數(shù)為
以此類推可用半徑為r的客體去覆蓋被測對象，所需個數(shù)N(r)的值與r的取值關系表示為，
定義D為相似容量維數(shù)，取對數(shù)得相似容量維數(shù)[7]
本文計算平均最短路徑長度和聚集系數(shù)的D來分析復雜金融網(wǎng)絡自相似性
3 實證分析
由于本文是分析動態(tài)復雜網(wǎng)絡的自相似性，所以用不同數(shù)量的股票來構造網(wǎng)絡。
1） 分別用200，250，300，350，400，450，500不等數(shù)量的股票構造金融網(wǎng)絡，然后基于R/S分析用各網(wǎng)絡節(jié)點度分布來求Hurst指數(shù)，在matlab編程基礎上得到H=0.823，可知復雜金融網(wǎng)絡具有自相似性。取閾值為0.85，構建股票網(wǎng)絡并計算各網(wǎng)絡的平均最短路徑長度和聚集系數(shù)。
實證研究發(fā)現(xiàn)在網(wǎng)絡平均度數(shù)緩慢增長時，網(wǎng)絡平均路徑長度和聚集系數(shù)呈現(xiàn)相似的變化趨勢，這也是網(wǎng)絡拓撲特性自相似性表現(xiàn)。
2） 選用200,250,300,350,400,450,500只股票分別構造金融網(wǎng)絡，用比較分析法分析金融網(wǎng)絡的自相似性。
比較300，400，500只股票時相關系數(shù)的概率分布，然后采用修正法[3]求相關系數(shù)的概率分布。文獻[3]提出采用修正法求相關系數(shù)矩陣，來消除時間因素的影響。但筆者認為不能做修正，盡量保持原有信息，這才能反應真實的市場環(huán)境。因為首先證券股票市場存在在投機行為，趨利性等很容易造成追殺跌漲的“羊群效應”，其次證券市場受到經(jīng)濟周期和行業(yè)因素的影響，而每個行業(yè)都要經(jīng)歷幼稚期、成長期、成熟期、衰退期的發(fā)展演變過程，這個過程成為行業(yè)生命周期，再次證券市場還受到產(chǎn)業(yè)政策等影響。筆者用修正法[3]對300,400,500只股票構建的網(wǎng)絡進行了修正，得到圖3~圖4。
顯然修正后的相關系數(shù)的概率密度是正態(tài)分布，符合強勢有效市場的假設，但中國證券市場目前狀況是弱勢有效市場，證券價格只能反映歷史信息，還存在內(nèi)幕信息等，所以本文不對收益序列做任何修改。
在閾值為0.85時各股票網(wǎng)絡都表現(xiàn)出很好的無標度特性（如表1所示）：(最小二乘法)。
給出在閾值為0.85時節(jié)點為300、400、500的度分布圖1。
以500只股票構造的網(wǎng)絡為整個復雜網(wǎng)絡，300只和400只都為局部小網(wǎng)絡，得到容量相似維數(shù)。
從表2中可以看出Dl,Dc都比較相近，所以得動態(tài)的網(wǎng)絡也具有自相似性。
4 結束語
本文基于復雜網(wǎng)絡的理論分析了金融市場的網(wǎng)絡特性―小世界效應和無標度特性。無標度則表示網(wǎng)絡節(jié)點分布不均勻，網(wǎng)絡中有地位比較重要的“中心點”，可知股票市場存在影響力比較大的股票或是行業(yè)。實證研究結果得出，金融網(wǎng)絡的冪律指數(shù)大概為1，這與莊新田[2]等人得出上海證券市場網(wǎng)絡的冪律指數(shù)為0.8219和0.7930差異不大。本文還著重介紹了兩種方法分析金融網(wǎng)絡的自相似性，這說明金融市場變化趨勢有一部分依賴于過去，到底依賴程度有多少，就需看整個金融市場自相似程度，這便成了下一步的研究內(nèi)容。
面對越來越復雜的網(wǎng)絡環(huán)境及應用,今天的企業(yè)用戶需要的已經(jīng)不僅僅是一個傳統(tǒng)意義上的產(chǎn)品或者系統(tǒng),他們需要自己的IT應用發(fā)揮更大的價值,實現(xiàn)與客戶之間的交互、員工生產(chǎn)力的優(yōu)化以及企業(yè)資源的整合等,并通過這些方面的整合提升企業(yè)的運營效率。視頻會議作為提高溝通效率的有效方式,滿足了人們?nèi)轿坏慕涣餍枨?因而在近年來取得了飛速的發(fā)展。
目前,國外從事視頻會議系統(tǒng)研制、生產(chǎn)的大公司大多已經(jīng)進入中國市場,國內(nèi)也有越來越多的企業(yè)積極參與到市場競爭中來,在競爭越來越激烈的情況下,視頻會議系統(tǒng)供應商必須充分發(fā)揮自身的優(yōu)勢,才能搶占更大的市場份額。北京盛維新世紀網(wǎng)絡通信技術有限公司是一家專注于網(wǎng)絡多媒體通訊軟件開發(fā)及服務的高新技術企業(yè)。作為全球少數(shù)真正全面掌握多媒體通訊核心技術的企業(yè),盛維公司在過去幾年中密切關注用戶的使用需求,并在其Cenwave多媒體通訊軟件平臺上開發(fā)出網(wǎng)絡視頻會議系統(tǒng)、網(wǎng)絡直播系統(tǒng)、網(wǎng)絡實時課堂、多方電話會議等多種視頻應用產(chǎn)品。
全面靈活的解決方案
由于我國存在比較復雜的運營商網(wǎng)絡環(huán)境,企業(yè)的出口網(wǎng)絡一般較窄,為了確保用戶在任何情況下都能夠成功召開遠程會議,盛維公司為用戶準備了一整套遠程會議綜合解決方案,可以為客戶提供基于不同終端、多種實現(xiàn)方式融合的、系統(tǒng)化的視頻服務支持。北京盛維新世紀通信技術有限公司總裁魏松祥表示:“我們正在向用戶交付一個真正兼容的平臺,能夠兼容不同網(wǎng)絡、不同種類的終端設備,實現(xiàn)語音、視頻、數(shù)據(jù)的全面整合。讓用戶可以在任何時間、任何地點、和任何人進行多媒體的溝通和交流,實現(xiàn)協(xié)同辦公?！?
相比較市場上其他服務商提供的解決方案,盛維遠程會議綜合解決方案全面涵蓋了軟件視頻會議系統(tǒng)、硬件視頻會議終端、軟硬混合視頻會議系統(tǒng)、MCU租用、電話會議租用、網(wǎng)絡會議租用等各種產(chǎn)品與服務,并能夠根據(jù)客戶的需求提供這一系列產(chǎn)品與服務的組合,真正做到實現(xiàn)客戶各種形式、各種應用環(huán)境下“成功召開遠程會議”的目標。
魏松祥告訴記者,在盛維提供的純軟件高清視頻會議解決方案中,用戶只需通過普通的PC機、麥克風、攝像頭就能夠輕松在互聯(lián)網(wǎng)上召開網(wǎng)絡會議。對于關注成本的中小企業(yè)用戶來說,盛維軟件高清視頻會議解決方案可以讓它們以最小成本實現(xiàn)遠程視頻會議的召開。而基于硬件的高清視頻會議終端主要是為了滿足大中型企業(yè)客戶的應用需求,系統(tǒng)采用了高集成度、嵌入式的設計模式,是一款體積小巧、外形美觀、穩(wěn)定可靠的硬件會議終端。
此外,為了加快網(wǎng)絡視頻會議在中小型企業(yè)市場的普及,盛維以顛覆性的思維推出了網(wǎng)絡視頻會議租用服務,為企業(yè)提供了低風險、低投入、實施簡單的視頻應用服務。在這種服務模式下,一切網(wǎng)絡基礎設施、軟件平臺、硬件平臺的建設和維護工作都由盛維公司提供,當用戶需要使用網(wǎng)絡視頻會議時,只需向盛維申請開通網(wǎng)絡會議服務,獲得登錄賬號就可以召開遠程網(wǎng)絡視頻會議。這種獨創(chuàng)性的租用服務模式,使得企業(yè)無需購買任何系統(tǒng)軟件、硬件設備,無需租用昂貴的服務器帶寬,也無需專業(yè)IT人員維護就可以輕松召開遠程視頻會議,真正做到幫助企業(yè)降低運營成本,提高工作效率。
覆蓋全球的運營網(wǎng)絡
多媒體視訊服務需要堅實可靠的網(wǎng)絡來支撐。在全球化的時代,用戶的溝通對象可能在全國乃至世界各地。一個網(wǎng)絡會議運營網(wǎng)絡不但需要能充分覆蓋國內(nèi),也要能較好覆蓋世界各地。盛維在發(fā)展過程中,逐步建立起一個覆蓋面廣、通信質量可靠的面向全球用戶的網(wǎng)絡會議運營網(wǎng)絡,通過這個網(wǎng)絡平臺可以保證高清視頻會議系統(tǒng)的穩(wěn)定運行。
盛維網(wǎng)絡會議運營網(wǎng)絡為租用盛維網(wǎng)絡會議的客戶提供了一個高速的專用網(wǎng)絡,確保用戶在這個平臺上能召開高質量的網(wǎng)絡會議。同時盛維還與全球各地的電信運營商建立了緊密合作關系,把電話網(wǎng)成功對接到這個運營網(wǎng)絡上。用戶能以極低廉的資費召開電話會議,或者實現(xiàn)電話會議與網(wǎng)絡視頻會議的混合使用。
魏松祥表示,盛維運營網(wǎng)目前已經(jīng)覆蓋了全國所有地區(qū),在主要骨干網(wǎng)上部署了上百臺服務器,總帶寬達到將近2Gbps。同時,盛維公司在亞太地區(qū)、北美與歐洲也部署了眾多服務器,其運營網(wǎng)絡能全面覆蓋亞洲、北美以及歐洲等地。此外,為了確保用戶在盛維運營網(wǎng)上的通信安全保密,盛維公司采用了嚴格的安全策略以及256位數(shù)據(jù)加密算法,并且有專業(yè)運維團隊7×24監(jiān)控服務器與網(wǎng)絡。
憑借出色的技術能力,盛維系列產(chǎn)品目前已應用政府、軍隊、教育、醫(yī)療、金融、能源、IT等多個行業(yè)。在國內(nèi)教育行業(yè),更是取得市場占有率60%的業(yè)績。魏松祥告訴記者:“每天全球有數(shù)萬用戶在使用我們的產(chǎn)品及服務,并且已有上百家客戶使用我們提供的產(chǎn)品成功召開1000人以上大規(guī)模會議或遠程培訓。”憑借以上出色的表現(xiàn),在2009年6月,盛維公司一舉榮獲第十三屆中國國際軟件博覽會“獻禮新中國成立60周年?中國軟件行業(yè)最具成長力企業(yè)獎”。
可以說,在工業(yè)化與信息化日益融合的大趨勢下,盛維公司給企業(yè)信息化選型創(chuàng)造了有利的條件,降低了企業(yè)視頻應用的門檻。某種意義上講,盛維公司正在改變傳統(tǒng)多媒體通訊軟件銷售的模式,為企業(yè)提供了低風險、低投入、實施簡單的信息化方案,使企業(yè)通過互聯(lián)網(wǎng)便可以享受到相應的軟件和維護服務,切實做到了幫助企業(yè)降低運營成本,提高工作效率。
摘 要：提出一種基于復雜網(wǎng)絡的風險傳播模型及有效算法，通過結合復雜網(wǎng)絡中傳播蔓延現(xiàn)象的推廣模型，將風險傳播模型劃分為兩種：主動型風險傳播模型與被動型風險傳播模型。并對已有風險傳播算法進行改進，實驗表明，該模型及算法能健全風險傳播機制，提高傳播速度與精確度。
關鍵詞：復雜網(wǎng)絡；推廣模型；風險傳播
1 引 言
隨著網(wǎng)絡安全問題的日益突出，風險評估越來越受到人們的重視。風險評估一般分為靜態(tài)評估和動態(tài)評估兩種，前者評估體系比較完善，評估精確性程度較高，但缺點是評估周期過長，評估模型可能隨著時間的推移而不能適用，不能反映網(wǎng)絡的實時信息；后者評估能根據(jù)網(wǎng)絡狀況適時的做出風險估計，能及時反映網(wǎng)絡風險的動態(tài)變化，性能好于靜態(tài)評估[1，2]。而針對動態(tài)風險評估的研究有：基于免疫的網(wǎng)絡安全風險檢測的模型[3，4]，是一種基于入侵時的檢測模型；基于隱馬爾可夫模型的網(wǎng)絡風險評估方法研究[5，6]；基于貝葉斯模型的網(wǎng)絡風險動態(tài)評估方法[7，8]， 可以對網(wǎng)絡的總體風險和局部要素可能引起風險的程度進行評估。以上文獻對網(wǎng)絡入侵檢測研究較為深入，但側重于對攻擊的動態(tài)評估，未能考慮已有風險如何擴散與轉移。針對網(wǎng)絡風險傳播，張永錚等提出了用于評估網(wǎng)絡信息系統(tǒng)的風險傳播模型[9]和一種求解網(wǎng)絡風險傳播問題的近似算法[10]，對已有風險在網(wǎng)絡中的傳播進行研究，但其傳播模型與算法存在一些缺點：首先，模型中僅考慮了風險傳播模型，未能考慮風險引入模型；其次，一個部件上可能存在多個弱點，則該部件對另一部件的同一方向的可信訪問路徑可多于一種，則部件不能在有向圖中被視為圖節(jié)點。第三，最小入度的部件感染風險的概率較低，因此其作為風險源的概率不高。第四，若入度最小的部件已經(jīng)感染風險，其出度不一定是最大的，正如流感爆發(fā)在人口密集的地區(qū)一樣，則其風險不能立即傳播出去，存在滯后性，時效性欠佳。
本文在針對網(wǎng)絡風險傳播問題，結合復雜網(wǎng)絡中傳播蔓延現(xiàn)象的推廣模型 [11，12]，提出了一種網(wǎng)絡風險傳播模型及相關定義，并改進了風險傳播算法。
2 推廣模型下的風險傳播
網(wǎng)絡信息的動態(tài)風險不僅僅表現(xiàn)為一般意義的風險，其傳播可能會對社會造成不可估量的損失，如病毒的傳播造成的跨域風險、有害信息的傳播造成的社會風險等。為此我們將借鑒復雜網(wǎng)絡的傳播機理和分析的方法，研究網(wǎng)絡風險傳播模型。
按照復雜網(wǎng)絡的傳播蔓延現(xiàn)象的推廣模型[11，12]：假設網(wǎng)絡中有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)絡風險移除狀態(tài)，即僅考慮風險在整個網(wǎng)絡中如何轉移，而未考慮網(wǎng)絡風險傳播后所造成情況的如何消除。因此上述推廣模型應用于風險傳播如下：
計算技術與自動化2016年6月
第35卷第2期呂元海等：基于復雜網(wǎng)絡的風險傳播模型及有效算法
每一時刻t，風險結點j對其直連結點i每發(fā)動一次攻擊，就會從被攻擊結點i中獲取一定的信息劑量di（t），則在過去T時期中風險結點獲取被攻擊結點的信息總劑量為：
3 風險傳播模型
3.1 相關定義
定義1.結點：指網(wǎng)絡系統(tǒng)中任意一臺網(wǎng)絡設備上任意可能被利用的最小單元。其中已經(jīng)被利用的稱為風險結點，而尚未被利用的稱為非風險結點。
定義2.有向路徑：結點A訪問結點B時，形成的從A指向B的單向訪問關系。這里所說的單向訪問關系是指合法或非法的、由主動發(fā)起方指向被訪問方的訪問，而不代表實際信息傳輸?shù)穆窂?，因為嚴格的講，任何兩個相連結點之間的鏈路都是雙向的。有向路徑概率即為結點訪問概率。
定義3.風險傳出：指風險結點對其所訪問的任一結點造成的損失或影響。
定義4.風險引入：指非風險結點訪問風險結點時，由于存在實際信息的交換而受到該風險結點的影響。
這里舉例說明一下定義3、4，某病毒利用空氣（相當于網(wǎng)絡中的信息交換鏈路）進行傳播，當病體A主動接觸易染體B時，A將病毒傳播給B，其中A主動接觸B即為A訪問B，病毒傳播方向為A到B；反之當易染體B主動接觸病體A，也會被感染，同樣病毒傳播方向為A至B，但為B訪問A。
定義5.風險傳出公式：設結點n被成功利用的概率為Pn，被利用后對網(wǎng)絡系統(tǒng)的危害程度為Wn，利用至該結點的有向路徑概率為Pmn，其中m為主動訪問n的風險結點，則對結點n而言，產(chǎn)生的風險為Riskn=Pmn×Pn×Wn。
定義6.風險引入公式：設結點n為非風險結點，該結點成功訪問風險結點m的概率為Pm，利用至結點m的有向路徑概率為Pnm，由結點n發(fā)出至結點m的有用消息權重及概率分別為Unm、pnm，由結點m發(fā)出至結點n的有害消息權重及概率分別為Hmn、pmn，則對結點n而言，引入的風險為Riskn=Pnm×Pm×（Unm×pnm+Hmn×pmn）。
定義7.風險網(wǎng)絡：借鑒張永錚等對風險網(wǎng)絡[4]定義，把一個能夠描述各結點風險分布與有向路徑的網(wǎng)絡稱為風險網(wǎng)絡。風險分布為網(wǎng)絡系統(tǒng)各個設備中結點攜帶風險的分布情況，為內(nèi)在風險；有向路徑即為各結點之間的訪問方向，為外來風險的傳出與被引入提供可能。
3.2 風險傳播模型
1.主動型風險傳播模型：也稱為主動型風險傳出，即利用風險結點已存在的風險對其直連結點進行主動訪問（包括非法攻擊或可信訪問，下同），產(chǎn)生風險擴散（即風險傳出）。如圖1（a）所示，結點A為風險源結點，存在至結點B、C、D、E的四條有向路徑，設結點A風險結點，至結點B、C、D、E的有向路徑概率為PAJ，（J=B，C，D，E），各結點自身被成功訪問的概率為PJ，（J=B，C，D，E）[8]，則結點A以概率PAJ×PJ（J=B，C，D，E）引起其出度所連結點發(fā)生風險，如圖1（b）所示。
在實際網(wǎng)絡中，路徑傳播概率可由兩結點的所有可能路徑計算得出，而結點被成功攻擊的概率則有風險傳播推廣模型計算得出。
4 最大出度算法
針對最小入度最近鄰算法[5]的不足，本文設計了一種能更好反映網(wǎng)絡風險動態(tài)特征的算法――最大出度算法，又分為針對主動型風險傳播模型的最大出度算法和針對被動型風險傳播模型的最大出度算法。
4.1 風險源結點最大出度算法
Step1：計算未被處理過的風險結點出度值numofoutdegree。
Step2：優(yōu)先選擇最大出度的結點，利用圖1所示算法將其風險值沿其出度傳播給相鄰結點，風險計算方法見定義5。
Step3：傳播風險后將該結點標記為color=red。
Step4：重復Step1、Step2、Step3，直至所有風險結點全部被標記。
4.2 零入度非風險源最大出度算法
嚴格的講，零入度的結點是不存在的，因此最小入度最近鄰算法關于零入度的概念未指明其時間范疇，在本文中，零入度的結點是指在某時間段內(nèi)不接受訪問的結點。
Step A：將網(wǎng)絡結點中所有零入度的非風險源結點標記為color=green。
Step B：計算未被處理過的零入度的非風險源的出度值numofoutdegree。
Step C：優(yōu)先選擇最大出度結點，并判斷其出度中有無風險結點，若有則選擇其出度所連結點中風險值最大的一個作為引入風險源，以概率引入風險，風險計算方法見定義6，將該結點標記為color=pink，斷開與引入風險源的有向鏈接；若無，則重新選擇結點，對該結點不進行任何處理直到再次滿足條件。
Step D：引入風險后，該結點已為風險結點，如果滿足最大出度的條件，則跳轉至最大出度算法的Step2繼續(xù)風險傳播。如果暫不滿足最大出度的條件，則跳轉至Step A順序執(zhí)行。
4.3 一般非風險源風險引入
網(wǎng)絡結點的風險在傳播最后往往會出現(xiàn)如圖3所示的情況：結點A、B、C為非風險源結點，D、E為風險結點且RiskD>RiskE，按照文[5]的理論，則其程序在圖3情況下停止運行，為了解決這一問題，引入如下算法：
Step a：計算非風險源結點的出度值numofoutdegree。
Step b：優(yōu)先選擇出度最大的結點，若其出度所連接結點中存在風險結點，則選擇風險值最大的一個結點作為風險引入源并斷開與該風險引入源的有向鏈路，該結點被標記為color=pink；若不存在，則重新選擇。
Step c：引入風險后，該結點已為風險結點，跳至Step b繼續(xù)執(zhí)行，直至又出現(xiàn)圖3情況，則跳轉至Step a繼續(xù)執(zhí)行，直至風險傳播完畢。
說明：網(wǎng)絡結點被初始化為風險結點（color=pink）和安全可信結點（color=green）后，運行風險源最大出度算法和零入度非風險源最大出度算法時，兩者發(fā)執(zhí)行，不存在先后次序，而一般非風險源風險引入只是在出現(xiàn)如圖3情況下才使用的算法，是為了防止風險傳播中忽略此類風險引入導致風險誤差較大的情況。
5 算法性能比較
5.1 風險傳播機制比較
最小入度最近鄰傳播算法[5]雖然能夠對網(wǎng)絡風險傳播給出比較精確的結論，但其在理論上有一定的缺陷，如圖4所示，假設結點1、2為風險結點，按照最小入度最近鄰傳播算法，結點1為入度最小的滿足條件的風險結點，則其以概率使結點2、4產(chǎn)生風險，同時將自己標記為已處理，如圖5（a）所示，然后結點2又滿足傳播條件，并以概率使結點3、5、6產(chǎn)生風險，并被標記為已處理，如圖5（b）所示，兩步共計感染四個結點，但其卻是在第二步才將風險傳給結點6，因而其時效性欠佳。而按照風險源最大出度算法，則優(yōu)先選擇結點2，使其攜帶的風險迅速被傳播給結點3、5、6，如圖6（a）所示，再次結點6滿足傳播條件，并將風險傳播給其出度所連的四個結點，如圖6（b）所示，兩步共計感染七個結點，多于最小入度最近鄰傳播算法的新感染結點，并且其時效性優(yōu)勢隨著網(wǎng)絡結點的復雜化而凸顯，更容易滿足動態(tài)網(wǎng)絡風險評估的要求。
此外，零入度的非風險源結點不會傳出風險[5]，因此應在風險傳播之前對其進行處理：斷開此類結點的所有出度，如圖7所示，結點9被認為不會對結點2及尤其是結點10造成風險傳播，因此可以斷開其所有出度。但本論文認為結點9雖不會對結點10造成直接的風險傳播，但是它可能會從結點2引入風險，從而使自己變?yōu)轱L險結點，進而對結點10造成風險傳播，如圖8所示。
5.2 實驗結果對比
本實驗實驗環(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ù)：總結點為200，平均度為10，風險結點不超過所有結點入度之和，結點危害性參數(shù)W=1，風險結點初始風險值為1，路徑傳播概率服從[0，0.5] 上的均勻分布。
本文參數(shù)：結點被成功訪問概率P可利用推廣模型計算，其中推廣模型的參數(shù)p=0.5，f（d）=δ（d-1），g（d*）=δ（d*-3），采用最大出度算法進行傳播。
文[5]參數(shù)：概率權p（x）=0.5，采用最小入度最近鄰算法進行傳播。
6 結 論
實驗表明：本文方法則是風險呈非線性變化，并且開始變化較快，最后變化緩慢，即在一定的精確度容許的范圍內(nèi)，對風險進行任意時刻的抽樣，本文的風險值更接近真實風險，因而動態(tài)性能更好。另外考慮的非風險源結點的風險引入，使風險值被忽略的部分被重新計算在內(nèi)，提高了風險精確度。
摘要：針對車載自組織網(wǎng)絡（VANET）的抗毀性問題，分析了其在隨意攻擊和蓄意攻擊下網(wǎng)絡的抗毀性特征。首先，提出以最大連通度、連通分支平均規(guī)模、臨界點移除比例及網(wǎng)絡效率為評價指標的VANET拓撲抗毀性參數(shù)；然后，基于帶有車輛換道功能的智能駕駛員模型，應用VanetMobisim仿真軟件建立VANET；最后，通過仿真實驗分析了網(wǎng)絡節(jié)點數(shù)、通信半徑以及攻擊模式對VANET抗毀性的影響。實驗結果表明由于車輛節(jié)點度分布的不均勻性，VANET對隨意攻擊具有較強的抗毀性，而在蓄意攻擊下顯得比較脆弱；基于節(jié)點介數(shù)的蓄意攻擊對網(wǎng)絡的破壞更快、更強。這些規(guī)律為優(yōu)化VANET拓撲控制、網(wǎng)絡協(xié)議開發(fā)和網(wǎng)絡管理提供新的指導。
關鍵詞：
車載自組織網(wǎng)絡；復雜網(wǎng)絡；抗毀性；隨意攻擊；蓄意攻擊；仿真
0引言
移動Ad Hoc網(wǎng)絡（Mobile Ad Hoc NETwork， MANET）是一種自組織無線網(wǎng)絡，由于它不需要基礎設施支持，因此網(wǎng)絡部署快速，擴展方便，使得它被廣泛應用于軍事、救災、商業(yè)等各領域。近年來，城市車輛與日俱增，移動網(wǎng)絡技術日益突破，車輛自組織網(wǎng)絡（Vehicle Ad Hoc NETwork， VANET）[1]作為一種特殊的MANET網(wǎng)絡也快速引起高度重視。在VANET中，在一定的區(qū)域內(nèi)使用無線網(wǎng)絡通信技術將車輛與車輛以及車輛與固定基礎設施連接在一起，從而一個車輛間多跳通信網(wǎng)絡在現(xiàn)有道路上被動態(tài)、快速地構建，且具有自組織、分布式控制的特點，因此，VANET在交通方面具有良好的應用前景，如信息預警、行車安全、車輛之間通信及車輛Internet訪問等。
VANET既具MANET網(wǎng)絡的特點，如拓撲結構動態(tài)變化、自組織無中心、低帶寬等，又有自己的特點，比如快速移動性、拓撲變化頻繁、間歇連通性、網(wǎng)絡規(guī)模大、充足的能量供應等[2]。在VANET中，由于車輛的高速運動，網(wǎng)絡拓撲隨之變化，對網(wǎng)絡性能造成直接影響，因此如果能夠掌握VANET拓撲結構的動態(tài)特性，可以設計高效的拓撲控制算法，優(yōu)化網(wǎng)絡連通性，使網(wǎng)絡能夠持續(xù)穩(wěn)定提供可靠的服務?？箽允窃u價網(wǎng)絡拓撲特征的主要指標之一，通過抗毀性的研究可以發(fā)現(xiàn)網(wǎng)絡中的安全隱患和薄弱環(huán)節(jié)，從而采取一系列有效的措施來提高網(wǎng)絡的抗毀性，優(yōu)化網(wǎng)絡拓撲結構，保證網(wǎng)絡的穩(wěn)定的通信能力，這對拓撲動態(tài)變化的VANET協(xié)議開發(fā)和網(wǎng)絡管理有著重要的意義。
目前，國內(nèi)外對Ad Hoc網(wǎng)絡的抗毀性研究較多。比如文獻[3]研究了網(wǎng)絡抗毀性受節(jié)點行為的影響，通過建立節(jié)點行為模型及分析三維網(wǎng)絡連通性得到了三維MANET網(wǎng)絡抗毀性的一種定量分析方法；同時仿真檢驗了它的有效性和合理性。文獻[4]引入自然連通度為抗毀性度量指標，建立了能耗的移動Ad Hoc網(wǎng)絡拓撲結構抗毀性綜合測度模型，并確定了基于網(wǎng)絡拓撲抗毀性的最優(yōu)發(fā)射半徑。Azni等[5]根據(jù)相關節(jié)點的行為建立了k相關抗毀性模型，通過仿真分析了Ad Hoc網(wǎng)絡的全局抗毀性。文獻[6]中有針對性地分別從失效成因、測度、提升策略與故障檢測和修復等4個方面對無線傳感器網(wǎng)絡抗毀性的研究進行歸納和分類，著重探討了基于網(wǎng)絡重構和拓撲演化及路由控制的無線傳感器網(wǎng)絡抗毀性優(yōu)化策略。
目前，對VANET拓撲結構的研究主要是基于復雜網(wǎng)絡理論分析其網(wǎng)絡的度分布、聚類系數(shù)、路徑長度等。文獻[7]以多Agent微觀交通仿真器（Multiagent Microscopic Traffic Simulator， MMTS）為仿真工具，研究了瑞士城市蘇黎世交通網(wǎng)絡的瞬時特性，研究結果表明網(wǎng)絡節(jié)點數(shù)服從參數(shù)冪律分布；通信半徑越大，最大集團的值越大，集團的數(shù)目越少；VANET不存在小世界特性。文獻[8]中利用4000多輛出租車收集的實時數(shù)據(jù)，分析了城市環(huán)境下車輛自組網(wǎng)的度分布、聚類系數(shù)、特征路徑長度等拓撲特性，建立了一種車輛自組網(wǎng)的網(wǎng)絡模型，通過仿真驗證了所建模型的有效性。文獻[9]以城市道路交通仿真軟件（Simulation of Urban Mobility，SUMO）為仿真工具研究了德國科隆的交通網(wǎng)絡的瞬時拓撲結構，其主要刻畫參數(shù)包括最大連通分支、度及介數(shù)中心性等，分析結果表明車載自組織網(wǎng)不具有小世界特性。文獻[10]應用Barabasi和Albert提出的BA（BarabasiAlbert）無標度網(wǎng)絡對VANET拓撲進行建模分析，認為VANET具有小世界特性。文獻[11]利用車輛全球定位系統(tǒng)（Global Positioning System， GPS）數(shù)據(jù)分析了VANET拓撲結構的動態(tài)演化特征。據(jù)研究所知，對VANET拓撲結構抗毀性的研究甚少，僅有文獻[12]對VANET的抗毀性作了初步研究，但是該文認為VANET是無標度網(wǎng)絡，然后用無標度網(wǎng)絡模型產(chǎn)生VANET，事實上，這樣生成的VANET就是一個無標度網(wǎng)絡，與現(xiàn)實環(huán)境的VANET相差太遠，幾乎沒有考慮VANET的任何特征，比如節(jié)點移動性、節(jié)點移動受到道路限制等，因此該文本質上是研究了無標度網(wǎng)絡的抗毀性，并非VANET的抗毀性。
抗毀性是VANET拓撲結構的重要特性之一，它代表網(wǎng)絡在某種極端攻擊或錯誤條件下其服務能力下降的程度。由于真實、公開的VANET的trace比較少，而且能夠獲得的一些真實trace存在一些問題，比如GPS數(shù)據(jù)不完整、時間粒度、數(shù)據(jù)精度不夠等，使得用真實VANET移動數(shù)據(jù)研究抗毀性存在一定困難，因此，本文通過VanetMobiSim車輛仿真軟件，深入分析VANET的抗毀性特征，為網(wǎng)絡拓撲結構的優(yōu)化提供指導。
1VANET抗毀性研究方法及測度
1.1抗毀性研究方法
目前，抗毀性的主要研究方法是用不同的方式對網(wǎng)絡進行攻擊，用相應的測度指標對網(wǎng)絡的抗毀性進行分析。網(wǎng)絡攻擊策略是指采取何種方式刪除網(wǎng)絡中的節(jié)點或邊，在現(xiàn)有研究中主要應用Albert等[13]Albert提出的文獻，與文獻13的作者不匹配，請作相應調(diào)整，以便保持一致；要注意論文在正文中的依次引用順序。提出的隨意攻擊（Random Attacks or Failure）和蓄意攻擊（Intentional Attacks）兩種方式。隨意攻擊通常是指隨機選擇網(wǎng)絡的一個節(jié)點或邊進行攻擊，然后再隨意攻擊其余節(jié)點中的一個節(jié)點或邊，直至將網(wǎng)絡中所有節(jié)點全部攻擊完為止。蓄意攻擊又稱為選擇性攻擊，選擇重要的節(jié)點或邊作為攻擊對象，一般用度和介數(shù)度量節(jié)點和邊的重要性。具體攻擊過程為：首先選取網(wǎng)絡中度或介數(shù)最大的節(jié)點或邊作為第一攻擊目標，攻擊完以后重新計算網(wǎng)絡各節(jié)點或邊的度量等級，依舊對度量等級最高的節(jié)點或邊進行攻擊，重復該過程，直到網(wǎng)絡中所有的節(jié)點全部被攻擊完為止。
1.2節(jié)點重要度評估方法
蓄意攻擊選擇重要節(jié)點或邊進行攻擊，評估網(wǎng)絡中節(jié)點或邊重要性的方法很多，本質都源于圖論及基于圖論的數(shù)據(jù)挖掘。本文用度和介數(shù)評估車輛節(jié)點的重要性。
定義1節(jié)點的度。在網(wǎng)絡中，節(jié)點vi的鄰邊數(shù)目ki稱為該節(jié)點vi的度。網(wǎng)絡的平均度為：
k=1N∑Ni=1ki（1）
直觀上看，一個節(jié)點的度越大，該節(jié)點越重要。
定義2節(jié)點的介數(shù)。節(jié)點vi的介數(shù)Bi就是網(wǎng)絡中所有最短路徑中經(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)絡中的作用和影響力。在VANET中，若一個節(jié)點的介數(shù)越大，則表明它在網(wǎng)絡中交換的信息流越大，可視為網(wǎng)絡中的核心節(jié)點，也意味著它更容易擁塞，成為網(wǎng)絡的瓶頸。
1.3VANET抗毀性測度
設G=（V，E）為VANET的拓撲圖，其中V={v1，v2，…，vN}是網(wǎng)絡節(jié)點的集合，E={e1，e2，…，ek}是網(wǎng)絡邊的集合，節(jié)點數(shù)定義為N=V。定義子圖Ci=G（Vi，Ei）為含節(jié)點vi連通分支，設m（G）=max1≤i≤nV（Ci）表示圖G的所有連通分支中頂點數(shù)最多的那個連通分支的節(jié)點數(shù)，則節(jié)點數(shù)最多的連通分支為最大連通分支。
定義3最大連通度S。將網(wǎng)絡中的最大連通分支中節(jié)點數(shù)與網(wǎng)絡中總的節(jié)點數(shù)的比值稱為最大連通度，即：
S=m（G）/N（3）
那么0
定義4連通分支平均規(guī)模s。當VAENT受到攻擊后，網(wǎng)絡被分割為若干連通分支，連通分支平均規(guī)模定義為去掉最大連通分支后其他連通分支的平均節(jié)點數(shù)，即：
s=（∑ni=1V（Ci）-m（G））/（n-1）（4）
顯然0
定義5臨界點移除比例fc。當網(wǎng)絡中的節(jié)點受到攻擊后，網(wǎng)絡處于崩潰邊緣時，網(wǎng)絡中被攻擊的節(jié)點數(shù)占總節(jié)點數(shù)的比例，稱為臨界點移除比例，記為fc。
網(wǎng)絡在某種攻擊模式下，百分比f的節(jié)點被移除，當f超過一定閾值，即f≥fc當在“=fc”時，屬于哪種情形，需明確。時，網(wǎng)絡分割成許多小的非連通分支；當f
設網(wǎng)絡中任意兩個節(jié)點vi與vj之間的距離dij為連接這兩個節(jié)點的最短路徑上的邊數(shù)。VANET由于車輛的高速移動、拓撲變化頻繁，使得網(wǎng)絡間歇連通，因此存在dij=∞。而且當網(wǎng)絡受到攻擊時，網(wǎng)絡的連通性也將發(fā)生改變，網(wǎng)絡被破壞到一定程度時，會產(chǎn)生孤立節(jié)點，此時會存在dij=∞，因此，文獻[13]提出用網(wǎng)絡全局效率來描述非全連通網(wǎng)絡的連通性。
定義6全局效率E。定義網(wǎng)絡全局效率為：
E=1N（N-1）∑i， j∈V，i≠j1dij（5）
顯然，網(wǎng)絡全局效率越大，網(wǎng)絡連通性越好。
2仿真實驗
2.1VANET仿真環(huán)境
本文采用VanetMobiSim[14]軟件建立VANET環(huán)境，移動模型采用帶有車道變換的智能駕駛員模型（Intelligent Driver Model with Lane Changes， IDMLC）[15]。該模型是一種微觀交通流模型，是在IDM的基礎上增加了車輛在十字路口的管理及車輛換道功能的智能移動模型，使得其更加符合真實的交通場景。仿真實驗中，網(wǎng)絡節(jié)點即為運動的車輛，可以獲取任意時刻任意車輛的位置、速度、加速度、所處車道等瞬時信息。IDMLC移動模型中車輛長度為5m，加速度a和減速度b分別為0.6m/s2和0.9m/s2，禮貌參數(shù)p為0.5，其他參數(shù)設置如表1所示。
2.2VANET抗毀性分析
下面分析在不同攻擊模式下VANET的抗毀性，為了在圖中便于區(qū)分不同攻擊模型，用符號Failure、RD和RB分別表示隨意攻擊、基于節(jié)點度的蓄意攻擊和基于節(jié)點介數(shù)的蓄意攻擊。圖1為網(wǎng)絡中車輛數(shù)為200、不同通信半徑時，VANET受到Failure、RD和RB等三種攻擊時網(wǎng)絡最大連通度的變化趨勢。由圖1可知，當通信半徑r=200m， f=0時，S=0.3630，即初始網(wǎng)絡連通性較差。在攻擊過程中當最大連通度低于0.1000時，視網(wǎng)絡基本癱瘓。在隨意攻擊下，當S為0.0911時，臨界點移除比例fc=53.42%；在RD攻擊下，當S為0.0616， fc=28.77%；在RB攻擊下，當S為0.0890時， fc=20.55%。當r=400m， f=0時，S=0.9521，初始網(wǎng)絡近乎全連通（網(wǎng)絡全連通時S=1）。在隨意攻擊下，當S為0.0747時， fc=82.19%；在RD攻擊下，當S為0.0822時， fc=57.53%；在RB攻擊下，當S為0.0959時， fc=36.99%。這一方面說明了通信半徑越大，VANET連通性越好，臨界點移除比例fc越大，抗毀性越強；另一方面，當通信半徑相同時，隨意攻擊的臨界點移除比例fc的值均大于蓄意攻擊模式的，因此VANET有較強的魯棒性，且在蓄意攻擊下，由于將重要節(jié)點移除后網(wǎng)絡迅速分割為多個連通分支，S先呈現(xiàn)迅速大幅度下降、然后緩慢下降趨勢，即VANET又具有脆弱性。這種既魯棒又脆弱的抗毀特征是VANET中車輛度分布不均勻所致。
圖2為網(wǎng)絡中車輛數(shù)為200、不同通信半徑時，VANET受到Failure、RD和RB三種攻擊時的網(wǎng)絡連通分支平均規(guī)模。由圖2可知，當通信半徑較?。ㄈ鐁=200m）時，初始網(wǎng)絡連通性較差，三種攻擊策略下連通分支平均規(guī)模s均隨移除節(jié)點比例的增加而逐漸減小。當通信半徑較大時，網(wǎng)絡初始連通性較好，則s隨去除節(jié)點比例的變化趨勢都是先變大后變小。當通信半徑r=400m時，在遭受隨意攻擊時，s在閾值f=0.8220處開始緩慢變小，在遭受蓄意（RB、RD）攻擊時，s分別在閾值f=0.4521和f=0.2055處開始變小。連通分支平均規(guī)模s之所以在閾值之前會變大，是由于隨著節(jié)點被移除，網(wǎng)絡總體連通程度變得越來越松散。在閾值之后會變小，是因為網(wǎng)絡在大量節(jié)點失效時被分割成互不連通的多個較小的分支，當節(jié)點被全部移除時，網(wǎng)絡則會消失。通過計算，在r=300m時，VANET在Failure、RD和RB三種攻擊下連通分支平均規(guī)模s的方差分別為2.0306，2.4913和9.0228，即Failure攻擊下s的波動最小，RB的波動最大，當通信半徑發(fā)生變化時，也有類似的結論。這也說明了VANET既魯棒又脆弱的特征。
圖3分別為網(wǎng)絡中車輛數(shù)為200、不同通信半徑時，VANET受到Failure、RD和RB三種攻擊時網(wǎng)絡全局效率的變化趨勢。由圖3可知，通信半徑越大，VANET效率越高；同時，隨意攻擊模式下的網(wǎng)絡效率均高于蓄意攻擊的。
另外，比較圖1～3中最大連通度、臨界點移除比例、連通分支平均規(guī)模和網(wǎng)絡效率等抗毀性測度的值，可知對于蓄意攻擊的兩種策略，RB模式的攻擊效能要強于RD模式。
下面研究車輛密度對VANET抗毀性的影響。圖4～6為r=400m時不同車輛密度的VANET采取Failure、RD和RB攻擊策略時表現(xiàn)出的抗毀性差異。從圖4～6中分析得到：在通信半徑一定時，車輛密度越大，VANET連通性越好，抗毀性越強，但是當網(wǎng)絡達到全連通時，車輛密度對VANET抗毀性影響不大，因此，在VANET拓撲控制時，可以根據(jù)實際道路、地形、路邊單元（RoadSide Unit， RSU）的配置等情況，對車輛通信半徑和車輛密度進行優(yōu)化設置，使得網(wǎng)絡能夠保持良好的連通性。
3結語
在VANET中，抗毀性對于分析整個網(wǎng)絡性能來說十分重要，尤其是在增強安全性方面的應用。本文基于IDMLC移動模型對車載自組織網(wǎng)絡的抗毀性特征作了研究，仿真結果表明，VANETs既有魯棒性又有脆弱性；通信半徑和車輛密度越大，VANETs抗毀性越好，但當網(wǎng)絡全連通時，車輛密度對抗毀性影響很小。由于蓄意攻擊（RD、RB）對網(wǎng)絡破壞性強，因此，如何在拓撲控制時優(yōu)化網(wǎng)絡通信半徑、車輛密度及路邊基礎設施配置等參數(shù)，使得網(wǎng)絡中各個車輛節(jié)點保持相對均衡地位，從而提高VANETs抗毀性，這將是后續(xù)的研究工作。另外，本文只研究了VANET的瞬時拓撲結構及其抗毀性，然而，VANET的重要特征之一是網(wǎng)絡拓撲結構的實時變化，其動態(tài)抗毀性特征也是接下來工作之一。
摘 要：隨著電網(wǎng)規(guī)模日益增大，對其進行電壓控制越發(fā)困難。為了更好的對其進行電網(wǎng)優(yōu)化控制，集中選取電網(wǎng)中的主導節(jié)點作為無功補償點成為關鍵。為此文章提出基于復雜網(wǎng)絡理論的主導節(jié)點選擇方法，并通過IEEE-39節(jié)點系統(tǒng)進行仿真校驗。
關鍵詞：電網(wǎng)；電網(wǎng)控制；主導節(jié)點，復雜網(wǎng)絡理論
前言
自從1999年Baraba和Albert發(fā)現(xiàn)了無標度網(wǎng)絡特性，揭示出復雜網(wǎng)絡結構中包含的結構特征與各種動力學特征之間的關系，突破了單純的規(guī)則網(wǎng)絡和隨機網(wǎng)絡模型的束縛后，復雜網(wǎng)絡理論的研究就上了一個新的臺階[1]。而電網(wǎng)可以抽象成一個復雜網(wǎng)絡，具有復雜網(wǎng)絡的一般特征，可運用復雜網(wǎng)絡理論來進行分析。文章引入復雜網(wǎng)絡理論中的程度中心性指標與靈敏度矩陣相結合來衡量節(jié)點在電網(wǎng)系統(tǒng)中的重要程度。
1 主導節(jié)點選擇方法
1.1 靈敏度矩陣的介紹
電網(wǎng)中的主導節(jié)點不僅要能進行電壓調(diào)控，同時也應該具有反映其節(jié)點電壓水平的能力。因此，在已有文獻中大部分都是通過構建成考慮可觀性與可控性的目標函數(shù)來進行主導節(jié)點選擇[2-3]。該矩陣是關于無功注入變化對電壓變化的靈敏度，其性質能反映電網(wǎng)間無功、電壓間聯(lián)系的疏密程度。電網(wǎng)節(jié)點i的靈敏度目標函數(shù)定義為：
式中，m，j分別為區(qū)域內(nèi)所有負荷節(jié)點的編號和無功電源節(jié)點的編號；Se為分區(qū)內(nèi)所有負荷節(jié)點合集，Sg為分區(qū)內(nèi)所有無功電源節(jié)點合集?？捎^性指標？琢im和可控性指標？茁ij均由潮流計算收斂后的雅克比矩陣求得。
1.2 程度中心性指標介紹
程度中心性指標是社團中節(jié)點在其所屬群體內(nèi)的重要程度進行判別依據(jù)之一[4]，其定義為：
式中，di（n）為電網(wǎng)第n個節(jié)點與電網(wǎng)內(nèi)其他節(jié)點關系權重和，gi為電網(wǎng)內(nèi)所有節(jié)點之間權重和。
按目標函數(shù)（1）計算出電網(wǎng)節(jié)點具有較大的靈敏度，但在實際電網(wǎng)中求出的節(jié)點可能處于電網(wǎng)區(qū)域末端位置，那么該節(jié)點就不適合作為電網(wǎng)主導節(jié)點。因此本文提出基于程度中心性指標改進目標函數(shù)，改進的目標函數(shù)表達式如下：
為了驗證基于復雜網(wǎng)絡理論中程度中心性指標的電網(wǎng)主導選擇方法的可行性，文章將利用Matlab仿真軟件對IEEE-39節(jié)點標準測試系統(tǒng)進行仿真分析。
2 算例分析
根據(jù)潮流計算收斂后的雅克比矩陣求出了？琢im矩陣和？茁ij矩陣，但這兩矩陣數(shù)量值不在同一個數(shù)量級上，因此需對其進行標準化計算。根據(jù)式（3）求出節(jié)點的目標函數(shù)值，文章只列出最大的3個節(jié)點，其值如表1所示。
由表1可以看出，所選主導節(jié)點在區(qū)域內(nèi)部大致處于中心位置，有利于對電網(wǎng)區(qū)域中末端位置的節(jié)點電壓水平進行調(diào)控，能更好的實現(xiàn)電壓無功控制。
3 結束語
文章基于復雜網(wǎng)絡理論提出了一種新的主導節(jié)點選擇方法。并在IEEE-39節(jié)點標準測試系統(tǒng)上進行了仿真驗證，所得到的主導節(jié)點綜合考慮了電網(wǎng)的地理結構與靈敏度矩陣，從而提高了主導節(jié)點選擇的準確度。
