無標(biāo)度網(wǎng)絡(luò)：基礎(chǔ)理論和應(yīng)用研究

史定華

(上海大學(xué)數(shù)學(xué)系 上海 寶山區(qū) 200444)

20世紀(jì)末21世紀(jì)初，《自然》和《科學(xué)》相繼發(fā)表了3篇重要的關(guān)于網(wǎng)絡(luò)的文章：小世界網(wǎng)絡(luò)模型[1]說明了少量的隨機(jī)捷徑會(huì)改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，從而涌現(xiàn)出小世界效應(yīng)；無標(biāo)度網(wǎng)絡(luò)模型[2]揭示了增長(zhǎng)和擇優(yōu)機(jī)制在復(fù)雜網(wǎng)絡(luò)自組織演化過程中的普遍性和冪律的重要性；可導(dǎo)航網(wǎng)絡(luò)模型[3]則解釋了如何利用局部信息尋找網(wǎng)絡(luò)中的最短路徑。這些模型說明復(fù)雜系統(tǒng)也可由某些簡(jiǎn)單規(guī)則自組織演化而形成。

復(fù)雜網(wǎng)絡(luò)理論與應(yīng)用發(fā)展至今已十余年，其轟動(dòng)效果和強(qiáng)烈沖擊很大程度上歸功于《自然》和《科學(xué)》上的一系列開創(chuàng)性論文[2,4-7]。雖然這些論文的思想新穎動(dòng)人，但也留下了廣闊的發(fā)展空間。為了復(fù)雜網(wǎng)絡(luò)理論與應(yīng)用的健康發(fā)展，本文基于文獻(xiàn)[8]，逐一展開討論，說明加強(qiáng)基礎(chǔ)理論和應(yīng)用研究的重要性。對(duì)無標(biāo)度網(wǎng)絡(luò)過去十年的發(fā)展情況及未來前景，文獻(xiàn)[8]要點(diǎn)總結(jié)如下：

(1) 通過對(duì)萬維網(wǎng)結(jié)構(gòu)調(diào)查得到的情況指出網(wǎng)絡(luò)并非都是隨機(jī)連線，而是顯示出增長(zhǎng)和擇優(yōu)連線兩種機(jī)制，這恰是使得網(wǎng)絡(luò)產(chǎn)生冪律度分布的可能的原因。

(2) 許多真實(shí)的網(wǎng)絡(luò)系統(tǒng)，從細(xì)胞到因特網(wǎng)，都收斂到類似的(度分布為冪律)結(jié)構(gòu)上，而與它們的年齡、方式和規(guī)模等無關(guān)。

(3) 無標(biāo)度特性的意義之一在于認(rèn)識(shí)到網(wǎng)絡(luò)的結(jié)構(gòu)和演化不可分割，即真實(shí)的網(wǎng)絡(luò)是動(dòng)態(tài)的而非靜態(tài)的，網(wǎng)絡(luò)處在不斷的變化之中。

(4) 在無標(biāo)度網(wǎng)絡(luò)(如因特網(wǎng)等)中，網(wǎng)絡(luò)整體的連通性對(duì)節(jié)點(diǎn)隨機(jī)故障的魯棒性以及hub nodes易受蓄意攻擊而遭到大規(guī)模破壞具有“穩(wěn)健而又脆弱”的特性。

(5) 從度分布到度?度相關(guān)性等等，不同網(wǎng)絡(luò)拓?fù)涮卣鞯膹V泛存在被作為研究不同現(xiàn)象以及作出預(yù)測(cè)的跳板，除非探討網(wǎng)絡(luò)拓?fù)洌駝t無法理解復(fù)雜系統(tǒng)。

(6) 需要攻克的下一個(gè)前沿問題是理解在網(wǎng)絡(luò)上發(fā)生的動(dòng)力學(xué)過程。共性是存在的，只是還沒有發(fā)現(xiàn)能夠解釋網(wǎng)絡(luò)動(dòng)力學(xué)的普適框架。

(7) 雖然復(fù)雜系統(tǒng)的許多研究熱潮來了又走，但是有一件事日益清楚，即單元之間的相互連接(作用)如此重要，這正是現(xiàn)今關(guān)注網(wǎng)絡(luò)的原因。

本文將分5個(gè)小節(jié)展開討論。

