復雜網絡論文

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

基于復雜網絡理論的計算機網絡拓撲分析

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

關鍵詞：復雜網絡；計算機網絡；網絡拓撲

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

一、復雜網絡理論簡介

復雜網絡是指具有無標度、小世界、吸引子、自相似、自組織中部分或者所有性質的網絡。復雜網絡理論的主要內容有：網絡的演化特征、演化規律、演化動力學機制、演化的統計規律以及網絡的模型特質、形成機制、幾何性質、結構穩定性等。在自然科學中，復雜網絡研究的最為基本的內容包括：度、相關性、集聚程度、最短距離、介數以及它們的分布特征。

復雜網絡系統一般有著下面幾個特征：

（1）小世界。復雜網絡通過簡單的描述對許多復雜的現實網絡進行了解釋，認為不管規模多大的網絡，其任意兩個節點都是由一條路徑連接的事實。它闡釋無論什么世界都是通過相互關系非常小的無數個節點所連接起來的。比如，在現實的社會網中，每個人的生活圈很小，人跟人認識的數目非常少，但是這個社會卻是由無數個關系所組成的，通過一條關系，可以找到跟你相距很遠的無關系的陌生人。就好像麥克盧漢所講的，地球將越來越小，是一個小的地球村，即一個小世界。

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

（3）冪律的度分布。度是指網絡中的節點及其節點關系的數量；度的相關性是指各個節點之間的聯系緊密程度；介數是指網絡中所有最短路徑經過某一節點的數量，即有一節點A，在網絡中，所有經過A的數量，它反映的是節點A的影響力。無標度網絡的特征主要集中反映了集聚的集中性?？傊?，復雜網絡的主要特征有：無標度性、小世界效應、節點度的冪律分布。

二、Internet網絡的拓撲分析

（一）Internet拓撲的特點

近些年來對于Internet拓撲的研究，最重要的成果是對于Internet拓撲節點度的冪律分布。這種分布在規模不同的網絡拓撲中表現出一定的穩定性，也就是指，在規模不同的Internet拓撲中，它們的節點度表現出一種冪律分布，即：

P（k）=k-β

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

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

（二）基于復雜網絡理論的Internet網絡拓撲模型的構建

在世人發現Internet網絡節點度具有冪律分布的規律之后，Internet網絡拓撲模型的構建產生巨大的轉變。大家更多的選擇從優先連接和生長等這一網絡拓撲規律入手進行Internet網絡的拓撲建模，其主要是為了讓符合現實Internet拓撲性質的模型通過一些簡單規則的演化讓其自動地產生出來?？衫脙炏冗B接來對新節點加入網絡的過程進行描述還比較粗糙，首先是因為新節點在加入之前，對網絡全局的信息進行了解和把握具有很大的難度，其次一個原因是單一的優先連接不能夠描述復雜的加入決策過程，而且在全網中容易形成少量的集散節點。所以要建立更加符合現實Internet拓撲特征的網絡模型則需要考慮更完善的加入規則。

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

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

三、結束語

綜上所述，復雜網絡理論最主要的特性是無標度性、小世界效應、節點度的冪律分布。Internet網絡延續著這些性質，在其拓撲結構構建和形成中表現出來，具體所形成的拓撲規則是：Internet網絡中節點的生長性和優先連接。通過其不斷的生長以及生長出的節點的優先連接，從而促使網絡拓撲是一種消息自組織和傳遞的過程。

復雜網絡論文:計算機網絡行為的復雜性理論研究

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

關鍵詞：計算機網絡；網絡行為；復雜性理論

一、引言

當今的計算機網絡異常復雜，運行時的動態變化規律成超分布、超并行、超復雜性質。計算機網絡行為研究的對象正是這種動態變化規律，具體研究對象有：拓撲結構的動態變化、傳輸性能動態演化、網絡安全、故障診斷、以及動態網絡流量等。建立或優化出具有更高性能的計算機網絡，在巨量用戶的情況下，依然能保證高質量服務。故，研究計算機網絡行為具有重要的意義。

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

