無尺度網(wǎng)絡(luò)分析與研究

摘要:講述了無尺度網(wǎng)絡(luò)的發(fā)現(xiàn)及其特性， 介紹了無尺度網(wǎng)絡(luò)對(duì)于科學(xué)研究的意義，并指出了其面臨的挑戰(zhàn)。

關(guān)鍵詞:無尺度網(wǎng)絡(luò);冪次定律;集散節(jié)點(diǎn)

中圖分類號(hào):TP301.6 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009-3044(2009)15-3876-02

The Analysis and research of Scale-free Networks

LIU Qing-Feng

(Anyang Institute of Technology， Anyang 455000， China)

Abstract: This paper describes the discovery of scale-free networks and their properties， introduces briefly the significance of scale-free networks for research of science， and point out the challenges it faced.

Key words: scale-free networks; power law; networks hub-node

1 引言

社會(huì)也是一個(gè)網(wǎng)絡(luò)，它由友情、家庭和職業(yè)關(guān)系彼此連結(jié)。在更大的尺度上，食物鏈和生態(tài)系統(tǒng)可以看作是由物種所構(gòu)成的網(wǎng)絡(luò)。大腦，也是由軸突相連結(jié)的神經(jīng)細(xì)胞網(wǎng)絡(luò)組成的，而細(xì)胞本身，又是生化反應(yīng)相連結(jié)的分子網(wǎng)絡(luò)。科技領(lǐng)域的網(wǎng)絡(luò)更是隨處可見:因特網(wǎng)、電力網(wǎng)和運(yùn)輸系統(tǒng)都是實(shí)例。就連在文章中我們用以向你傳遞思想的語言，也是一種由語法相互串連在一起的文字網(wǎng)絡(luò)。

盡管網(wǎng)絡(luò)是如此重要和普遍，但科學(xué)家對(duì)它的結(jié)構(gòu)和屬性卻知之不多。在復(fù)雜的基因網(wǎng)絡(luò)中，故障節(jié)點(diǎn)是如何相互作用而引發(fā)癌癥的?在特定的社會(huì)和通信系統(tǒng)中，疾病和電腦病毒如何快速傳播而導(dǎo)致流行?某些網(wǎng)絡(luò)即便大部分節(jié)點(diǎn)失效，還能維持運(yùn)行，原因何在?

2 無尺度網(wǎng)絡(luò)

網(wǎng)絡(luò)有隨機(jī)網(wǎng)絡(luò)和無尺度網(wǎng)絡(luò)，許多網(wǎng)絡(luò)包括因特網(wǎng)、人類社會(huì)和人體細(xì)胞代謝網(wǎng)絡(luò)等，都是無尺度網(wǎng)絡(luò)。網(wǎng)民對(duì)網(wǎng)站的訪問，可以說是獨(dú)立、自由的，完全取決于網(wǎng)民本人的主觀意愿。在做大量統(tǒng)計(jì)實(shí)驗(yàn)之前，科學(xué)家預(yù)測(cè)，連接數(shù)k應(yīng)當(dāng)服從泊松分布或正態(tài)分布，即每個(gè)網(wǎng)站的被訪問量差異不會(huì)太大，就像人類身高差異不會(huì)太大那樣。然而，實(shí)測(cè)結(jié)果推翻了這個(gè)預(yù)測(cè)。Barabasi等人設(shè)計(jì)了一種軟件，可以從一個(gè)節(jié)點(diǎn)跳到另一節(jié)點(diǎn)，收集并記錄網(wǎng)上的所有連接。在對(duì)幾十萬個(gè)節(jié)點(diǎn)進(jìn)行統(tǒng)計(jì)之后，發(fā)現(xiàn)了令人驚異的結(jié)果:當(dāng)絕大多數(shù)網(wǎng)站的連接數(shù)很少的情況下，卻有極少數(shù)網(wǎng)站擁有高于普通網(wǎng)站百倍、千倍甚至萬倍的連接數(shù)。就像在茫茫人海中突然發(fā)現(xiàn)若干身高數(shù)百尺巨人那樣令人意外。巨人的身高之大，已不能用普通人高度的尺度來度量，于是想出了“無尺度”的用詞，形容少數(shù)節(jié)點(diǎn)連接數(shù)大大超出普通節(jié)點(diǎn)的現(xiàn)象。

上述實(shí)驗(yàn)結(jié)果可以用冪次定律表達(dá):出現(xiàn)連接數(shù)為k的概率 p(k)，反比于k的n次方( P (k ) ～ k-n )。其中，n稱為冪數(shù)，它是很接近于2的一個(gè)常數(shù)。

2.1無尺度網(wǎng)絡(luò)的特性

很多復(fù)雜系統(tǒng)擁有共同的重要特性:大部分節(jié)點(diǎn)只有少數(shù)幾個(gè)連結(jié)，而某些節(jié)點(diǎn)卻擁有與其他節(jié)點(diǎn)的大量連結(jié)。這些具有大量連結(jié)的節(jié)點(diǎn)稱為“集散節(jié)點(diǎn)”，所擁有的連結(jié)可能高達(dá)數(shù)百、數(shù)千甚至數(shù)百萬。由此看來，這一特性似乎能說明網(wǎng)絡(luò)是無尺度的。

