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

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

網(wǎng)絡(luò)結(jié)構(gòu)和功能是網(wǎng)絡(luò)理論研究的核心內(nèi)容。

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

2大規(guī)模復(fù)雜網(wǎng)絡(luò)拓撲結(jié)構(gòu)分析與其他學(xué)科的關(guān)系

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

但是網(wǎng)絡(luò)拓撲結(jié)構(gòu)分析方法與傳統(tǒng)學(xué)科中的方法還是有很大不同。傳統(tǒng)的統(tǒng)計學(xué)側(cè)重于對屬性數(shù)據(jù)的分析，網(wǎng)絡(luò)結(jié)構(gòu)的分析方法則通常側(cè)重于對關(guān)系數(shù)據(jù)的分析。屬性數(shù)據(jù)是指節(jié)點或一組節(jié)點自身擁有的數(shù)據(jù)。關(guān)系數(shù)據(jù)是指節(jié)點間關(guān)系、社團(eOlllmullity)問關(guān)系、整體層次、塊層次間的關(guān)系，是2個或更多節(jié)點共同擁有的。關(guān)系數(shù)據(jù)與屬性數(shù)據(jù)是不同的分析對象，其分析方法也有很大的差異。

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

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

3互聯(lián)網(wǎng)拓撲結(jié)構(gòu)特征

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

3．1冪律的發(fā)現(xiàn)

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