二、傳統計算機網絡行為研究

傳統的計算機網絡行為分析方法的基礎理論大多為“還原論”思想，一定程度不能較全面地當今復雜計算機網絡行為研究的發展需求，其局限主要表現在以下幾個方面：

1.傳統的計算機網絡中的采樣和測量理論已不適用于現在復雜背景下的計算機網絡。

2.復雜計算機網絡中的宏觀可靠性的研究甚少。

3.復雜計算機網絡中的安全行和宏觀安全監控理論缺乏。

4.傳統的陣列新能評估理論不能處理長程相關條件下的性能評估。

5.復雜計算機網絡拓撲圖狀態分析理論甚少。

6.復雜計算機網絡中時常發生異常大流量，對這種顯現的研究和處理理論甚少，而傳統的Poisson和Markov理論不能準確刻畫，故，需要新的數學理論對其進行研究。

7.研究復雜計算機網絡中的流量實時測量和監控理論較少。

然而，現今的計算機網絡發展迅猛，已經深入人們生活的各個領域，故，探索新的方法，來研究復雜計算機網絡行的方法，以提高網絡服務質量，因此其具有重要的理論意義和實用價值。

三、復雜性理論

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

將復雜性理論應用于現今的復雜計算機網絡行為研究之中，可從計算機網絡系統的宏觀上研究和分析其網絡行為特性，該領域的研究能突破傳統算法的一些局限，更好地建設出和優化現今的計算機網絡結構，保證服務質量。

復雜性理論主要包括：混沌學、分形學、自組織學、以及復雜網絡學等，是一種新型的交叉科學：

1.混沌是非線性系統中，貌似隨機運動的復雜現象，各個科學領域，包括計算機網絡中，存在大量的混沌現象，其主要特征包括有界性、遍歷性、不可預測性、分為性、普適性等。

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

3.自組織是一種系統的自我調節的過程，為整個系統自我生存、尋求適應性、創造性的行為。各種內在因素相互影響，使復雜系統能夠自動地變換成“自組織臨界狀態”，此時，系統的時空動力學行為不再具有特征時間和特征空間尺度，而是時空關聯（滿足冪定律分布），如果越過該臨界狀態，系統會產生復雜的相變現象。

復雜計算機網絡行為的復雜性是宏觀的，包括行為復雜、功能復雜、結構復雜等各個方面。而復雜性理論的自組織性、臨界性、自相似性、非線性等鮮明特征正好符合研究復雜計算機網絡行為的各種特征。

四、計算機網絡行為的復雜性理論發展

由于復雜性理論的特性適用于研究復雜計算機網絡行為，故國內外很多學者對將復雜性理論應用于網絡行為研究感興趣，并取得了一些成果。

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

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

在將混沌學引入到計算機網絡行為研究中的方面，研究發現計算機網絡中普遍存在一種貌似隨機的現象，其具有混沌的各種特性。為引導這種混沌現象向好的方面發展，學者陳關榮等人在詳細分析了計算機網絡流量控制系統中的混沌現象之后，將將混沌控制方法引入到網絡流量控制當中，另外，國內外一些學者探索試將混沌最大Lyapunov指數、以及相空間重構技術引入到計算機網絡流量行為研究和分析領域，獲得了一些成果。

五、展望

將復雜性理論引入計算機網絡行為研究，雖然取得了豐碩的成果，但也存在一些尚待解決的問題。現今的計算機網絡越來越復雜、有其符合復雜性理論的特性，且復雜性理論的研究比較成熟。

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

六、結論

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

復雜網絡論文:復雜網絡研究

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

關鍵詞：復雜網絡；隨機網絡；小世界網絡；無標度網絡

1 復雜網絡研究概況

近年來，國內外掀起了研究復雜網絡的熱潮。復雜網絡之所以復雜，不僅在于網絡規模的巨大，網絡結構的復雜，而且網絡在時間、空間上都具有動態復雜，網絡行為也很復雜。

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

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

