- 相關推薦
基于復雜網絡理論的計算機網絡拓撲研究
摘 要：復雜網絡理論近年來發展迅速。介紹了復雜網絡理論的相關知識，基于此對計算機網絡拓撲進行了探究，闡述其特性并對其未來發展趨勢進行了展望。
關鍵詞：復雜網絡理論;計算機網絡;網絡拓撲
0、引言
近年來，關于復雜網絡的文章不斷在各大國際一流刊物上發表，內容涉及復雜網絡理論、復雜網絡模型以及復雜網絡理論在各學科中的應用等等。出現以上情況，肇因于復雜網絡理論面對一些情況表現出的普適性，這也使復雜網絡理論成為國際學術界新的研究熱點。計算機網絡技術作為同樣迅猛發展的學科，也是學術界一直以來關注的熱點，巧合的是用復雜網絡理論知識可以非常簡化且準確地通過拓撲的形式闡釋計算機網絡。我們將單個的計算機看作一個獨立的節點，將連接各個計算機網絡的介質看作路徑，那么計算機網絡就可以簡化描述為一個以復雜網絡理論為基礎的拓撲圖�；谝陨辖Y論，本文將對復雜網絡理論下的計算機網絡拓撲進行研究。
1、復雜網絡理論概述
著名科學家錢學森給出了復雜網絡的定義：具有自組織、內部相似、吸引引子、小區域、無標度中一部分或者是全部的網絡稱為復雜網絡。
1.1 復雜網絡-陛質
(1)平均路徑長度。平均路徑長度指所有節點之間距離的平均值，能夠形象解釋這一概念的是著名的“小世界”試驗，實驗要求參與者把一封信傳給他們熟悉的人之一，藉此探明數人網絡中路徑長度的分布，結果表明平均穿過人數僅為6人，這一試驗也正是流行的“六度分離”概念的起源。
(2)聚集系數。聚集系數C用來描述網絡中節點的聚集情況，同樣以人類社交為例，即在社會網絡中，與你保持朋友關系的幾個人也有可能彼此是朋友，通過大量的實驗，結果表明大部分真實網絡中的節點是相對聚集的。
(3)度分布。度分布用來描述網絡中邊的數目相同的節點在整個網絡節點中的比值，即在社交網絡中有指定數目的朋友個數占總人數的比值。除了以上3個性質外，復雜網絡還有網絡彈性、介數、度和聚集系數相關性等性質，在未來對于復雜網絡和應用學科的結合中都將起到指導作用。
1.2 復雜網絡特征
(1)小世界效應。前文中提到由復雜網絡的平均路徑長度概念引入的著名試驗闡釋了“小世界”的內涵，這一內涵之于現實網絡的意義在于揭示了復雜網絡無論規模大小，都是由N個微小節點連接的，看似毫無關聯的幾個小節點網絡通過非常短的路徑就可以產生聯系，相互關聯，而這種關聯的建立也是大規模復雜網絡構建的基礎。
(2)集群性。集群性是指在一個大規模復雜網絡中存在的一種內聚傾向。仍然以社會網絡為例，甲在當地的一個茶道社A，乙是甲的好友，而乙同樣也是另一個茶道社B的社員，那么隨著甲和乙溝通交往的深入，最后很有可能使得茶道社A與茶道社B之間產生更多更緊密的聯系，而這樣的聯系所引發的后續影響就是世界在逐步縮小，個體間的關系越來越緊密。
(3)冪律分布。在一個復雜網絡里，冪律的度值趨于服從泊松定律，即滿足公式P(k)一k—r，而冪律分布統計參數r與網絡的大小無關，我們將這樣的網絡稱為無標度網絡，該網絡的無標度性體現在無論測量的單位變大或是變小，所研究的客體性質如形態、復雜程度和統計特征均不發生變化。
1.3 復雜網絡模型
網絡模型的基礎是規則網絡模型，規則網絡模型的特點是每個節點的邊數都相同，而這樣的網絡模型過于理想化，在真實網絡中出現這樣的規則網絡概率小而又小，岡此在20世紀50年代末又有人提出了全隨機網絡模型，這種模型更加符合真實網絡的實際情況，基于這樣的模型，又有一些其它網絡模型被相繼提出。
(1)小世界網絡(smal—world networks)。大量的實驗結果表明，真實網絡表現出的特點不像規則網絡和隨機網絡那樣分為幾段而是更趨于兩者之間，它在具有較短平均路徑的同時也有較高的聚集性。因此Watts和Strongatz在l998年提出了一種介于規則模型和全隨機模型之間的新模型—— 小世界網絡(簡稱WS網絡)，模型的構造如圖1所示。
(2)無標度網絡(Scale—free net works)。提到無標度網絡就不得不提到著名的BA模型(由Barabasi和Albert提出故命名為BA模型)。BA模型認為以前的模型沒有考慮到網絡是開放的，不斷會有新的節點加人，也沒有考慮到新節點會自動擇優選擇度數大的節點進行連接。BA模型在考慮到以上因素后，經過大量的實驗和計算，得出BA 網絡度的分布逐漸穩定在指數為3的冪律分布，這一結論也恰好能夠與真實網絡的大量實驗結論相吻合。BA模型的貢獻還在于它催生出很多以這一模型為基礎的新研究，比如李翔和陳關榮提出的局域世界演化模型、權重演化網絡模型等等，這標志著人們對網絡世界的認識更加主動而深入了。
2、復雜網絡理論在計算機網絡拓撲中的應用
計算機網絡技術面臨著前所未有的復雜情況，在這個世界上幾乎每秒鐘都有新的用戶加入計算機網絡，幾乎每秒鐘都有新的技術或協議融人計算機網絡。因此，計算機網絡技術不同于其它復雜網絡學科，它的快速變化決定其與眾不同�；诖颂攸c，復雜網絡理論與計算機網路相結合將催生新的、更符合實際網絡情況的新模型以用于研究計算機網絡拓撲。
2.1 計算機網絡動力學模型
計算機網絡的復雜性很大程度上是從其動力學的復雜性表現的，具體來說就是網絡既具備抗變換性同時也具有脆弱性，所謂抗變換性就是魯棒性，它是指控制系統在一定(結構、大小)的參數攝動下，維持其它某些性能特性，即在異常和危險情況下系統的生存，比如計算機在輸人錯誤、磁盤故障、網絡過載或惡意攻擊下還能夠保證不死機、不崩潰。而計算機網絡在具備抗變換性的同時還具有脆弱性。在整個計算機網絡中有一些關鍵節點，一旦它們中的部分失效— — 即使是它們中的一小部分失效，都很有可能導致計算機網絡崩潰。計算機網絡的特性決定了復雜網絡理論的幾個經典模型并不適用，于是美國加州大學的學者近年來根據計算機網絡特點提出了HOT 模型。HOT系統可采用沙堆模型進行模擬，但這里的沙堆必須加入人工設計因素，即存在優化目標和人為調整因素。通過實驗可以看出HOT模型已經能夠初步解釋計算機網絡的人工設計，但是這種解釋仍然是初步的，對于計算機網絡中的很多特性HOT模型仍然無法做到完全涵蓋，但是相對于之前以復雜網絡特性為基礎研究的情況，這不能不說是該研究的重要進步。
2.2 計算機網絡病毒防治
復雜網絡理論能夠較好地應用于人類的病毒傳播學當中，同樣，在計算機網絡病毒防治領域也能夠發揮其作用。
拓撲結構決定網絡的特性，這句話不僅強調了網絡拓撲結構的重要性，同時也為人們認識和防治計算機網絡病毒傳播提供了重要啟示。在研究中發現，由于規則網絡自身的拓撲結構特點決定了它不利于計算機病毒的傳播，相比之下，小世界網絡更容易傳播病毒，無標度網絡只要小部分節點感染就能導致大范圍的病毒傳播，巧合的是計算機網絡不僅具有小世界的特征，同樣也有無標度性，因此計算機網絡病毒的傳播防治一直是一項具有挑戰性的工作。
復雜網絡理論無論在動力學建模還是在病毒防治方面都有重要意義，未來與計算機網絡拓撲相結合的復雜網絡理論研究必將成為該學科的研究重點和熱點。
3、計算機網絡拓撲研究展望
基于復雜網絡理論的計算機網絡拓撲研究，從新的視角審視計算機網絡技術，從拓撲結構的高度關注一些具有復雜網絡性質的事件，通過對這些事件不同視角的解讀進行研究。
3.1 理論角度
完善應用于計算機網絡的復雜網絡理論，盡快構造符合要求的網絡拓撲模型，基于更優的模型對計算機網絡結構的統計學特性進行再研究。只有向著這個方向努力，才能夠更好地面對快速發展的技術帶來的“副作用”，在問題發生時不是采取“治標不治本”的補救措施，而是從結構人手，將問題從根源上解決。與此同時，面對不斷發展的網絡環境，我們應當總結出一整套較為完善的模型評價機制，使模型評價的維度更全面，對于新問題的響應更迅速。
3.2 應用角度
根據復雜網絡的統計特性，應當更深入地研究計算機的網絡拓撲結構、資源管理與配置，在應用層面上構建性能良好、安全性高、便于管理的服務程序，推出具有小世界性或無標度性的P2P網絡甚至是web網絡。
3.3 同步控制
計算機網絡的同步性一直是計算機網絡穩定的大敵，同步發生將導致網絡擁堵甚至崩潰。因此，從復雜理論的角度分析計算機網絡拓撲，從結構暑面解決有害同步將是未來研究的重點之一。
3.4 病毒防治
要明確計算機網絡病毒傳播的方式，了解原網絡拓撲結構的特性，找出針對特定病毒傳播方式的特定結構缺陷，最大程度保障計算機網絡安全。
4、結語
計算機網絡以其龐大的規模和復雜多變的動態結構向專業研究人員提出了挑戰，復雜網絡理論無疑為該研究洞開了一扇大門，以復雜網絡理論的研究方式分析計算機網絡問題，不僅為研究提供了新方向、新方法，為計算機網絡研究重大突破提供了理論準備，同時也為計算機網絡應用和管理帶來了更合理的規劃和管理措施。
參考文獻：
[1] 陳炳坤，姚爽林.復雜網絡理論的計算機網絡拓撲研究[M].上海：同濟大學出版社，2009.
[2] GUAREJ.Six degrees of separation：aplay[g].NewYork：Vintage，199O.
[3] WATTS D J，STROGATZ S H.Collective dynamics of”small—world”networks[J].Nature.1998.393(6).
[4] 劉磊.基于復雜網絡理論的計算機網絡拓撲研究[J].計算機光盤軟件與應用，2009(3).
【基于復雜網絡理論的計算機網絡拓撲研究】相關文章：
基于ＳＮＭＰ的拓撲發現的研究10-09
基于復雜網絡的證券投資行為擴散研究08-07
基于復雜性科學的企業分形治理研究07-15
基于計算機網絡的監控系統應用研究06-27
復雜網絡理論在城市交通網絡分析中的應用10-22
大規模IP網絡中基于SNMP的網絡拓撲發現方法分析05-22
基于內容的圖像檢索研究07-08
基于ＡＨＰ的企業外包研究10-10