1 BA模型和萬維網(wǎng)因特網(wǎng)

一系列開創(chuàng)性論文中，文獻(xiàn)[2]尤其引人關(guān)注。論文的主要思想有：從許多實(shí)際復(fù)雜網(wǎng)絡(luò)度分布的統(tǒng)計(jì)結(jié)果發(fā)現(xiàn)，具有冪律尾部是其普遍的特征；提出一個(gè)擇優(yōu)增長(zhǎng)的動(dòng)態(tài)模型(即BA模型)去解釋產(chǎn)生冪律的機(jī)制；認(rèn)為正確的模型其網(wǎng)絡(luò)度分布應(yīng)該獨(dú)立于時(shí)間。從此，具有冪律度分布的網(wǎng)絡(luò)被稱為無標(biāo)度(scale-free)網(wǎng)絡(luò)。然而，該文存在某些不夠完善之處。

首先，文獻(xiàn)[9]指出BA模型有兩點(diǎn)不夠明確：一是初始網(wǎng)絡(luò)沒有設(shè)定，孤立節(jié)點(diǎn)無法擇優(yōu)連線；二是有多條連線時(shí)如何進(jìn)行擇優(yōu)連接，是一條一條連線還是同時(shí)連線？前者擇優(yōu)概率會(huì)改變，后者度分布結(jié)果大相經(jīng)庭。所以，模型定義不明確將難以開展理論研究。為此，文獻(xiàn)[9]提出了同時(shí)允許節(jié)點(diǎn)自連線和節(jié)點(diǎn)之間重復(fù)連線的線性化弦圖(linearized chord diagram)模型。通過允許節(jié)點(diǎn)之間重復(fù)連線但不允許節(jié)點(diǎn)自連線，文獻(xiàn)[10]引入了一個(gè)原始吸引模型避免BA模型連線的不明確。為了提高BA模型的群集系數(shù)，文獻(xiàn)[11]提出了一種不允許重復(fù)連線的方式：第1條連線按節(jié)點(diǎn)度擇優(yōu)連接，其余m?1條連線在被第1條連線選中節(jié)點(diǎn)的鄰域依次不重復(fù)連線。

利用鞅論和馬氏鏈等數(shù)學(xué)理論已經(jīng)嚴(yán)格證明：上述3個(gè)模型都具有與BA模型用啟發(fā)式方法得到的相同度分布。

其次，文獻(xiàn)[12]認(rèn)為僅以度分布是冪律作為無標(biāo)度網(wǎng)定義不盡合理。一方面，網(wǎng)絡(luò)拓?fù)涑硕确植纪膺€有度?度相關(guān)性等許多測(cè)度；另一方面，因?yàn)閮缏墒欠讲羁赡軣o窮的高可變分布，由于存在極大的波動(dòng)性，所以冪律相同的度分布網(wǎng)絡(luò)完全可能具有極其不同的拓?fù)浣Y(jié)構(gòu)和特性。該文獻(xiàn)從度?度相關(guān)性引入一個(gè)測(cè)量無標(biāo)度程度的量，發(fā)現(xiàn)對(duì)具有相同冪律度分布的網(wǎng)絡(luò)，有的顯示為“無標(biāo)度”，有的卻顯示為“標(biāo)度豐富”。因特網(wǎng)和代謝網(wǎng)的度分布雖然為冪律，但卻是標(biāo)度豐富的兩個(gè)典型案例，它們面對(duì)蓄意攻擊仍然“穩(wěn)健而非脆弱”。文獻(xiàn)[13]針對(duì)因特網(wǎng)進(jìn)行詳細(xì)解釋，同時(shí)說明BA模型不是因特網(wǎng)的恰當(dāng)模型，從流量、帶寬以及技術(shù)可靠等設(shè)計(jì)角度提出了一個(gè)啟發(fā)式最優(yōu)拓?fù)淠Ｐ汀?/p>

其中，度指數(shù)相對(duì)網(wǎng)絡(luò)規(guī)模穩(wěn)健，系數(shù)需要重點(diǎn)探討。