2 復雜網絡主要特征度量

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

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

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

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

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

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

2.3 度分布(Degree Distribution)

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

3 復雜網絡模型

3.1 隨機網絡模型

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

隨機網絡的基本特性可以歸納如下:

1) 隨機網絡的平均度為：

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

網絡的平均最短距離隨網絡規模的增加呈對數增長。

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

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

3.2 小世界網絡模型

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

1) 開始于規則圖形。初始有數目固定的N個節點，每個節點有k個臨近節點，構成一個規則的一維圓環。

2) 隨機化。以概率p對圓環中的每一條邊重新連接。這個過程中要求不能自身連接和重復連接。例如圖1[5]所示，p=0對應于規則圖，p=1對應于隨機圖；當前研究的熱點是p在0到1之間的WS網絡的性質。

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

WS網絡的主要性質為：

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

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

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

3.3 無標度網絡模型

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

無標度網絡最顯著特征是度分布屬于冪分布。其表現出的特性是：大多數的節點只與一兩個少數節點相連接，但有少數節點卻被大量的連接。無標度模型一般用來分析網絡的動態特性，揭示大型復雜網絡的拓撲結構。

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

BA模型是第一個增長的網絡模型，其算法如下：

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

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

圖2 BA模型的演化過程

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

b) 平均路徑長度。BA無標度網絡的平均路徑長度為，這表明該網絡也具有小世界特性。

c) 聚類系數。BA無標度網絡的聚類系數和網絡大小有關，近似成一種冪率分布。

4 小結與展望

綜上所述，以前，用規則網絡和隨機網絡理論來描述真實系統的拓撲結構，這只反映了眾多系統的兩種極端情況，不能很好地描述多數現實系統。近幾年來，以小世界網絡與無標度網絡為核心的復雜網絡領域的最新成果反映了大多數復雜系統的基本特性，使得對復雜系統建模的研究取得了實質性的突破。復雜網絡的模型研究雖然己取得很大進展，但仍然存在一些問題。

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

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

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

復雜網絡論文:利用MEX文件實現復雜網絡分形維數計算

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

關鍵詞:復雜網絡;分形維數;C-MEX

隨著20世紀末Watts-Strogatz的小世界網絡模型和Barabasi-Albert的無尺度網絡模型的提出,復雜網絡的研究取得快速的發展。經過十幾年的蓬勃發展,復雜網絡已成為最近幾年流行的新興學科之一,已不同程度的應用于工程技術、經濟、醫藥、生物等領域。

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

1 復雜網絡分形維數探討

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

NB≈lB-dB (1)

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

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

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

1) 給網絡中的所有節點分配一個唯一的從1到N的數,每個節點并沒有著色

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

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

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

(2) 將lB設為1

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

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

(5) i=i+1

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

2 利用CMEX文件計算復雜網絡分形維數

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

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

MEX文件又稱為外部程序調用接口,在進行大規模的數據處理,比如影響 MATLAB執行速度的循環體時,可以編寫相應的C或C ++子程序完成相同的功能,并編譯成 MEX文件,再由MATLAB調用此MEX文件以提高運行速度。

C-MEX是通過MATLAB的編譯器轉換為可執行文件,是按照MEX技術要求的格式編寫相應的程序,通過編譯連接,生成擴展名為.dll的動態鏈接庫文件,可以在MATLAB環境下以函數的形式直接調用。一般來說,C-MEX 文件的執行速度是相同功能的M文件執行速率的20~40倍。

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

針對于盒子覆蓋法中的貪婪著色算法,我們也利用MEX文件編程實現了此算法來對復雜網絡分形維數進行計算。具體利用C―MEX計算復雜網絡分形維數的過程如下:

(1) 我們先根據貪婪著色算法描述,用matlab的M文件實現

(2) 找出M文件中循環次數較多的代碼段