無尺度網(wǎng)絡(luò)具有某些重要特性。例如它們都可以承受意外的故障，但面對(duì)協(xié)同式攻擊卻很脆弱。

了解這些特性，可能導(dǎo)致許多領(lǐng)域出現(xiàn)新的應(yīng)用。例如，電腦科學(xué)家可能據(jù)此設(shè)計(jì)出更有效的策略，以保護(hù)因特網(wǎng)免受電腦病毒的侵害。

2.2 無尺度網(wǎng)絡(luò)的存在

過去幾年中，研究者在很多不同的系統(tǒng)中都發(fā)現(xiàn)了無尺度結(jié)構(gòu)。我們研究萬維網(wǎng)的目標(biāo)是以超連結(jié)彼此串連的虛擬網(wǎng)頁網(wǎng)絡(luò)。相比之下，美國(guó)加州大學(xué)河濱分校的Faloutsos、加拿大多倫多大學(xué)的Faloutsos以及美國(guó)卡耐基梅隆大學(xué)的Faloutsos則是分析因特網(wǎng)的物理結(jié)構(gòu)。這三位電腦科學(xué)家兄弟研究了以光纖或其他通信線路連接的路由器，他們發(fā)現(xiàn)，這個(gè)實(shí)體網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)也是無尺性的。

3 無尺度網(wǎng)絡(luò)的形成原因

無尺度網(wǎng)絡(luò)的形成主要有兩個(gè)原因。

3.1 成長(zhǎng)性

萬維網(wǎng)的頁面數(shù)量絕對(duì)不是恒定的。1990年整個(gè)萬維網(wǎng)只有一個(gè)網(wǎng)頁，而到今天它的網(wǎng)頁數(shù)已經(jīng)超過了30億。大部分網(wǎng)絡(luò)也都具有類似的發(fā)展過程。1890年好萊塢只有屈指可數(shù)的幾位演員，但隨著越來越多的人加入這個(gè)行業(yè)，新人與之演員建立聯(lián)系，如今這個(gè)網(wǎng)絡(luò)已經(jīng)超過了50萬人。大約30年前，整個(gè)因特網(wǎng)只有幾個(gè)路由器，隨著新的路由器與網(wǎng)絡(luò)原有的路由器相連結(jié)，如今路由器的數(shù)量已經(jīng)高達(dá)百萬。由于現(xiàn)實(shí)中的網(wǎng)絡(luò)具有不斷成長(zhǎng)的本性，所以老節(jié)點(diǎn)獲得連結(jié)的機(jī)會(huì)就比較高。

3.2 優(yōu)先性

此外，并非所有的節(jié)點(diǎn)都是平等的。在選擇將網(wǎng)頁連結(jié)到何處時(shí)，人們可以從數(shù)十億個(gè)網(wǎng)站中進(jìn)行選擇。然而我們大部分人只熟悉整個(gè)萬維網(wǎng)的一小部分，這一小部分中往往包含那些擁有較多連結(jié)的站點(diǎn)，因?yàn)檫@樣的站點(diǎn)更容易為人所知。只要連結(jié)到這些站點(diǎn)，就等于造就或加強(qiáng)了對(duì)它們的偏好。這種“優(yōu)先連結(jié)”的過程，也發(fā)生在其他網(wǎng)絡(luò)。在好萊塢，連結(jié)關(guān)系較多的影星更容易受到新秀們的重視。而在因特網(wǎng)上，那些連結(jié)較多的路由器通常還擁有更大的帶寬，因而新用戶就更傾向于連結(jié)到這些路由器上。在美國(guó)的生物技術(shù)產(chǎn)業(yè)內(nèi)，象Genzyme這樣的知名公司更容易吸引到同盟者，而這又進(jìn)一步加強(qiáng)了它在未來合作中的吸引力。類似地，被引用較多的科學(xué)文獻(xiàn)，會(huì)吸引更多的研究者去閱讀和引用。美國(guó)著名的社會(huì)學(xué)家K·Merton將這種現(xiàn)象稱之為“馬太效應(yīng)”。這個(gè)詞來源于《新約》圣經(jīng)的內(nèi)容:“凡有的，還要加給他，叫他有余。”

成長(zhǎng)性和優(yōu)先連結(jié)這兩種機(jī)制，有助于解釋集散節(jié)點(diǎn)的存在。當(dāng)新節(jié)點(diǎn)出現(xiàn)時(shí)，它們更傾向于連結(jié)到已經(jīng)有較多連結(jié)的節(jié)點(diǎn)，隨著時(shí)間的推進(jìn)，這些節(jié)點(diǎn)就擁有比其他節(jié)點(diǎn)更多的連結(jié)數(shù)目。這種“富者逾富”的過程，有利于早期節(jié)點(diǎn)，它們更有可能成為集散節(jié)點(diǎn)。

4 無尺度網(wǎng)絡(luò)的潛在意義

4.1 運(yùn)算