用模型網(wǎng)絡(luò)的度分布預(yù)測(cè)實(shí)際網(wǎng)絡(luò)高度數(shù)的概率時(shí)會(huì)嚴(yán)重偏離或失效，文獻(xiàn)[16]提出研究有限標(biāo)度問題，發(fā)現(xiàn)有限標(biāo)度函數(shù)會(huì)顯著地依賴于初始網(wǎng)絡(luò)。許多研究工作[17-18]報(bào)道了網(wǎng)絡(luò)動(dòng)力學(xué)行為也依賴于網(wǎng)絡(luò)規(guī)模的大小。另外，萬維網(wǎng)和因特網(wǎng)的連線增長(zhǎng)明顯快于節(jié)點(diǎn)增長(zhǎng)[19-20]，同樣，BA模型也不是萬維網(wǎng)和因特網(wǎng)的合理模型。復(fù)制模型[15]的平均度對(duì)數(shù)增長(zhǎng)，文獻(xiàn)[14]提出的飽和模型增長(zhǎng)有個(gè)上限，或許它們才是更恰當(dāng)?shù)哪Ｐ汀?/p>

2 層次網(wǎng)絡(luò)模型和代謝網(wǎng)絡(luò)

文獻(xiàn)[8]雖然沒有提及代謝網(wǎng)絡(luò)和層次組織兩篇開創(chuàng)性論文[5-6]。但文獻(xiàn)[5-6]統(tǒng)計(jì)了大量的代謝網(wǎng)絡(luò)，發(fā)現(xiàn)它們是無標(biāo)度的，度指數(shù)接近2.2以及群集系數(shù)與度k存在反比關(guān)系。生物網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)最重要的應(yīng)用領(lǐng)域之一，為了給代謝網(wǎng)絡(luò)建立恰當(dāng)?shù)哪Ｐ?，Barabási等人提出了確定的層次網(wǎng)絡(luò)模型。然而層次網(wǎng)絡(luò)、偽分形圖、阿波羅網(wǎng)等幾何增長(zhǎng)網(wǎng)絡(luò)的度分布和度指數(shù)在文獻(xiàn)上就一直是頗有爭(zhēng)議的問題。該問題還與實(shí)際網(wǎng)絡(luò)度分布的統(tǒng)計(jì)有關(guān)，因此值得在此討論。

文獻(xiàn)[21]提出了第一個(gè)確定性的層次網(wǎng)絡(luò)，得到該模型網(wǎng)絡(luò)的度分布為：

其實(shí)，正確的答案文獻(xiàn)[12]早就給出。關(guān)于冪律和標(biāo)度首先要有一個(gè)正確的定義，文獻(xiàn)[12]對(duì)確定的和隨機(jī)的兩種情況都有詳盡的論述。幾何增長(zhǎng)網(wǎng)絡(luò)和實(shí)際網(wǎng)絡(luò)數(shù)據(jù)都屬于確定的情況，復(fù)雜網(wǎng)絡(luò)文獻(xiàn)判斷度分布和度指數(shù)有畫頻率圖、畫logarithmic binning圖、畫秩次(或類同的補(bǔ)分布)圖3種方法。秩次圖是以秩次為縱坐標(biāo)，將N個(gè)節(jié)點(diǎn)的度從大到小排序，依序給予從1～N的秩次所畫的圖。在雙對(duì)數(shù)坐標(biāo)上，如果圖形近似為一條直線，就認(rèn)為是冪律；負(fù)的斜率為度指數(shù)，秩次(補(bǔ)分布)方法需要加1。顯然，頻率方法忽略了頻率為零的度，結(jié)論容易誤導(dǎo)；logarithmic binning是一種粗?；椒?，也不可靠；正確的方法是畫秩次圖。所以幾何增長(zhǎng)網(wǎng)絡(luò)正確的度指數(shù)應(yīng)該加1才對(duì)。另外，文獻(xiàn)[27]論述了代謝網(wǎng)是標(biāo)度豐富的，因此層次網(wǎng)絡(luò)不是代謝網(wǎng)的恰當(dāng)模型。

3 無標(biāo)度網(wǎng)絡(luò)的動(dòng)力學(xué)特性

文獻(xiàn)[7]是第一篇?jiǎng)恿W(xué)文獻(xiàn)。通過模擬比較了ER隨機(jī)圖和BA無標(biāo)度網(wǎng)對(duì)節(jié)點(diǎn)刪除的影響。考慮兩種節(jié)點(diǎn)刪除方式：一是某些節(jié)點(diǎn)隨機(jī)失效；二是蓄意攻擊hub nodes。對(duì)10 000個(gè)節(jié)點(diǎn)20 000條連線，橫坐標(biāo)f表示刪除節(jié)點(diǎn)比例，縱坐標(biāo)d表示網(wǎng)絡(luò)直徑變化，結(jié)果如圖1所示。