(3) 將這些循環次數較多的代碼段轉化成相應的C-MEX程序,并編譯成相應的.dll文件

(4) 將M文件中循環次數較多的代碼段用相應的.dll代替

(5) 最后對修改后的程序編譯執行

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

從表1的結果,我們可以看到使用C-MEX混合編程后,實現復雜網絡分形維數計算算法的執行時間得到了很大程度的提高。這也證明了我們所采用的方法是行之有效的。

3 結論

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

復雜網絡論文:基因表達譜的復雜網絡研究

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

關鍵詞：基因芯片；基因表達譜；社區結構；分類信息指數；最小生成樹；閾值；復雜網絡

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

復雜網絡理論是近年來發展起來的一個重要的交叉。對于一個復雜的系統，很多時候我們不能夠單獨通過分析系統內元組來反應系統性質。復雜系統是由微觀層次上的海量個體所組成，個體之間存在著作用。把個體抽象為網絡節點，而個體之間的相互作用抽象為節點之間的邊，則復雜系統就可以用一個復雜網絡來描述。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

復雜網絡的結構是不均勻的，往往存在很多連接致密的集團，在這些集團之間只有很少邊形成的松散的連接。這些致密的結構往往與功能有著密切的關系，因此受到普遍的關注。當前普遍采用的劃分社區的方法是Newman-Girvan算法。

社區劃分反映基因間的功能關系，而在網絡模塊中，可以發現網絡發生了明顯的改變。首先我們畫出正常樣本網絡，用Newman-Girvan的劃分算法對得到的網絡進行分塊。當把正常樣本網分成14個社區時，得到的聚類系數最大，為Q=0.596（如表2），這樣就把網絡分成了14個大的功能模塊。如圖3所示，即為正常樣本網絡的社區結構（每種顏色代表一個社區）。可以看出，各個社區結構中的節點數目分布并不均勻，并且存在很多孤立節點。社區內節點間的連接比較緊密，而不同社區間的連接比較稀疏。

同樣用Newman-Girvan的劃分算法，我們畫出腫瘤樣本的網絡，把腫瘤樣本網分成了13社區（如圖4）。此時得到的聚類系數最大，為Q=0.630（如表3）。可以看出，腫瘤樣本網絡的各個社區結構中的節點數目分布也是并不均勻，并且同樣存在很多孤立節點。社區內節點間的連接比較緊密，而不同社區間的連接比較稀少。

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

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

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

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

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

表6

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

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

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

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

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

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

復雜網絡論文:復雜金融網絡的自相似性研究

摘要：以股票為節點，選取適當閾值量化股票收益率序列間相關關系從而構建復雜金融網絡。基于復雜網絡的理論，討論金融網絡的度分布、平均最短路徑和聚集系數，發現面向金融時間序列的股票網絡具有小世界效應，無標度特性和一個很重要的特性―自相似性。該文用兩種方法分析了網絡的自相似性：一是提出用網絡節點的度構造Hurst指數，定量分析金融網絡的自相似性；二是金融網絡的平均路徑長度和聚集系數定性地分析了復雜網絡的自相似性。

關鍵詞：金融市場；復雜網絡；無標度；自相似

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

復雜網絡的自相似性是指網絡局部和整體在某些特征上相似。對于固定網絡自相似性的研究一般是利用節點內部互動性來探測網絡的演化過程。自相似系數的測量方法是由 C.M.Song與S.Havlin[4]提出利用重構化測量，以及R.Guimera,L.Danon[5]提出利用郵件系統測量社區結構的相似性，他們也用這些方法描述了一些現實網絡的自相似性[4]。

1 復雜金融網絡建模

1.1 數據來源

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

1.2 復雜金融網絡建模

以滬深A股為節點，股票相互影響關系為連邊構建無權無向網絡。設股票i在第t時刻的平均價為xi(t)，xi(t)為股票i在t時刻開盤價，收盤價，最高價和最低價的平均值。

為股票i對數收益率。定義股票i和股票j的相關系數為：

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

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