具有無尺度結(jié)構(gòu)的計(jì)算機(jī)網(wǎng)絡(luò)，例如萬維網(wǎng)，對(duì)意外故障具有極強(qiáng)的承受能力，但面對(duì)蓄意的攻擊和破壞卻可能不堪一擊。 要想在因特網(wǎng)上徹底清除病毒，即使是已知的病毒，也是不可能的。

4.2 醫(yī)學(xué)

對(duì)天花等嚴(yán)重疾病的疫苗接種，如果能針對(duì)集散節(jié)點(diǎn)(即那些與很多人具有連結(jié)關(guān)系的人)進(jìn)行，也許可以達(dá)到最大的效果，但要找出屬于集散節(jié)點(diǎn)的人非常困難。

弄清人體細(xì)胞內(nèi)的網(wǎng)絡(luò)結(jié)構(gòu)，將有助于研究者發(fā)現(xiàn)和控制藥物的副作用。此外，若能識(shí)別出那些與特定疾病有關(guān)的集散點(diǎn)分子，就可開發(fā)只針對(duì)這些集散節(jié)點(diǎn)作用的新藥物。

4.3 商業(yè)

了解公司、產(chǎn)業(yè)與經(jīng)濟(jì)之間的連結(jié)方式，有助于研究人員監(jiān)控和預(yù)防大規(guī)模的經(jīng)濟(jì)衰退。

研究流行病在無尺度網(wǎng)絡(luò)中的傳播現(xiàn)象，為市場(chǎng)人員傳播他們的新產(chǎn)品提供了新方法。

5 無尺度網(wǎng)絡(luò)面臨的挑戰(zhàn)

無尺度網(wǎng)絡(luò)對(duì)意外故障具有驚人的強(qiáng)韌性，這一特性本質(zhì)上源于這些網(wǎng)絡(luò)的非同質(zhì)拓?fù)浣Y(jié)構(gòu)。隨機(jī)去除的方式所破壞的主要是那些不重要的節(jié)點(diǎn)，因?yàn)樗鼈兊臄?shù)目遠(yuǎn)大于集散節(jié)點(diǎn)。與那些幾乎連結(jié)所有節(jié)點(diǎn)的集散節(jié)點(diǎn)相此。那些不重要的節(jié)點(diǎn)只擁有少量的連結(jié)。因而去除它們不會(huì)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)產(chǎn)生重大的影響。但是，對(duì)集散節(jié)點(diǎn)的依賴，也帶來了一個(gè)嚴(yán)重問題:面對(duì)蓄意攻擊時(shí)，網(wǎng)絡(luò)可能不堪一擊。通過一系列的模擬，我們發(fā)現(xiàn)，只要去除少數(shù)幾個(gè)主要集散節(jié)點(diǎn)，就可導(dǎo)致因特網(wǎng)潰散成孤立無援的小群路由器。

無尺度網(wǎng)絡(luò)的這一致命缺陷，引發(fā)了這樣一個(gè)問題:到底有多少集散節(jié)點(diǎn)是必不可少的?最近的研究表明，總的來說，只要有5-10%的集散節(jié)點(diǎn)同時(shí)失效，就足以搞垮系統(tǒng)。我們對(duì)因特網(wǎng)的實(shí)驗(yàn)顯示，一次有組織的協(xié)同攻擊，只要去除掉若干個(gè)集散節(jié)點(diǎn)(先去除最大的，再去除次大的，依次類推)，就足以造成重大破壞。

6 結(jié)束語

為了避免因惡意攻擊帶來網(wǎng)絡(luò)的大規(guī)模破壞，最有效的辦法就是保護(hù)好集散節(jié)點(diǎn)。不過，要想知道特定的網(wǎng)絡(luò)系統(tǒng)到底有多容易被破壞掉，還有待進(jìn)一步的研究。

參考文獻(xiàn):

[1 ]Andrew Y.Wu Michael Garland Jiawei Han. Mining Scale-free Networks using Geodesic Clustering [J].KDD’04 August: 719-724.

[2] Albert R， Barabási A L. Statistical mechanics of complex networks [J]. Rev. Mod. Phys，2002， 74: 47- 97.

[3] Newman M E J. The structure and function of complex network s [J]. Society for Industrial and Applied Mathematics， 2003， 45: 167-256.

[4] 李幼平.無尺度現(xiàn)象引發(fā)的思考——文化傳播對(duì)網(wǎng)絡(luò)的反作用[EB/OL]. 中國(guó)工程物理研究院(傳媒投資網(wǎng)2005-3-18發(fā)布)

[5] 無尺度網(wǎng)絡(luò)[J]. 摘自《科學(xué)美國(guó)人》中文版2003.7

[6] Yan Gang， ZhouTao， Wang Jie， Fu Zhong-Qian， Wang Bing-Hong. Epidemic spread in weighted scale-free networks [J]. September 13， 2004 .

[7] Watts D J， Strogatz S H. Collective dynamics of small world networks [J].Nature. 1998， 393:440- 442.

[8] Barabási A L， Albert R. Emergence of scaling in random networks [J]. Science， 1999， 286:509-512.