圖1 指數(shù)網(wǎng)絡(luò)與無標(biāo)度網(wǎng)絡(luò)其直徑d關(guān)于f的曲線[7]

從圖1可以看出：對(duì)ER隨機(jī)圖，隨機(jī)失效和蓄意攻擊沒有區(qū)別；但對(duì)無標(biāo)度網(wǎng)絡(luò)，隨機(jī)失效和蓄意攻擊顯著不同。如何解釋這種動(dòng)力學(xué)性質(zhì)的差異？文獻(xiàn)[7]認(rèn)為是ER隨機(jī)圖節(jié)點(diǎn)同質(zhì)而BA無標(biāo)度網(wǎng)節(jié)點(diǎn)異質(zhì)，即存在hub nodes所致。該期《自然》雜志還特別在封面用標(biāo)題為《因特網(wǎng)的Achilles踵(heel)》的文章對(duì)此發(fā)現(xiàn)做了介紹。Achilles是古希臘傳說中的一位杰出英雄，但他的腳后跟與普通人一樣存在致命弱點(diǎn)。換句話說，Achilles踵也就是中國(guó)武功的“罩門”。能找到復(fù)雜網(wǎng)絡(luò)的罩門，對(duì)網(wǎng)絡(luò)科學(xué)當(dāng)然意義重大。

這里有兩個(gè)問題需要認(rèn)真思考，一是“穩(wěn)健而又脆弱”是否為無標(biāo)度網(wǎng)的普適特性？二是究竟什么原因造成復(fù)雜網(wǎng)絡(luò)對(duì)蓄意攻擊脆弱？關(guān)于第一個(gè)問題，文獻(xiàn)[12]給予了否定的回答。然而，第二個(gè)問題的回答就沒有那么簡(jiǎn)單。是不是因?yàn)榇嬖趆ub nodes，即度數(shù)很大的少數(shù)節(jié)點(diǎn)，答案顯然不全面，因?yàn)槿魏斡邢蘧W(wǎng)絡(luò)都存在最大度節(jié)點(diǎn)。而是否與這些hub nodes的連接方式有關(guān)，將在下一小節(jié)討論。值得一提的是，文獻(xiàn)[28]對(duì)類似于BA模型的LCD模型，用數(shù)學(xué)方法就第二個(gè)問題進(jìn)行了嚴(yán)格的理論證明。證明篇幅長(zhǎng)達(dá)35頁，主要結(jié)論是：BA無標(biāo)度網(wǎng)絡(luò)比ER隨機(jī)圖更穩(wěn)健而又更脆弱的主要原因是由于擇優(yōu)連線。

網(wǎng)絡(luò)動(dòng)力學(xué)的另一個(gè)重要發(fā)現(xiàn)[29]是：在無標(biāo)度網(wǎng)絡(luò)中，傳染病的傳播閾值收斂于0。這只是對(duì)BA無標(biāo)度網(wǎng)絡(luò)得到的理論結(jié)果，因?yàn)閷?shí)際網(wǎng)絡(luò)都是有限網(wǎng)絡(luò)，需要考慮網(wǎng)絡(luò)有限規(guī)模的影響[16]。文獻(xiàn)[17]最近發(fā)現(xiàn)，無標(biāo)度網(wǎng)絡(luò)的動(dòng)力學(xué)模型有兩類不同的有限網(wǎng)絡(luò)影響，一類只依賴有限網(wǎng)絡(luò)的規(guī)模N(等于模擬步數(shù)t加m0)；另一類同時(shí)依賴有限網(wǎng)絡(luò)的規(guī)模N和上割kc。

4 網(wǎng)絡(luò)核心和度?度相關(guān)性

文獻(xiàn)[12]認(rèn)為hub nodes的連接方式?jīng)Q定了度分布為冪律的網(wǎng)絡(luò)對(duì)蓄意攻擊是否脆弱。文獻(xiàn)[12]繪制了4個(gè)路由器層次因特網(wǎng)模型的網(wǎng)絡(luò)如圖2所示。