1.3 復雜金融網絡的拓撲結構特征

1.3.1 節點度分布

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

1.3.2 平均最短路徑長度

若一個包含n個節點的無向網絡，，其中dij為節點i和節點j的最短距離，也是節點i,j最短路徑所經過的邊數。考慮到每個節點到期自身的距離為0，無關聯節點的距離為無窮大，此時存在問題，所以對進行修改，得到“調和平均”最短路徑長度。在股票網絡中，平均最短路徑長度是任意兩只股票相關中介數量的平均值，反映網絡的大小和分離程度。

1.3.3 聚集系數

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

2 復雜金融網絡的自相似性研究

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

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

2.1 基于R/S分析的金融網絡自相似性分析

設網絡為動態增長的，網絡節點不斷地增長記為n1,n2,…ni，計算節點在ni時度分布的累積極差R(k)和標準差S(k)。

設x(k)為網絡節點是ni時各節點的度數，的均值，也為網絡的平均度數。

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

標準差S(k)：，則關系式為，

R/S為重標極差，H為Hurst指數，所以

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

復雜網絡自相似性與Hurst指數的關系[6]

若0≤H

若H=0.5， 說明復雜網絡節點是互相獨立的，度分布是隨機的。

若0.5

2.2 基于容量維數的自相似性分析

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

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

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

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

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

本文計算平均最短路徑長度和聚集系數的D來分析復雜金融網絡自相似性

3 實證分析

由于本文是分析動態復雜網絡的自相似性，所以用不同數量的股票來構造網絡。

1） 分別用200，250，300，350，400，450，500不等數量的股票構造金融網絡，然后基于R/S分析用各網絡節點度分布來求Hurst指數，在matlab編程基礎上得到H=0.823，可知復雜金融網絡具有自相似性。取閾值為0.85，構建股票網絡并計算各網絡的平均最短路徑長度和聚集系數。

實證研究發現在網絡平均度數緩慢增長時，網絡平均路徑長度和聚集系數呈現相似的變化趨勢，這也是網絡拓撲特性自相似性表現。

2） 選用200,250,300,350,400,450,500只股票分別構造金融網絡，用比較分析法分析金融網絡的自相似性。

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

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

在閾值為0.85時各股票網絡都表現出很好的無標度特性（如表1所示）：(最小二乘法)。

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

以500只股票構造的網絡為整個復雜網絡，300只和400只都為局部小網絡，得到容量相似維數。

從表2中可以看出Dl,Dc都比較相近，所以得動態的網絡也具有自相似性。

4 結束語

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

復雜網絡論文:復雜網絡下的綜合視頻會議服務

面對越來越復雜的網絡環境及應用,今天的企業用戶需要的已經不僅僅是一個傳統意義上的產品或者系統,他們需要自己的IT應用發揮更大的價值,實現與客戶之間的交互、員工生產力的優化以及企業資源的整合等,并通過這些方面的整合提升企業的運營效率。視頻會議作為提高溝通效率的有效方式,滿足了人們全方位的交流需求,因而在近年來取得了飛速的發展。

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

全面靈活的解決方案

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

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

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

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

覆蓋全球的運營網絡

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

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

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

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

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

復雜網絡論文:基于復雜網絡的風險傳播模型及有效算法

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

關鍵詞：復雜網絡；推廣模型；風險傳播

1 引 言

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

本文在針對網絡風險傳播問題，結合復雜網絡中傳播蔓延現象的推廣模型 [11，12]，提出了一種網絡風險傳播模型及相關定義，并改進了風險傳播算法。

2 推廣模型下的風險傳播

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

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

在本文中，暫不考慮網絡風險移除狀態，即僅考慮風險在整個網絡中如何轉移，而未考慮網絡風險傳播后所造成情況的如何消除。因此上述推廣模型應用于風險傳播如下：

計算技術與自動化2016年6月

第35卷第2期呂元海等：基于復雜網絡的風險傳播模型及有效算法

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

