前言：尋找寫作靈感？中文期刊網(wǎng)用心挑選的互聯(lián)網(wǎng)拓?fù)浞治霭l(fā)展，希望能為您的閱讀和創(chuàng)作帶來靈感，歡迎大家閱讀并分享。
1在自然界和人類社會(huì)中存在各種各樣的網(wǎng)絡(luò)，像作為基礎(chǔ)設(shè)施的鐵路、公路、航空等各種交通網(wǎng)、電力網(wǎng)，近年來廣泛應(yīng)用的技術(shù)網(wǎng)絡(luò)萬維網(wǎng)(www)、對(duì)等傳輸(P2P)網(wǎng)絡(luò)、互聯(lián)網(wǎng)等。一個(gè)典型的網(wǎng)絡(luò)由許多節(jié)點(diǎn)和連接節(jié)點(diǎn)的邊組成，通常節(jié)點(diǎn)代表真實(shí)世界中的個(gè)體或組織，而它們間的關(guān)系用邊來表示。例如，在互聯(lián)網(wǎng)中，可以用點(diǎn)來表示自治系統(tǒng)(AS，autonomoussystem)，邊來表示其間的連接關(guān)系，即形成自治系統(tǒng)級(jí)的網(wǎng)絡(luò)拓?fù)洌蝗绻鸦ヂ?lián)網(wǎng)中的路由器看成節(jié)點(diǎn)，而路由器間的連接關(guān)系看成邊，這樣就形成了路由器級(jí)的互聯(lián)網(wǎng)拓?fù)?/a>。 數(shù)學(xué)家和物理學(xué)家在研究網(wǎng)絡(luò)的時(shí)候，為了抓住本質(zhì)，通常進(jìn)行一定的抽象，表現(xiàn)在既不關(guān)心節(jié)點(diǎn)的特定物理位置、大小，也不在意邊的長(zhǎng)短、曲直、相交與否，只關(guān)心節(jié)點(diǎn)和節(jié)點(diǎn)間是否相連。例如，歐拉在解決哥尼斯堡七橋問題的時(shí)候，雖然當(dāng)時(shí)(1736年)討論長(zhǎng)短大小的幾何學(xué)是主流，而不考慮長(zhǎng)短大小、不牽涉量計(jì)算的情形幾乎沒人研究，但他卻撇開研究對(duì)象的長(zhǎng)短、大小、面積、體積等度量性質(zhì)和數(shù)量關(guān)系，把2座小島和河的兩岸分別抽象成4個(gè)點(diǎn)，而把7座橋抽象這4個(gè)點(diǎn)之間的連線，開創(chuàng)了拓?fù)溲芯康南群印．?dāng)人們把網(wǎng)絡(luò)抽象成這種不依賴于節(jié)點(diǎn)的位置、大小和邊的具體形態(tài)，所得到的性質(zhì)就成為網(wǎng)絡(luò)的拓?fù)湫再|(zhì)，相應(yīng)的結(jié)構(gòu)稱作網(wǎng)絡(luò)的拓?fù)浣Y(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)計(jì)特征(如度分布、聚集系數(shù)、平均最短路徑、度一度關(guān)聯(lián)性等)來刻畫，網(wǎng)絡(luò)功能由網(wǎng)絡(luò)上的動(dòng)態(tài)變化過程來反映。這兩者并非相互獨(dú)立，而是存在必然的本質(zhì)聯(lián)系。通常結(jié)構(gòu)決定功能，功能反過來影響網(wǎng)絡(luò)結(jié)構(gòu)的演化。例如，交通網(wǎng)中不同的結(jié)構(gòu)決定了網(wǎng)絡(luò)的容量有很大的不同，而交通量的增加也可能引起人們?cè)黾勇窂剑瑥亩绊懢W(wǎng)絡(luò)的演化。 2大規(guī)模復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析與其他學(xué)科的關(guān)系 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)知識(shí)需要通過拓?fù)浣Y(jié)構(gòu)分析獲得。當(dāng)前網(wǎng)絡(luò)科學(xué)關(guān)心的主要對(duì)象是大規(guī)模復(fù)雜網(wǎng)絡(luò)，如互聯(lián)網(wǎng)。而網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析方法是網(wǎng)絡(luò)科學(xué)的核心內(nèi)容。從學(xué)科角度看，這方面的研究要以傳統(tǒng)統(tǒng)計(jì)學(xué)、圖論、統(tǒng)計(jì)力學(xué)、隨機(jī)過程等學(xué)科為基礎(chǔ)。因?yàn)閺?fù)雜網(wǎng)絡(luò)規(guī)模巨大，網(wǎng)絡(luò)結(jié)構(gòu)又具有多樣性、動(dòng)態(tài)性、復(fù)雜性，必須經(jīng)過統(tǒng)計(jì)處理；而圖論提供了簡(jiǎn)潔精確的方法來描述網(wǎng)絡(luò)，已成為研究人員的共同語言和必要工具。近年來，國(guó)內(nèi)外已出版了相關(guān)的一些文章和專著。 但是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析方法與傳統(tǒng)學(xué)科中的方法還是有很大不同。傳統(tǒng)的統(tǒng)計(jì)學(xué)側(cè)重于對(duì)屬性數(shù)據(jù)的分析，網(wǎng)絡(luò)結(jié)構(gòu)的分析方法則通常側(cè)重于對(duì)關(guān)系數(shù)據(jù)的分析。屬性數(shù)據(jù)是指節(jié)點(diǎn)或一組節(jié)點(diǎn)自身?yè)碛械臄?shù)據(jù)。關(guān)系數(shù)據(jù)是指節(jié)點(diǎn)間關(guān)系、社團(tuán)(eOlllmullity)問關(guān)系、整體層次、塊層次間的關(guān)系，是2個(gè)或更多節(jié)點(diǎn)共同擁有的。關(guān)系數(shù)據(jù)與屬性數(shù)據(jù)是不同的分析對(duì)象，其分析方法也有很大的差異。 經(jīng)典圖論的研究對(duì)象通常只有幾個(gè)或幾十個(gè)節(jié)點(diǎn)，數(shù)學(xué)家們可以對(duì)其做精確的網(wǎng)絡(luò)優(yōu)化，而復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)分析方法處理的節(jié)點(diǎn)數(shù)目常常為數(shù)千、數(shù)萬、數(shù)億甚至更大規(guī)模，因此，需要從不同尺度作抽象。而過分抽象可能導(dǎo)致所得結(jié)論與實(shí)際情況相差甚遠(yuǎn)，從而引發(fā)各種爭(zhēng)論，這就要求研究者需要根據(jù)實(shí)際情況從不同尺度來看問題。常常可以發(fā)現(xiàn)，一個(gè)尺度上發(fā)現(xiàn)的結(jié)論在另一個(gè)尺度上并不一定成立。如互聯(lián)網(wǎng)自治系統(tǒng)級(jí)拓?fù)涞亩确植紳M足冪律【l，8惟1，而在互聯(lián)網(wǎng)路由器級(jí)拓?fù)渲校捎诼酚善鹘涌跀?shù)目的限制，度分布顯然不會(huì)滿足冪律。由于不同學(xué)科的研究者看問題的尺度不同，最近就引起了激烈的爭(zhēng)論，計(jì)算機(jī)網(wǎng)絡(luò)領(lǐng)域的研究人員對(duì)網(wǎng)絡(luò)科學(xué)領(lǐng)域的研究結(jié)論產(chǎn)生異議就是一例【9J。這好比拿《庖丁解牛》中的庖丁與普通廚師的工作做比較，庖丁是在反復(fù)實(shí)踐的基礎(chǔ)上，掌握牛的結(jié)構(gòu)(即事物的規(guī)律，現(xiàn)在的說法就是一個(gè)“科學(xué)問題”)，再去指導(dǎo)實(shí)踐(“解牛”)，而普通廚師則不必做庖丁的工作，只要把牛肉做成牛排、做成菜就可以直接滿足用戶需要了，更多的是一個(gè)“技術(shù)問題”。 也就是說，兩者是兩個(gè)層面的工作，但都是有益的工作。網(wǎng)絡(luò)結(jié)構(gòu)分析在社會(huì)網(wǎng)、技術(shù)網(wǎng)、生物網(wǎng)的研究和實(shí)踐中都已發(fā)揮了重要作用，互聯(lián)網(wǎng)就是一個(gè)典型的例子。作為一個(gè)真實(shí)網(wǎng)絡(luò)，互聯(lián)網(wǎng)從最初的4個(gè)節(jié)點(diǎn)，發(fā)展成為當(dāng)今世界的信息基礎(chǔ)設(shè)施，其應(yīng)用的深入發(fā)展和無處不在的廣泛性深刻地改變了人們的工作、生活和學(xué)習(xí)方式，己成為一個(gè)名副其實(shí)的具有復(fù)雜結(jié)構(gòu)的巨大系統(tǒng)。對(duì)互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)研究所蘊(yùn)含的科學(xué)意義和應(yīng)用價(jià)值正受到學(xué)術(shù)界、應(yīng)用部門和軍事部門的普遍重視。下面主要對(duì)互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)分析的成果及其應(yīng)用做比較詳細(xì)的說明。 3互聯(lián)網(wǎng)拓?fù)浣Y(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)計(jì)的特征量和度量方法來直觀地表征一個(gè)網(wǎng)絡(luò)的主要結(jié)構(gòu)特點(diǎn)。常用的刻畫一個(gè)網(wǎng)絡(luò)特征的指標(biāo)有：節(jié)點(diǎn)度分布、平均路徑長(zhǎng)度、聚集系數(shù)、度一度關(guān)聯(lián)性系數(shù)、介數(shù)、核數(shù)等。近年來，人們通過對(duì)互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)的分析，發(fā)現(xiàn)了多項(xiàng)互聯(lián)網(wǎng)的拓?fù)浣Y(jié)構(gòu)特征。 3．1冪律的發(fā)現(xiàn) 在互聯(lián)網(wǎng)拓?fù)溲芯恐校?999年法魯托斯(Faloutsos)等人對(duì)美國(guó)應(yīng)用網(wǎng)絡(luò)研究國(guó)家實(shí)驗(yàn)室(NLANR，nationallabforappliednetworkresearch)1997年至1998年的3份BGP(bordergatewaypro．toc01)數(shù)據(jù)以及1995年的一份traceroute眥探測(cè)數(shù)據(jù)進(jìn)行分析，發(fā)現(xiàn)了互聯(lián)網(wǎng)拓?fù)渲写嬖?條冪律。在SIGCOMM’99和《計(jì)算機(jī)通信評(píng)論(ComputerCommunicationReview)))…上。這個(gè)實(shí)驗(yàn)結(jié)論所指的冪律是近似冪律。這一結(jié)論最重要的是在本質(zhì)上揭示了節(jié)點(diǎn)間的差異，表明與原先占主導(dǎo)地位的隨機(jī)網(wǎng)絡(luò)【l州根本不同的是，在自治系統(tǒng)級(jí)拓?fù)渲校贁?shù)節(jié)點(diǎn)有大度值，而多數(shù)節(jié)點(diǎn)的度值小。 #p#分頁(yè)標(biāo)題#e# 這個(gè)發(fā)現(xiàn)引起了廣泛的關(guān)注，掀起了一股研究熱潮。需要特別說明的是，自治系統(tǒng)級(jí)拓?fù)渖隙确植紳M足冪律并不意味著互聯(lián)網(wǎng)在其他尺度(如路由器級(jí)拓?fù)?上也滿足冪律。 事實(shí)上，平常所見的構(gòu)成互聯(lián)網(wǎng)底層網(wǎng)絡(luò)的各種子網(wǎng)常常是星型、樹型等結(jié)構(gòu)，并不遵從冪律，但把這些子網(wǎng)互聯(lián)之后，從宏觀的自治系統(tǒng)層面看，就出現(xiàn)了冪律特征，這是一種“涌現(xiàn)”現(xiàn)象。這類似于社會(huì)科學(xué)領(lǐng)域中人類個(gè)體間的相互作用會(huì)產(chǎn)生經(jīng)濟(jì)制度，神經(jīng)元間相互作用會(huì)產(chǎn)生智力。 3．2小世界網(wǎng)絡(luò) 文獻(xiàn)【2】給出了具體的實(shí)驗(yàn)數(shù)據(jù)，說明了互聯(lián)網(wǎng)自治系統(tǒng)級(jí)拓?fù)溆行〉钠骄嚯x和較大的平均聚集系數(shù)，是一個(gè)“小世界”∞網(wǎng)絡(luò)。 文獻(xiàn)【11】分析了互聯(lián)網(wǎng)演化的數(shù)據(jù)，在2001年12月至2006年12月期間，互聯(lián)網(wǎng)自治系統(tǒng)拓?fù)渲泄?jié)點(diǎn)數(shù)目、邊的數(shù)目翻一番的情況下，平均距離為3．62—3．82，平均聚集系數(shù)為0．242～0．296，也驗(yàn)證了互聯(lián)網(wǎng)自治系統(tǒng)級(jí)拓?fù)渚哂行∈澜缇W(wǎng)絡(luò)的特征。 3．3同配性與異配性 紐曼(M．E．J．Newman)從節(jié)點(diǎn)度的角度考察多種網(wǎng)絡(luò)的度——度關(guān)聯(lián)性【12’l31，發(fā)現(xiàn)互聯(lián)網(wǎng)自治系統(tǒng)級(jí)拓?fù)涞倪B接存在異配性，即網(wǎng)絡(luò)中的大度節(jié)點(diǎn)傾向于與小度的節(jié)點(diǎn)連接。 文獻(xiàn)f14]從k．shell分解的角度考察多種網(wǎng)絡(luò)的層次關(guān)聯(lián)性，發(fā)現(xiàn)互聯(lián)網(wǎng)自治系統(tǒng)級(jí)拓?fù)涞倪B接存在層次異配性，即拓?fù)鋱D按k．shell分解后，外層傾向于和內(nèi)層的連接，而互聯(lián)網(wǎng)路由器級(jí)的拓?fù)浣Y(jié)構(gòu)呈現(xiàn)層次同配性。作為對(duì)比，互聯(lián)網(wǎng)自治系統(tǒng)拓?fù)浜吐酚善骷?jí)拓?fù)涞亩?mdash;—度關(guān)聯(lián)性卻均呈現(xiàn)異配性。 3．4高度節(jié)點(diǎn)間連接呈宦人俱樂部結(jié)構(gòu) 文獻(xiàn)【15】中指出，在互聯(lián)網(wǎng)自治系統(tǒng)拓?fù)渲校瑩碛写罅窟叺纳贁?shù)節(jié)點(diǎn)間更傾向于相互連接，并比擬地稱之為“富人俱樂部現(xiàn)象”，可以用富人俱樂部連通性系數(shù)痧(，．／Ⅳ)來刻畫：州Ⅳ)=而L該系數(shù)表示網(wǎng)絡(luò)中最大的前，個(gè)度的節(jié)點(diǎn)之間，實(shí)際存在的邊數(shù)L與這r個(gè)節(jié)點(diǎn)之間可能存在的最多連接邊數(shù)r(r一1)／2的比值。如果dp(r／Ⅳ)=1，說明最大的前，．個(gè)度節(jié)點(diǎn)組成的網(wǎng)絡(luò)為一個(gè)完全連通的子圖。 該文作者對(duì)互聯(lián)網(wǎng)自治系統(tǒng)拓?fù)渑c一些常見的網(wǎng)絡(luò)模型的富人俱樂部系數(shù)作了比較，在自治系統(tǒng)圖中極小比例的高度節(jié)點(diǎn)有大的連接數(shù)，而且其富人俱樂部系數(shù)大于常見的網(wǎng)絡(luò)模型的富人俱樂部系數(shù)。作者還在按度值大小排列的基礎(chǔ)上將所有節(jié)點(diǎn)劃分為20等份，比較了各區(qū)段間的連接邊數(shù)情況，也可以得出高度節(jié)點(diǎn)間有較多連接的結(jié)論。 文章在以上2個(gè)比較中認(rèn)為：在自治系統(tǒng)級(jí)拓?fù)渲芯哂?ldquo;富人俱樂部現(xiàn)象”。 文獻(xiàn)【16】對(duì)存在富人俱樂部現(xiàn)象提出了異議，他們認(rèn)為一個(gè)簡(jiǎn)單的富人俱樂部系數(shù)用于區(qū)別是否存在富人俱樂部現(xiàn)象是一個(gè)誤導(dǎo)，應(yīng)該將該度量建立在同樣度分布的隨機(jī)網(wǎng)絡(luò)基礎(chǔ)上，并提出了一種判定方法。 定義富人俱樂部系數(shù)與相同度序列隨機(jī)網(wǎng)絡(luò)的富人俱樂部系數(shù)的平均值之比死(七)=烈七)／諺。(七)，如果該值大于l，則說明該網(wǎng)絡(luò)存在富人俱樂部現(xiàn)象，否則不存在富人俱樂部現(xiàn)象。 文獻(xiàn)『17]對(duì)判定富人俱樂部現(xiàn)象提出了自己的看法，他們從統(tǒng)計(jì)的角度上提出了另一種判定方法：即對(duì)文獻(xiàn)[161所提出的相對(duì)富人俱樂部系數(shù)計(jì)算n次，然后統(tǒng)計(jì)在這n次中，相對(duì)富人俱樂部系數(shù)值小于等于1的概率，如果該概率值小于口(文中設(shè)口=5％)，則說明該網(wǎng)絡(luò)存在富人俱樂部現(xiàn)象。然而，文中最后舉了一個(gè)反例，說明這種方法在某些情況下也不適用。 至此，針對(duì)網(wǎng)絡(luò)中富人俱樂部現(xiàn)象的判定方法不斷進(jìn)步，但仍不完美。不同領(lǐng)域研究者從自己的學(xué)科特點(diǎn)給出了相應(yīng)的定義，從中也可看出工程技術(shù)背景的研究者與物理學(xué)研究者的思維方式的不同。 3．5共生效應(yīng) 通過對(duì)多種真實(shí)網(wǎng)絡(luò)的分析，文獻(xiàn)[18】發(fā)現(xiàn)了互聯(lián)網(wǎng)自治系統(tǒng)級(jí)拓?fù)渲谢?種不同中心性(度、介數(shù))都呈現(xiàn)富人俱樂部結(jié)構(gòu)(兩者的富人俱樂部系數(shù)趨于一致)，這種現(xiàn)象稱作富人俱樂部結(jié)構(gòu)的共生效應(yīng)。實(shí)證表明，許多真實(shí)網(wǎng)絡(luò)如互聯(lián)網(wǎng)路由器級(jí)拓?fù)洹⒌鞍踪|(zhì)交互網(wǎng)絡(luò)、科學(xué)家合作網(wǎng)絡(luò)都沒有(或較弱)這種效應(yīng)，而廣泛應(yīng)用的BA汁4模犁119]及其變種ESF(extendedscalefree)擴(kuò)展的無標(biāo)度網(wǎng)絡(luò)模型腳】、GLP(generalizedlinearpreference)廣義線性優(yōu)先12¨、PFP(positive—feedbackpreference)正反饋優(yōu)先【2副都有(較強(qiáng)的)這種效應(yīng)。這種效應(yīng)可以通過區(qū)別網(wǎng)絡(luò)的宏觀結(jié)構(gòu)來選擇是否采用BA模型及其變種，作為網(wǎng)絡(luò)建模的一個(gè)準(zhǔn)則。 3．6自相似結(jié)構(gòu) 研究了中國(guó)互聯(lián)網(wǎng)的拓?fù)涮卣鳎袊?guó)互聯(lián)網(wǎng)在網(wǎng)絡(luò)建設(shè)和規(guī)劃中要考慮已經(jīng)存在的許多中國(guó)特色，如社會(huì)制度不同、運(yùn)營(yíng)商的特點(diǎn)不同、用戶眾多等，但研究表明，作為世界互聯(lián)網(wǎng)的一部分，中國(guó)互聯(lián)網(wǎng)自治系統(tǒng)級(jí)拓?fù)渑c世界互聯(lián)網(wǎng)自治系統(tǒng)級(jí)拓?fù)涞闹饕暧^特征可以用同一個(gè)PFP模型模擬出來，表明作為互聯(lián)網(wǎng)局部的中國(guó)互聯(lián)網(wǎng)的拓?fù)浣Y(jié)構(gòu)與全球整體的互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)是自相似的18J。 傳統(tǒng)的自相似結(jié)構(gòu)通過分形的概念來刻畫【231，文獻(xiàn)[24】提出了互聯(lián)網(wǎng)結(jié)構(gòu)的一種概念模型Medusa：約占70％的節(jié)點(diǎn)構(gòu)成一個(gè)極大連通子圖。 這個(gè)子圖可以不經(jīng)過核(nucleus)而構(gòu)成一個(gè)連通圖，這個(gè)子圖存在自相似結(jié)構(gòu)，并可用分形的方法來刻畫。 3．7局部聚集現(xiàn)象 文獻(xiàn)【25】在局部聚集系數(shù)和節(jié)點(diǎn)度的關(guān)聯(lián)性、三角形的分布、連通子圖的冗余性3個(gè)方面研究了互聯(lián)網(wǎng)自治系統(tǒng)級(jí)拓?fù)渲械木植烤奂匦浴ｋm然表面上自治系統(tǒng)之間的連接大多數(shù)是自由選擇的，但在地區(qū)和國(guó)家區(qū)域劃分的現(xiàn)實(shí)環(huán)境下存在相當(dāng)強(qiáng)的局部聚集現(xiàn)象。說明互聯(lián)網(wǎng)的連接不是隨機(jī)建立的，節(jié)點(diǎn)傾向于和局域的節(jié)點(diǎn)連接。另外，低度節(jié)點(diǎn)間存在連接冗余性。這些冗余連接可以豐富網(wǎng)絡(luò)的路由選擇并增強(qiáng)網(wǎng)絡(luò)的健壯性。網(wǎng)絡(luò)的局部聚集特性會(huì)對(duì)網(wǎng)絡(luò)的性能產(chǎn)生很大的影響。#p#分頁(yè)標(biāo)題#e# 根據(jù)互聯(lián)網(wǎng)中觀察到的局部聚集現(xiàn)糾251，文獻(xiàn)[26】改進(jìn)了PFP模型，提出了LDPFP(10cality—drivenPFP)模型。 3．8向心性結(jié)構(gòu) 文獻(xiàn)[141把網(wǎng)絡(luò)經(jīng)k-core分解后各層節(jié)點(diǎn)與最深核(nucleus)節(jié)點(diǎn)傾向于連接的結(jié)構(gòu)稱作為向心性結(jié)構(gòu)，并指出互聯(lián)網(wǎng)自治系統(tǒng)級(jí)拓?fù)渚哂忻黠@的向心性結(jié)構(gòu)，這種結(jié)構(gòu)可以降低網(wǎng)絡(luò)的平均距離，提高路由效率。 3．9層次結(jié)構(gòu) 互聯(lián)網(wǎng)自治系統(tǒng)級(jí)拓?fù)涞膶哟谓Y(jié)構(gòu)有多種表述，如Jellyfish(水母)模型【27】以節(jié)點(diǎn)度為基礎(chǔ)，把自治系統(tǒng)級(jí)拓?fù)湫蜗蟮乇硎緸樗感螤睿籑edusa模型阱l以核數(shù)為基礎(chǔ)，把自治系統(tǒng)拓?fù)浞殖闪?個(gè)部分：由所有最大核數(shù)節(jié)點(diǎn)構(gòu)成最深核，剩余部分存在一個(gè)極大連通子圖以及其他孤立的連通塊；文獻(xiàn)【ll】提出了核心一邊緣模型，指出了核心與邊緣不同的演化規(guī)律，文獻(xiàn)【14]還提出了層次關(guān)聯(lián)性、向心性結(jié)構(gòu)等都從不同角度體現(xiàn)了互聯(lián)網(wǎng)的層次結(jié)構(gòu)。 3．10健壯而又脆弱 互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)具有“健壯而又脆弱”(robustyetfragile)的雙重特性，在不同尺度上，其形成機(jī)理不同。在自治系統(tǒng)級(jí)層面上同時(shí)表現(xiàn)出【28J：對(duì)節(jié)點(diǎn)隨機(jī)失效的健壯性和在有意攻擊情況下，只要移除少數(shù)重要節(jié)點(diǎn)，全網(wǎng)就會(huì)招致癱瘓，即表現(xiàn)為十分脆弱。這種脆弱性，也被稱作阿基琉斯之踵(Achilles’heel)。其根源在于度分布的不均勻性。 但在路由器級(jí)拓?fù)渖希憩F(xiàn)為互聯(lián)網(wǎng)可以有效容忍在設(shè)計(jì)時(shí)考慮到的不確定因素，具有健壯性，而對(duì)設(shè)計(jì)時(shí)未被考慮的不確定因素(如IP前綴劫持、分布式拒絕服務(wù))變得非常脆弱【29】。其雙重特性是由于考慮到網(wǎng)絡(luò)設(shè)計(jì)與優(yōu)化等因素形成的，根源不在網(wǎng)絡(luò)的度分布。4互聯(lián)網(wǎng)結(jié)構(gòu)知識(shí)的應(yīng)用網(wǎng)絡(luò)結(jié)構(gòu)知識(shí)無疑有廣泛的用處。利用結(jié)構(gòu)知識(shí)可以解決一些網(wǎng)絡(luò)性能、抗毀、安全傳輸?shù)葐栴}，散見于各類資料中，至今未發(fā)現(xiàn)有比較系統(tǒng)性的材料，如文獻(xiàn)[30】利用節(jié)點(diǎn)的度作為OSPF(openshortestpathfirst)路由協(xié)議中連接權(quán)值的一個(gè)因素，使得路徑更多樣化，流量更均衡；文獻(xiàn)【3l】利用自治系統(tǒng)拓?fù)渲羞吀罴暮暧^動(dòng)態(tài)變化來檢測(cè)網(wǎng)絡(luò)中前綴劫持的發(fā)生：文獻(xiàn)[32，33】把結(jié)構(gòu)知識(shí)應(yīng)用于可擴(kuò)展路由。多年前，筆者認(rèn)識(shí)到拓?fù)浣Y(jié)構(gòu)的重要性，近年與同事利用互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)知識(shí)在流量?jī)?yōu)化、網(wǎng)絡(luò)抗毀路由、服務(wù)器部署、網(wǎng)絡(luò)體系結(jié)構(gòu)、路由算法設(shè)計(jì)、節(jié)能等應(yīng)用方面做了探索，部分已逐漸應(yīng)用到多項(xiàng)實(shí)際工作中。具體的例子如下。 1)在流量?jī)?yōu)化方面，利用互聯(lián)網(wǎng)拓?fù)渲R(shí)降低骨干網(wǎng)流量、優(yōu)化網(wǎng)絡(luò)性能，提出了PPM(P2Pmatcher)技術(shù)，使上層對(duì)等連接(P2P)網(wǎng)絡(luò)與承載網(wǎng)絡(luò)的拓?fù)湎嗥ヅ?m了71，主要思想是根據(jù)節(jié)點(diǎn)的m前綴和自治系統(tǒng)號(hào)來優(yōu)化P2P應(yīng)用的鄰居選擇和數(shù)據(jù)調(diào)度，提高對(duì)等連接流量的本地化程度，比國(guó)際上具有類似思想的p4p138]出現(xiàn)早了3年。2009年，還提出利用網(wǎng)絡(luò)編碼數(shù)據(jù)調(diào)度算法并結(jié)合位置感知技術(shù)來優(yōu)化對(duì)等連接應(yīng)用流量的方法【391。該方法與此前的最好方法相比能將類似BT的服務(wù)的流量降低一半，幾乎接近理論極限，從而可以實(shí)現(xiàn)ISP、P2P內(nèi)容提供商和終端用戶三贏的完美局面。部分工作正成為國(guó)家通信行業(yè)標(biāo)準(zhǔn)136J的主要內(nèi)容，國(guó)內(nèi)所有網(wǎng)絡(luò)運(yùn)營(yíng)商和主要設(shè)備制造商都參與了該標(biāo)準(zhǔn)的制定。另外，還針對(duì)互聯(lián)網(wǎng)中大量NAT(networkaddresstranslation)的客觀存在，進(jìn)行對(duì)等連接流量?jī)?yōu)化，提出了穿越私網(wǎng)的解決方案I姐411，旨在充分地利用接入網(wǎng)絡(luò)的資源，進(jìn)一步提高對(duì)等連接流量的本地化程度，減輕域間和骨干網(wǎng)絡(luò)上的流量。 2)在網(wǎng)絡(luò)抗毀方面，通過構(gòu)建一個(gè)覆蓋(oveday)網(wǎng)絡(luò)體系結(jié)構(gòu)來實(shí)現(xiàn)。為了在覆蓋網(wǎng)絡(luò)中可以構(gòu)建更加多樣化的網(wǎng)絡(luò)路徑以及使構(gòu)造的備用路徑的平均長(zhǎng)度較短、轉(zhuǎn)發(fā)效率更高，利用介數(shù)和核數(shù)刻畫網(wǎng)絡(luò)的特征，提出了一種在覆蓋網(wǎng)絡(luò)中可以實(shí)現(xiàn)高效選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)的算法1421。另外，利用核數(shù)和度的一些特點(diǎn)，結(jié)合轉(zhuǎn)發(fā)節(jié)點(diǎn)位置信息及鏈路性能測(cè)量結(jié)果，達(dá)到所生成的備用路徑的可靠性更高、實(shí)用性更吲4引，這些工作為抗毀路由的實(shí)施提供了技術(shù)保障。 3)在服務(wù)器部署方面，文獻(xiàn)[441從網(wǎng)絡(luò)結(jié)構(gòu)特征的角度對(duì)覆蓋網(wǎng)絡(luò)研究領(lǐng)域中覆蓋中繼服務(wù)器部署低效問題進(jìn)行研究，利用互聯(lián)網(wǎng)異配特性和富人俱樂部結(jié)構(gòu)的特點(diǎn)(即度大的節(jié)點(diǎn)既傾向于與度小的節(jié)點(diǎn)連接同時(shí)又與度大的節(jié)點(diǎn)連接比較密集)，提出一種基于度等級(jí)的覆蓋中繼放置(DROP'degreerankbasedoverlayrelaysplacement)的啟發(fā)式方案。該方案可以有效地選取一組用來放置覆蓋中繼節(jié)點(diǎn)的位置集合，使用很少的物理拓?fù)湫畔⒈憧梢詢?yōu)化整個(gè)中國(guó)互聯(lián)網(wǎng)的冗余性和通信可靠性。 4)文獻(xiàn)[451為了提高網(wǎng)絡(luò)服務(wù)的性能，有效利用自治系統(tǒng)粒度上拓?fù)浣Y(jié)構(gòu)信息相對(duì)穩(wěn)定且信息量適度的特征，使多路徑覆蓋路由的效率最大化，設(shè)計(jì)了分布式啟發(fā)式路由選擇算法BFSQ。仿真結(jié)果表明BFSQ算法可以為終端節(jié)點(diǎn)有效選取多條覆蓋路徑，并可在實(shí)際的覆蓋系統(tǒng)構(gòu)建中部署實(shí)施。 上面2)～4)利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)知識(shí)實(shí)現(xiàn)了服務(wù)器部署、轉(zhuǎn)發(fā)節(jié)點(diǎn)選取、路徑多樣性等關(guān)鍵技術(shù)，為實(shí)現(xiàn)網(wǎng)絡(luò)傳輸優(yōu)化、網(wǎng)絡(luò)抗毀等目標(biāo)構(gòu)建了一個(gè)具有overlay網(wǎng)絡(luò)體系結(jié)構(gòu)的實(shí)際系統(tǒng)【伯】，這項(xiàng)實(shí)踐不同于前人的網(wǎng)絡(luò)體系結(jié)構(gòu)研究工作，引入了體現(xiàn)網(wǎng)絡(luò)摹本屬性的拓?fù)涮卣鳎瑸橥負(fù)浣Y(jié)構(gòu)知識(shí)與網(wǎng)絡(luò)體系結(jié)構(gòu)研究相結(jié)合提供了積極有益的探索，把網(wǎng)絡(luò)科學(xué)知識(shí)應(yīng)用到了網(wǎng)絡(luò)工程技術(shù)中。未來將進(jìn)一步對(duì)后IP網(wǎng)絡(luò)研究產(chǎn)生積極影響。 5)在路由算法設(shè)計(jì)方面，文獻(xiàn)【47】提出了利用網(wǎng)絡(luò)的無標(biāo)度和強(qiáng)聚集特征來設(shè)計(jì)可擴(kuò)展的路由算法，將網(wǎng)絡(luò)看成由一個(gè)骨干樹和許多捷徑組成。 由于無標(biāo)度網(wǎng)絡(luò)上的長(zhǎng)捷徑很少，因此使用骨干樹和少數(shù)長(zhǎng)捷徑構(gòu)造的生成樹可以在路由表規(guī)模和拉伸系數(shù)上獲得較低的上限，通過實(shí)驗(yàn)驗(yàn)證了該方法的有效性。文獻(xiàn)【48】提出了一系列基于最大度地標(biāo)的緊湊路由算法——HDLR、HDLR+、NIHDLR+，具有比通用的緊湊路由算法更優(yōu)的基本性能，仿真驗(yàn)證了這些方法的有效性。#p#分頁(yè)標(biāo)題#e# 6)在優(yōu)化網(wǎng)絡(luò)容量方面，把網(wǎng)絡(luò)結(jié)構(gòu)知識(shí)用于擴(kuò)大網(wǎng)絡(luò)容量，在最短路徑路由占主導(dǎo)地位的情況下，提出了刪邊擴(kuò)容的方法D9J和在節(jié)點(diǎn)能力總和不變條件下，基于節(jié)點(diǎn)度的最優(yōu)節(jié)點(diǎn)能力分配方法即】。 利用刪邊擴(kuò)容策略，可以實(shí)現(xiàn)接入網(wǎng)流量?jī)?yōu)化140’4¨，也可實(shí)現(xiàn)高效轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇，避免擁塞【421。 7)在節(jié)能方面，文獻(xiàn)【5l】通過設(shè)計(jì)對(duì)能耗敏感的網(wǎng)絡(luò)拓?fù)洌镁酆虾托菝叻椒▽?shí)現(xiàn)網(wǎng)絡(luò)中處于工作狀態(tài)的設(shè)備數(shù)與網(wǎng)絡(luò)負(fù)載正相關(guān)，當(dāng)負(fù)載減輕時(shí)，更多設(shè)備會(huì)休眠，從而實(shí)現(xiàn)節(jié)能。另外，通過上述提到的P2P流量?jī)?yōu)化、服務(wù)器部署等方法大幅降低交通量以及在NAT環(huán)境下私網(wǎng)穿透方案[40,41]中增加感知等技術(shù)，達(dá)到節(jié)能目的。 8)文獻(xiàn)[52】以網(wǎng)絡(luò)體系結(jié)構(gòu)為匯合點(diǎn)，將拓?fù)浣Y(jié)構(gòu)研究同制度經(jīng)濟(jì)學(xué)研究結(jié)合起來，對(duì)體系結(jié)構(gòu)衍生的契約進(jìn)行分析。重點(diǎn)研究向用戶開放末端網(wǎng)絡(luò)的技術(shù)，提高自治度從而豐富契約關(guān)系，并進(jìn)一步產(chǎn)生促進(jìn)網(wǎng)絡(luò)經(jīng)濟(jì)發(fā)展的作用。這種研究不僅幫助我們理解互聯(lián)網(wǎng)體系結(jié)構(gòu)及其系統(tǒng)在微觀經(jīng)濟(jì)學(xué)層面上的意義，同時(shí)從經(jīng)濟(jì)學(xué)層面提出了衡量網(wǎng)絡(luò)體系結(jié)構(gòu)實(shí)用性的評(píng)價(jià)方法。 5結(jié)束語 正如弄清事物的結(jié)構(gòu)是人類認(rèn)識(shí)一個(gè)事物和對(duì)其進(jìn)行改造過程中首先面臨的基本問題一樣，對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的掌握也是認(rèn)識(shí)和改進(jìn)網(wǎng)絡(luò)的基礎(chǔ)。互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)是互聯(lián)網(wǎng)信息基礎(chǔ)設(shè)施最基本的內(nèi)在屬性。對(duì)互聯(lián)網(wǎng)拓?fù)涮卣骱椭R(shí)的發(fā)現(xiàn)及其應(yīng)用正在快速發(fā)展中。當(dāng)前熱點(diǎn)的信息系統(tǒng)工程領(lǐng)域(如云計(jì)算、三網(wǎng)融合、智慧地球、社會(huì)計(jì)算、物聯(lián)網(wǎng)等)都離不開互聯(lián)網(wǎng)這個(gè)信息基礎(chǔ)設(shè)施，上節(jié)介紹的各種應(yīng)用中部分可以用于這些工程。對(duì)互聯(lián)網(wǎng)結(jié)構(gòu)的揭示及其知識(shí)的深入理解，可以為人們有效利用網(wǎng)絡(luò)、合理構(gòu)建以互聯(lián)網(wǎng)為基礎(chǔ)的信息系統(tǒng)工程提供科學(xué)依據(jù)，為網(wǎng)絡(luò)建設(shè)、升級(jí)改造、上層應(yīng)用的優(yōu)化、設(shè)計(jì)新一代網(wǎng)絡(luò)體系結(jié)構(gòu)和協(xié)議提供理論指導(dǎo)。 互聯(lián)網(wǎng)是網(wǎng)絡(luò)科學(xué)領(lǐng)域的一個(gè)典型的網(wǎng)絡(luò)實(shí)例，對(duì)其拓?fù)浣Y(jié)構(gòu)知識(shí)的深入研究與應(yīng)用可以豐富網(wǎng)絡(luò)科學(xué)的內(nèi)涵，推動(dòng)網(wǎng)絡(luò)科學(xué)這個(gè)新興學(xué)科的發(fā)展。網(wǎng)絡(luò)科學(xué)具有廣泛的交叉性和復(fù)雜性，涉及數(shù)學(xué)、物理、計(jì)算機(jī)、系統(tǒng)科學(xué)等眾多學(xué)科，在數(shù)學(xué)中，又常常涉及圖論、統(tǒng)計(jì)學(xué)、隨機(jī)過程、拓?fù)鋵W(xué)等知識(shí)。網(wǎng)絡(luò)科學(xué)對(duì)復(fù)雜系統(tǒng)的一般性描述和總結(jié)出的規(guī)律也為深入研究互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)或其他具體網(wǎng)絡(luò)提供新的視角和指導(dǎo)。 當(dāng)前，國(guó)家有關(guān)部門正著力部署后口網(wǎng)絡(luò)、三網(wǎng)融合、網(wǎng)絡(luò)輿情等方面的研究，應(yīng)該不失時(shí)機(jī)把網(wǎng)絡(luò)科學(xué)知識(shí)與網(wǎng)絡(luò)工程技術(shù)結(jié)合起來。網(wǎng)絡(luò)與通信領(lǐng)域的頂級(jí)會(huì)議INFOCOM在2010年首次引入網(wǎng)絡(luò)科學(xué)的專題討論。期待在不久的將來，在網(wǎng)絡(luò)結(jié)構(gòu)分析領(lǐng)域能有更多樸素優(yōu)雅的科學(xué)發(fā)現(xiàn)，為技術(shù)的進(jìn)步提供方法論指導(dǎo)，進(jìn)而產(chǎn)生簡(jiǎn)潔高效的技術(shù)方法服務(wù)于社會(huì)。