圖2 具有完全相同數(shù)目的節(jié)點(diǎn)、連線和冪律度分布的4個(gè)路由器層次因特網(wǎng)模型

它們具有完全相同數(shù)目的節(jié)點(diǎn)、連線及冪律度分布，但帶寬(灰度深淺)卻不同。HSF(無標(biāo)度層次)網(wǎng)是基于文獻(xiàn)[6]的層次網(wǎng)絡(luò)模型；隨機(jī)(重連)網(wǎng)是從HSF通過保度重連得到的。拙劣設(shè)計(jì)網(wǎng)是將高度節(jié)點(diǎn)排成一條線，然后讓低度節(jié)點(diǎn)與高度節(jié)點(diǎn)連線；HOT(啟發(fā)式最優(yōu)拓?fù)?網(wǎng)有3層結(jié)構(gòu)，高帶寬低連通節(jié)點(diǎn)位于核心，而低帶寬高連通節(jié)點(diǎn)位于外圍。從圖中可以看出，圖2a和圖2b具有網(wǎng)絡(luò)核心，它們的高度數(shù)節(jié)點(diǎn)傾向于相互連接，即所謂網(wǎng)絡(luò)節(jié)點(diǎn)同配；圖2c和圖2d不像具有網(wǎng)絡(luò)核心，因?yàn)樗鼈兊母叨葦?shù)節(jié)點(diǎn)傾向于連接低度數(shù)節(jié)點(diǎn)，即網(wǎng)絡(luò)節(jié)點(diǎn)異配。文獻(xiàn)[13]的詳細(xì)研究說明：實(shí)際的因特網(wǎng)并不像HSF網(wǎng)，至少在定性上像HOT網(wǎng)。文獻(xiàn)[12]計(jì)算了該4個(gè)網(wǎng)絡(luò)的Newman相關(guān)系數(shù)r(g)[32]，然而，所得的數(shù)值都落在區(qū)間[?0.481 5, ?0.428 3]中，不足以區(qū)分。為此該文獻(xiàn)提出了一個(gè)無標(biāo)度程度新測(cè)度。

對(duì)BA模型通過模擬和計(jì)算得到r(g)和S(g)的結(jié)果如圖3所示。

圖3 r(g)和S(g)分別關(guān)于m和N的趨勢(shì)[33]

不難發(fā)現(xiàn)，r(g)和S(g)都顯著地依賴網(wǎng)絡(luò)的規(guī)模和網(wǎng)絡(luò)的平均度，所以這兩個(gè)測(cè)度對(duì)有限的實(shí)際網(wǎng)絡(luò)很難給出一個(gè)有意義的數(shù)值。另外，從圖3b可以看出，BA模型的無標(biāo)度程度也不能算大，但它面對(duì)蓄意攻擊卻是“穩(wěn)健而又脆弱”！

因此，本文同意文獻(xiàn)[8]的觀點(diǎn)：“除非(深入)探討網(wǎng)絡(luò)拓?fù)?，否則無法理解復(fù)雜系統(tǒng)”。網(wǎng)絡(luò)度?度相關(guān)性的完整信息包含在網(wǎng)絡(luò)聯(lián)合度分布中，目前文獻(xiàn)上只有BA模型的部分結(jié)果[34]，還沒有像度指數(shù)(或動(dòng)力學(xué)指數(shù))那樣簡(jiǎn)便的最佳測(cè)度。

為此，以網(wǎng)絡(luò)平均度為分界線，按度將節(jié)點(diǎn)分成大度和小度兩類，同類節(jié)點(diǎn)連線稱為同配，異類節(jié)點(diǎn)連線稱為異配，通過計(jì)算同配、異配數(shù)目，文獻(xiàn)[33]嘗試提議了一個(gè)簡(jiǎn)單的測(cè)度，模擬顯示對(duì)BA模型能做到與網(wǎng)絡(luò)規(guī)模無關(guān)。而且該測(cè)度與網(wǎng)絡(luò)疏密程度存在冪律關(guān)系，直觀上，網(wǎng)絡(luò)的疏密程度與網(wǎng)絡(luò)的抗毀性有關(guān)，所以網(wǎng)絡(luò)核心與網(wǎng)絡(luò)疏密程度有關(guān)應(yīng)該是合理的。

5 網(wǎng)絡(luò)馬氏鏈(圖值馬氏過程)