3 風險傳播模型

3.1 相關定義

定義1.結點：指網絡系統中任意一臺網絡設備上任意可能被利用的最小單元。其中已經被利用的稱為風險結點，而尚未被利用的稱為非風險結點。

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

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

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

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

定義5.風險傳出公式：設結點n被成功利用的概率為Pn，被利用后對網絡系統的危害程度為Wn，利用至該結點的有向路徑概率為Pmn，其中m為主動訪問n的風險結點，則對結點n而言，產生的風險為Riskn=Pmn×Pn×Wn。

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

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

3.2 風險傳播模型

1.主動型風險傳播模型：也稱為主動型風險傳出，即利用風險結點已存在的風險對其直連結點進行主動訪問（包括非法攻擊或可信訪問，下同），產生風險擴散（即風險傳出）。如圖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）引起其出度所連結點發生風險，如圖1（b）所示。

在實際網絡中，路徑傳播概率可由兩結點的所有可能路徑計算得出，而結點被成功攻擊的概率則有風險傳播推廣模型計算得出。

4 最大出度算法

針對最小入度最近鄰算法[5]的不足，本文設計了一種能更好反映網絡風險動態特征的算法――最大出度算法，又分為針對主動型風險傳播模型的最大出度算法和針對被動型風險傳播模型的最大出度算法。

4.1 風險源結點最大出度算法

Step1：計算未被處理過的風險結點出度值numofoutdegree。

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

Step3：傳播風險后將該結點標記為color=red。

Step4：重復Step1、Step2、Step3，直至所有風險結點全部被標記。

4.2 零入度非風險源最大出度算法

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

Step A：將網絡結點中所有零入度的非風險源結點標記為color=green。

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

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

Step D：引入風險后，該結點已為風險結點，如果滿足最大出度的條件，則跳轉至最大出度算法的Step2繼續風險傳播。如果暫不滿足最大出度的條件，則跳轉至Step A順序執行。

4.3 一般非風險源風險引入

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

Step a：計算非風險源結點的出度值numofoutdegree。

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

Step c：引入風險后，該結點已為風險結點，跳至Step b繼續執行，直至又出現圖3情況，則跳轉至Step a繼續執行，直至風險傳播完畢。

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

5 算法性能比較

5.1 風險傳播機制比較

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

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

5.2 實驗結果對比

本實驗實驗環境為Microsoft Windows XP Professional，Intel（R） Pentium（R） CPU 1.8GHz，512M RAM。仿真工具為NetLogo 4.0.4、Matlab 7.0.0.19920（R14）。

共同參數：總結點為200，平均度為10，風險結點不超過所有結點入度之和，結點危害性參數W=1，風險結點初始風險值為1，路徑傳播概率服從[0，0.5] 上的均勻分布。

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

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

6 結 論

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

復雜網絡論文:基于復雜網絡的車載自組織網絡抗毀性分析

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

關鍵詞：

車載自組織網絡；復雜網絡；抗毀性；隨意攻擊；蓄意攻擊；仿真

0引言

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

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

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

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

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

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

1.1抗毀性研究方法

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

1.2節點重要度評估方法

蓄意攻擊選擇重要節點或邊進行攻擊，評估網絡中節點或邊重要性的方法很多，本質都源于圖論及基于圖論的數據挖掘。本文用度和介數評估車輛節點的重要性。

定義1節點的度。在網絡中，節點vi的鄰邊數目ki稱為該節點vi的度。網絡的平均度為：

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

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

定義2節點的介數。節點vi的介數Bi就是網絡中所有最短路徑中經過該節點的數量比例之和，即：

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

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

1.3VANET抗毀性測度

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

定義3最大連通度S。將網絡中的最大連通分支中節點數與網絡中總的節點數的比值稱為最大連通度，即：

S=m（G）/N（3）

那么0

定義4連通分支平均規模s。當VAENT受到攻擊后，網絡被分割為若干連通分支，連通分支平均規模定義為去掉最大連通分支后其他連通分支的平均節點數，即：

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

