一類度互質(zhì)的無標(biāo)度網(wǎng)絡(luò)研究

蘇志忠+劉煥龍+孔祥泉

摘 要： 本文提出了一類度互質(zhì)的嚴(yán)格無標(biāo)度網(wǎng)絡(luò)模型，刻畫出其節(jié)點(diǎn)分布規(guī)律，并基于這種模型進(jìn)一步分析了冪指數(shù)大于2與小于等于2時(shí)無標(biāo)度網(wǎng)絡(luò)拓?fù)湫再|(zhì)的區(qū)別。

關(guān)鍵詞： 冪指數(shù) 無標(biāo)度網(wǎng)絡(luò) 平均度

一、引言

20世紀(jì)末以來，復(fù)雜網(wǎng)絡(luò)的研究逐步滲透到物理、生命科學(xué)、社會科學(xué)等眾多不同的領(lǐng)域，成為網(wǎng)絡(luò)時(shí)代科學(xué)研究極其重要的挑戰(zhàn)性課題。這股研究熱潮的起源是由國際上兩項(xiàng)開創(chuàng)性工作掀起的，其一是1998年Watts和Strogatz在Nature雜志上發(fā)表的論文，該文引入了小世界（Small-World）網(wǎng)絡(luò)模型，描述了完全規(guī)則網(wǎng)絡(luò)及完全隨機(jī)網(wǎng)絡(luò)之間的異同與完全規(guī)則網(wǎng)絡(luò)到完全隨機(jī)網(wǎng)絡(luò)的轉(zhuǎn)變。具有小世界性質(zhì)的網(wǎng)絡(luò)既具有與規(guī)則網(wǎng)絡(luò)相似的聚類特性，又具有與隨機(jī)網(wǎng)絡(luò)相似的較小的平均路徑長度。第二項(xiàng)重要工作是1999年Barabási和Albert在Science上發(fā)表的論文，該文基于對WWW的實(shí)證研究，指出眾多實(shí)際存在的復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)度分布具有冪律規(guī)律而不是均勻分布或高斯分布。由于冪律分布沒有明顯的特征長度，在概率論中具有無標(biāo)度特征性質(zhì)的分布僅有冪律分布，該類網(wǎng)絡(luò)又被人們稱為無標(biāo)度（Scale-Free）網(wǎng)絡(luò)[2]。由于現(xiàn)實(shí)世界中大多數(shù)無標(biāo)度網(wǎng)絡(luò)的標(biāo)度指數(shù)介于2和3之間，之后的幾年人們只對冪指數(shù)大于2的無標(biāo)度網(wǎng)絡(luò)進(jìn)行了研究，直到2005年，Seyed-allaei等關(guān)注到冪指數(shù)小于2的網(wǎng)絡(luò)，他們基于隨機(jī)不相關(guān)的無標(biāo)度網(wǎng)絡(luò)研究了網(wǎng)絡(luò)的平均度、結(jié)構(gòu)最大度及聚集系數(shù)，指出了冪指數(shù)小于2和冪指數(shù)大于2的無標(biāo)度網(wǎng)絡(luò)的拓?fù)湫再|(zhì)明顯不同。接下來國內(nèi)學(xué)者吳俊、王林、劉艷霞等進(jìn)一步研究了冪指數(shù)不大于2的無標(biāo)度網(wǎng)絡(luò)的拓?fù)湫再|(zhì)?；谇叭说墓ぷ鳎軇⑵G霞提出的一種素?cái)?shù)網(wǎng)絡(luò)模型的啟發(fā)，筆者觀察到這種嚴(yán)格的無標(biāo)度網(wǎng)絡(luò)模型具有以下局限性：（1）只能為素?cái)?shù)。（2）冪指數(shù)只能為整數(shù)。

因?yàn)橹挥袃缰笖?shù)為整數(shù)時(shí)才能保證度及其相應(yīng)的節(jié)點(diǎn)數(shù)都為整數(shù)。為了更好地研究無標(biāo)度網(wǎng)絡(luò)的拓?fù)湫再|(zhì)，本文提出了一類度互質(zhì)的無標(biāo)度網(wǎng)絡(luò)模型，這種嚴(yán)格的無標(biāo)度網(wǎng)絡(luò)模型中的度之間只需滿足互質(zhì)條件，且冪指數(shù)的數(shù)值可以取任意有意義的有理數(shù)。

從表1和圖2，能夠進(jìn)一步地認(rèn)識到無標(biāo)度網(wǎng)絡(luò)在γ取不同值時(shí)，呈現(xiàn)出截然不同的性質(zhì)。當(dāng)γ>2時(shí)，網(wǎng)絡(luò)平均度隨著網(wǎng)絡(luò)規(guī)模的增大基本不變，邊數(shù)緩慢增加，網(wǎng)絡(luò)相對比較稀疏。而當(dāng)1≤γ≤2時(shí)，網(wǎng)絡(luò)平均度隨著網(wǎng)絡(luò)規(guī)模的增大呈迅速上漲趨勢，也就是說，最小度節(jié)點(diǎn)所占的比例越來越小，最大度節(jié)點(diǎn)或者度數(shù)較大的節(jié)點(diǎn)所占的比例增大，網(wǎng)絡(luò)的邊數(shù)相對于節(jié)點(diǎn)快速增大，網(wǎng)絡(luò)越來越稠密。

四、結(jié)語

基于前人的結(jié)果，本文提出了一類度互質(zhì)的無標(biāo)度網(wǎng)絡(luò)模型，通過研究它的度分布特征，進(jìn)一步驗(yàn)證了冪指數(shù)大于2和冪指數(shù)不大于2的無標(biāo)度網(wǎng)絡(luò)的拓?fù)湫再|(zhì)，對進(jìn)一步研究無標(biāo)度網(wǎng)絡(luò)的拓?fù)湫再|(zhì)具有一定的作用。下一步，我們力爭找到這類網(wǎng)絡(luò)的實(shí)際應(yīng)用，并基于這種網(wǎng)絡(luò)模型進(jìn)一步研究冪指數(shù)在不同范圍時(shí)拓?fù)湫再|(zhì)及路由算法。

參考文獻(xiàn)：

[1]Watts D J，Strogatz S H.Collective dynamics of small-world networks[J].Nature.1998，393（6684）：440-442.

[2]Albert R，Jeong H，Barabási A.Internet：Diameter of the world-wide web[J].Nature.1999，401（6749）：130-131.

[3]Barabási A，Albert R.Emergence of scaling in random networks[J].Science.1999，286（5439）：509-512.

[4]Seyed-Allaei H，Bianconi G，Marsili M.Scale-free networks with an exponent less than two[J].Physical Review E.2006，73（4）：46113.

[5]吳俊等.標(biāo)度指數(shù)不大于2的無標(biāo)度網(wǎng)絡(luò)的若干性質(zhì)[J].系統(tǒng)科學(xué)與數(shù)學(xué)，2008，7：6.

[6]王林等.復(fù)雜網(wǎng)絡(luò)的度分布研究[J].西北工業(yè)大學(xué)學(xué)報(bào)，2006，24（4）：05-409.

[7]王林等.關(guān)于無標(biāo)度網(wǎng)絡(luò)中Hub節(jié)點(diǎn)的研究[J].計(jì)算機(jī)應(yīng)用，2010，11：63.

[8]劉艷霞.基于代數(shù)圖論的復(fù)雜網(wǎng)絡(luò)的拓?fù)湫再|(zhì)和構(gòu)造方法研究[D].華南理工大學(xué).