復(fù)雜網(wǎng)絡(luò)十年來的發(fā)展和成就毋容置疑，涉及領(lǐng)域的廣泛也使個(gè)人無法全局把握。其中物理學(xué)家的思想火花絢麗無比，物理社團(tuán)的大力推動(dòng)也功不可沒。前面對(duì)復(fù)雜網(wǎng)絡(luò)的討論負(fù)面評(píng)價(jià)較多，本節(jié)介紹復(fù)雜網(wǎng)絡(luò)中主觀認(rèn)為的兩個(gè)正面結(jié)果：一個(gè)是復(fù)雜網(wǎng)絡(luò)信息檢索，屬于應(yīng)用研究范疇；另一個(gè)是模型網(wǎng)絡(luò)度分布證明，屬于基礎(chǔ)理論領(lǐng)域，兩者都與網(wǎng)絡(luò)馬氏鏈或稱圖值馬氏過程有關(guān)。

在谷歌中輸入“荷塘月色”，馬上會(huì)出現(xiàn)許多條目，有朱自清的散文“荷塘月色”，有各種美麗的荷塘圖片，甚至?xí)霈F(xiàn)荷塘春色和可愛的青蛙形象，如圖4所示。人類上網(wǎng)沖浪就像青蛙在荷頁上跳動(dòng)，而馬氏鏈可以形象地用“荷塘春色蛙歡跳”來描述?！昂商猎律笨杀扔鳛殡[馬氏模型，只聞蛙聲，不見蛙跳，在生物信息學(xué)中有廣泛應(yīng)用，如圖5所示。

谷歌為什么會(huì)有如此強(qiáng)大的功能？它的原理依賴于復(fù)雜網(wǎng)絡(luò)的拓?fù)浜蛿?shù)學(xué)中的馬氏鏈。根據(jù)論文引用和被引用的思想，文獻(xiàn)[35]完成了網(wǎng)絡(luò)搜索和存儲(chǔ)，剩下尋找為網(wǎng)頁評(píng)定等級(jí)的方法。他們發(fā)明了一種基于網(wǎng)頁重要性的排序算法：一是看有多少超級(jí)鏈接指向它(入度)；二是要看那個(gè)頁面重要不重要(出度)，并命名為PageRank。因此，問題可歸結(jié)到求有向圖連線矩陣的非負(fù)特征向量，最后轉(zhuǎn)變?yōu)橛?jì)算有限馬氏鏈的平穩(wěn)分布。值得一提的是，文獻(xiàn)[36]當(dāng)時(shí)正好提出了中心網(wǎng)頁和權(quán)威網(wǎng)頁的評(píng)級(jí)系統(tǒng)，他們交流了各自的工作。該文作者由于提出可導(dǎo)航網(wǎng)絡(luò)模型和分散搜索算法，2006年獲得了世界數(shù)學(xué)家大會(huì)三大獎(jiǎng)之一的Nevanlinna獎(jiǎng)。

谷歌搜索引擎雖然取得了巨大成功，但排序只依賴頁面的連線(度)，因此會(huì)面臨垃圾網(wǎng)站的嚴(yán)重干擾。文獻(xiàn)[37]針對(duì)上述情況在2008年原創(chuàng)性地提出考慮用戶瀏覽過程的網(wǎng)頁排序，并把他們的算法取名為BrowseRank。根據(jù)用戶訪問網(wǎng)頁和網(wǎng)頁轉(zhuǎn)移的頻率數(shù)據(jù)qi和qij得Q-過程的轉(zhuǎn)移概率矩陣P=[qij/qi]，使問題轉(zhuǎn)化為求Q-過程的平穩(wěn)分布。他們的論文被評(píng)為當(dāng)年ACM會(huì)議唯一的最佳學(xué)生論文獎(jiǎng)，國(guó)際媒體用標(biāo)題“Microsoft tries to one-up Google PageRank”做了報(bào)道。

圖4 馬氏鏈?zhǔn)疽鈭D

圖5 隱馬氏鏈?zhǔn)疽鈭D

上述復(fù)雜網(wǎng)絡(luò)信息檢索工作，大家天天都在受益，堪稱復(fù)雜網(wǎng)絡(luò)成功應(yīng)用的典范。

6 結(jié) 束 語