顯然0

定義5臨界點移除比例fc。當網絡中的節點受到攻擊后，網絡處于崩潰邊緣時，網絡中被攻擊的節點數占總節點數的比例，稱為臨界點移除比例，記為fc。

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

設網絡中任意兩個節點vi與vj之間的距離dij為連接這兩個節點的最短路徑上的邊數。VANET由于車輛的高速移動、拓撲變化頻繁，使得網絡間歇連通，因此存在dij=∞。而且當網絡受到攻擊時，網絡的連通性也將發生改變，網絡被破壞到一定程度時，會產生孤立節點，此時會存在dij=∞，因此，文獻[13]提出用網絡全局效率來描述非全連通網絡的連通性。

定義6全局效率E。定義網絡全局效率為：

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

顯然，網絡全局效率越大，網絡連通性越好。

2仿真實驗

2.1VANET仿真環境

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

2.2VANET抗毀性分析

下面分析在不同攻擊模式下VANET的抗毀性，為了在圖中便于區分不同攻擊模型，用符號Failure、RD和RB分別表示隨意攻擊、基于節點度的蓄意攻擊和基于節點介數的蓄意攻擊。圖1為網絡中車輛數為200、不同通信半徑時，VANET受到Failure、RD和RB等三種攻擊時網絡最大連通度的變化趨勢。由圖1可知，當通信半徑r=200m， f=0時，S=0.3630，即初始網絡連通性較差。在攻擊過程中當最大連通度低于0.1000時，視網絡基本癱瘓。在隨意攻擊下，當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，初始網絡近乎全連通（網絡全連通時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有較強的魯棒性，且在蓄意攻擊下，由于將重要節點移除后網絡迅速分割為多個連通分支，S先呈現迅速大幅度下降、然后緩慢下降趨勢，即VANET又具有脆弱性。這種既魯棒又脆弱的抗毀特征是VANET中車輛度分布不均勻所致。

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

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

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

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

3結語

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

復雜網絡論文:基于復雜網絡理論的電網主導節點選擇

摘 要：隨著電網規模日益增大，對其進行電壓控制越發困難。為了更好的對其進行電網優化控制，集中選取電網中的主導節點作為無功補償點成為關鍵。為此文章提出基于復雜網絡理論的主導節點選擇方法，并通過IEEE-39節點系統進行仿真校驗。

關鍵詞：電網；電網控制；主導節點，復雜網絡理論

前言

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

1 主導節點選擇方法

1.1 靈敏度矩陣的介紹

電網中的主導節點不僅要能進行電壓調控，同時也應該具有反映其節點電壓水平的能力。因此，在已有文獻中大部分都是通過構建成考慮可觀性與可控性的目標函數來進行主導節點選擇[2-3]。該矩陣是關于無功注入變化對電壓變化的靈敏度，其性質能反映電網間無功、電壓間聯系的疏密程度。電網節點i的靈敏度目標函數定義為：

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

1.2 程度中心性指標介紹

程度中心性指標是社團中節點在其所屬群體內的重要程度進行判別依據之一[4]，其定義為：

式中，di（n）為電網第n個節點與電網內其他節點關系權重和，gi為電網內所有節點之間權重和。

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

為了驗證基于復雜網絡理論中程度中心性指標的電網主導選擇方法的可行性，文章將利用Matlab仿真軟件對IEEE-39節點標準測試系統進行仿真分析。

2 算例分析

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

由表1可以看出，所選主導節點在區域內部大致處于中心位置，有利于對電網區域中末端位置的節點電壓水平進行調控，能更好的實現電壓無功控制。

3 結束語

文章基于復雜網絡理論提出了一種新的主導節點選擇方法。并在IEEE-39節點標準測試系統上進行了仿真驗證，所得到的主導節點綜合考慮了電網的地理結構與靈敏度矩陣，從而提高了主導節點選擇的準確度。