1在自然界和人類社會中存在各種各樣的網絡，像作為基礎設施的鐵路、公路、航空等各種交通網、電力網，近年來廣泛應用的技術網絡萬維網(www)、對等傳輸(P2P)網絡、互聯網等。一個典型的網絡由許多節點和連接節點的邊組成，通常節點代表真實世界中的個體或組織，而它們間的關系用邊來表示。例如，在互聯網中，可以用點來表示自治系統(AS，autonomoussystem)，邊來表示其間的連接關系，即形成自治系統級的網絡拓撲；如果把互聯網中的路由器看成節點，而路由器間的連接關系看成邊，這樣就形成了路由器級的互聯網拓撲。

數學家和物理學家在研究網絡的時候，為了抓住本質，通常進行一定的抽象，表現在既不關心節點的特定物理位置、大小，也不在意邊的長短、曲直、相交與否，只關心節點和節點間是否相連。例如，歐拉在解決哥尼斯堡七橋問題的時候，雖然當時(1736年)討論長短大小的幾何學是主流，而不考慮長短大小、不牽涉量計算的情形幾乎沒人研究，但他卻撇開研究對象的長短、大小、面積、體積等度量性質和數量關系，把2座小島和河的兩岸分別抽象成4個點，而把7座橋抽象這4個點之間的連線，開創了拓撲研究的先河。當人們把網絡抽象成這種不依賴于節點的位置、大小和邊的具體形態，所得到的性質就成為網絡的拓撲性質，相應的結構稱作網絡的拓撲結構。

網絡結構和功能是網絡理論研究的核心內容。

其中網絡結構通常用網絡的統計特征(如度分布、聚集系數、平均最短路徑、度一度關聯性等)來刻畫，網絡功能由網絡上的動態變化過程來反映。這兩者并非相互獨立，而是存在必然的本質聯系。通常結構決定功能，功能反過來影響網絡結構的演化。例如，交通網中不同的結構決定了網絡的容量有很大的不同，而交通量的增加也可能引起人們增加路徑，從而影響網絡的演化。

2大規模復雜網絡拓撲結構分析與其他學科的關系

網絡拓撲結構知識需要通過拓撲結構分析獲得。當前網絡科學關心的主要對象是大規模復雜網絡，如互聯網。而網絡拓撲結構分析方法是網絡科學的核心內容。從學科角度看，這方面的研究要以傳統統計學、圖論、統計力學、隨機過程等學科為基礎。因為復雜網絡規模巨大，網絡結構又具有多樣性、動態性、復雜性，必須經過統計處理；而圖論提供了簡潔精確的方法來描述網絡，已成為研究人員的共同語言和必要工具。近年來，國內外已出版了相關的一些文章和專著。

但是網絡拓撲結構分析方法與傳統學科中的方法還是有很大不同。傳統的統計學側重于對屬性數據的分析，網絡結構的分析方法則通常側重于對關系數據的分析。屬性數據是指節點或一組節點自身擁有的數據。關系數據是指節點間關系、社團(eOlllmullity)問關系、整體層次、塊層次間的關系，是2個或更多節點共同擁有的。關系數據與屬性數據是不同的分析對象，其分析方法也有很大的差異。

經典圖論的研究對象通常只有幾個或幾十個節點，數學家們可以對其做精確的網絡優化，而復雜網絡結構分析方法處理的節點數目常常為數千、數萬、數億甚至更大規模，因此，需要從不同尺度作抽象。而過分抽象可能導致所得結論與實際情況相差甚遠，從而引發各種爭論，這就要求研究者需要根據實際情況從不同尺度來看問題。常常可以發現，一個尺度上發現的結論在另一個尺度上并不一定成立。如互聯網自治系統級拓撲的度分布滿足冪律【l，8惟1，而在互聯網路由器級拓撲中，由于路由器接口數目的限制，度分布顯然不會滿足冪律。由于不同學科的研究者看問題的尺度不同，最近就引起了激烈的爭論，計算機網絡領域的研究人員對網絡科學領域的研究結論產生異議就是一例【9J。這好比拿《庖丁解牛》中的庖丁與普通廚師的工作做比較，庖丁是在反復實踐的基礎上，掌握牛的結構(即事物的規律，現在的說法就是一個“科學問題”)，再去指導實踐(“解牛”)，而普通廚師則不必做庖丁的工作，只要把牛肉做成牛排、做成菜就可以直接滿足用戶需要了，更多的是一個“技術問題”。

也就是說，兩者是兩個層面的工作，但都是有益的工作。網絡結構分析在社會網、技術網、生物網的研究和實踐中都已發揮了重要作用，互聯網就是一個典型的例子。作為一個真實網絡，互聯網從最初的4個節點，發展成為當今世界的信息基礎設施，其應用的深入發展和無處不在的廣泛性深刻地改變了人們的工作、生活和學習方式，己成為一個名副其實的具有復雜結構的巨大系統。對互聯網拓撲結構研究所蘊含的科學意義和應用價值正受到學術界、應用部門和軍事部門的普遍重視。下面主要對互聯網拓撲結構分析的成果及其應用做比較詳細的說明。

3互聯網拓撲結構特征

千差萬別的網絡都可以通過圖來描述，鄰接矩陣和鄰接表包含了網絡的所有信息，是2種傳統的圖表示方法，但都不能直觀地告訴人們給定網絡的特征。由于網絡規模常常很大且結構復雜，為了刻畫網絡的性質，需要通過一些概念、統計的特征量和度量方法來直觀地表征一個網絡的主要結構特點。常用的刻畫一個網絡特征的指標有：節點度分布、平均路徑長度、聚集系數、度一度關聯性系數、介數、核數等。近年來，人們通過對互聯網拓撲結構的分析，發現了多項互聯網的拓撲結構特征。

3．1冪律的發現

在互聯網拓撲研究中，1999年法魯托斯(Faloutsos)等人對美國應用網絡研究國家實驗室(NLANR，nationallabforappliednetworkresearch)1997年至1998年的3份BGP(bordergatewaypro．toc01)數據以及1995年的一份traceroute眥探測數據進行分析，發現了互聯網拓撲中存在4條冪律。論文發表在SIGCOMM’99和《計算機通信評論(ComputerCommunicationReview)))…上。這個實驗結論所指的冪律是近似冪律。這一結論最重要的是在本質上揭示了節點間的差異，表明與原先占主導地位的隨機網絡【l州根本不同的是，在自治系統級拓撲中，少數節點有大度值，而多數節點的度值小。