復(fù)雜網(wǎng)絡(luò)在發(fā)展過程中存在欠妥并不可怕，貴在勇于修正錯(cuò)誤，因?yàn)榭茖W(xué)本身就被設(shè)計(jì)成尋找并改正錯(cuò)誤的過程，即科學(xué)的完整性(the integrity of science)。

通過對(duì)文獻(xiàn)[8]“無標(biāo)度網(wǎng)絡(luò)：過去十年及未來前景”一文的探討，即使在復(fù)雜網(wǎng)絡(luò)拓?fù)浞矫嫒匀挥性S多問題需要理清。至于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)方面，本文同意Barabási的觀點(diǎn)：“(只是)還沒有發(fā)現(xiàn)能夠解釋它們普遍性的框架”。因此加強(qiáng)復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論和應(yīng)用研究具有緊迫的重要意義。

回憶20世紀(jì)相對(duì)論與幾何學(xué)、量子力學(xué)與泛函分析的美好聯(lián)姻，新世紀(jì)會(huì)不會(huì)有一段復(fù)雜網(wǎng)絡(luò)(統(tǒng)計(jì)力學(xué))與馬氏過程的浪漫愛情？如果有，那將成為科學(xué)史上的佳話。

[1] WATTS D J, STROGATZ S H. Collective dynamics of small-world networks[J]. Nature, 1998, 393: 440-442.

[2] BARABáSI A-L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286: 509-512.

[3] KLEINBERG J M. Navigation in a small world[J]. Nature,2000, 406: 845.

[4] ALBERT R, JEONG H, BARABáSI A-L. Diameter of the world-wide web[J]. Nature, 1999, 401: 130-131.

[5] JEONG H, TOMBOR B, ALBERT R, et al. The large-scale organization of metabolic networks[J]. Nature, 2000, 407:651-654.

[6] RAVASZ E, SOMERA A L, MONGRU D A, et al.Hierarchical organization of modularity in metabolic networks[J]. Science, 2002, 297: 1551-1555.

[7] ALBERT R, JEONG H, BARABáSI A-L. Error and attack tolerance of complex networks[J]. Nature, 2000, 406:378-382.

[8] BARABáSI A-L. Scale-free networks: A decade and beyond[J]. Science, 2009, 325: 412-413.

[9] BOLLOBáS B, RIORDAN O M, SPENCER J, et al. The degree sequence of a scale-free random graph process[J].Random Structures and Algorithms, 2001, 18: 279-290.

[10] DOROGOVTSEV S N, MENDES J F F, SAMUKHIN A N.Structure of growth networks with preferential linking[J].PRL, 2000, 85: 4633-4636.

[11] HOLME P, KIM B J. Growing scale-free networks with tunable clustering[J]. PRE, 2002, 65: 026107.

[12] LI L, ALDERSON D, DOYLE J C, et al. Towards a theory of scale-free graphs: definitions, properties, and implications[J]. Internet Math, 2005, 2: 431-523.

[13] DOYLE J C, ALDERSON D, LI L, et al. The “robust yet fragile” nature of the Internet[J]. PNAS USA, 2005, 102:14497-14502.

[14] SHI D H, ZHOU H J, LIU L M. A discussion of Barabási and Albert’s 1999 paper[J]. Physics Procedia 2010, 3:1767-1774.

[15] KRAPIVSKY P L, REDNER S. Network growth by coping[J]. PRE, 2005, 71: 036118.

[16] KRAPIVSKY P L, REDNER S. Finiteness and fluctuations in growing networks[J]. Physica A: Math Gen, 2002, 35:9517-9534.

[17] HONG H, HA M, PARK H. Finite-size scaling in complex networks[J]. PRL, 2007, 98: 258701.

[18] CASTELLANO C, PASTOR-SATORRAS R. Routes to thermodynamic limit on scale-free networks[J]. PRL, 2008,100: 148701.

[19] BRODER A, KUMAR R, MAGHOUL F, et al. Graph structure in the web[J]. Computer Networks, 2000, 33:309-320.

[20] ZHANG G Q, ZHANG G Q, YAN Q F, et al. Evolution of the Internet and its cores[J]. New J Phys, 2008, 10: 123027.[21] BARABáSI A-L, RAVASZ E, VICSEK T. Determinic scale-free networks[J]. Physica A, 2001, 229: 559-564.

[22] FARKAS I, DERéNYI I, JEONG H, et al. Networks in life:scaling properties and eigenvalue spectra[J]. Physica A,2002, 314: 25-34.

[23] RAVASZ E, BARABáSI A-L. Hierarchical organization in complex networks[J]. PRE, 2003, 67: 026112.

[24] DOROGOVTSEV S N, GOTSEV A V, MENDES J F F.Pseudofractal scale-free web[J]. PRE, 2002, 65: 066122.

[25] ANDRADE J S, HERRMANN H J, ANDRADE R F S, et al. Apollonian networks[J]. PRL, 2005, 94: 018702.

[26] ANDRADE J S, HERRMANN H J, ANDRADE R F S, et al. Erratum: Apollonian networks[J]. PRL, 2009, 102:079901.

[27] TANAKA R. Scale-rich metabolic networks[J]. PRL, 2005,94: 168101.

[28] BOLLOBáS B, RIORDAN O. Robustness and vulnerability of scale-free random graphs[J]. Internet Math,2004, 1: 1-35.

[29] PASTOR-SATORRAS R, VESPIGNANI A. Epidemic spreading in scale-free networks[J]. PRL, 2001, 86: 3200-3203.

[30] MóRI T. F. The maximum degree of the Barabási random tree[J]. Combinatorics, Probability and Computing, 2005,14: 339-348.

[31] 周暉杰, 葉 臣, 閻春寧, 等. BA模型網(wǎng)絡(luò)最大度的發(fā)散和擾動(dòng)[C]// 數(shù)學(xué)·力學(xué)·物理學(xué)·高新技術(shù)交叉研究進(jìn)展. 北京: 科學(xué)出版社, 2010, 13: 232-237.ZHOU H J, YE C, YAN C N, et al. Divergence form and fluctuation law of the maximum degree in the BA model[C]// The progress of interdisciplinary research for mathematics, physics and high new technology[M]. Beijing:Science Press. Beijing: Science Press, 2010, 13: 232-237.

[32] NEWMAN M E J. Assortative mixing in networks[J]. PRL,2002, 89: 208701.

[33] 史定華, 周暉杰. 一種新的度相關(guān)測(cè)度[C]//第六屆全國(guó)復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議. 蘇州: 中國(guó)工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)專業(yè)委員會(huì), 2010.SHI D H, ZHOU H J. A new measurement for degree correlation[C]//The 6thChinese Conference of Complex Networks. Suzhou: China Society of Industrial and Applied Mathematics, Complex Systems and Complex Networks Technical Committee, 2010.

[34] KRAPIVSKY P L, REDNER S. Organization of growing random networks[J]. PRE, 2001, 63: 066123.

[35] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks and ISDN Systems, 1998, 30: 107-117.

[36] KLEINBERG J M. Authoritative sources in a hyperlinked environment[J]. J ACM, 1999, 46: 604-632.

[37] LIU Y T, GAO B, LIU T Y, et al. BrowseRank: letting web users vote for page importance[C]//Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, Singapore, ACM NY USA, 2008: 451-458.

[38] KRAPIVSKY P L, REDNER S, LEYVRAZ F.Connectivity of growing random networks[J]. PRL, 2000,85: 4629-4632

[39] COOPER C, FRIEZE A. A general model of Web graphs[J].Random Structures and Algorithms, 2003, 22: 311-335.

[40] SHI D H, CHEN Q H, LIU L M. Markov chain-based numerical method for degree distributions of growing networks[J]. PRE, 2005, 71: 036140.

[41] HOU Z T, KONG X X, SHI D H, et al. Degree-distribution stability of scale-free networks[J]. arXiv: 0805.1434v1[math.PR] 9 May 2008

[42] XU H, SHI D H. Stability of the BA network: a new approach to rigorous proof[J]. CPL, 2009, 26: 038901-4.

[43] SHI D H, XU H, LIU L M. A vertex-number-evolving markov chain of networks[J]. Physics Procedia 2010, 3,1757-1765.

[44] ZHOU J. (Ed.). Complex sciences——lecture notes of the institute for computer sciences, social informactics and telecommunications engineering[M]. [S.l.]: Springer, 2009:1827-1837.

[45] SHI D H, ZHOU H J, LIU L M. Markovian iterative method for degree distributions of growing networks[J].PRE, 2010, 82: 031105.