一類度互質的無標度網絡研究

蘇志忠+劉煥龍+孔祥泉

摘 要： 本文提出了一類度互質的嚴格無標度網絡模型，刻畫出其節點分布規律，并基于這種模型進一步分析了冪指數大于2與小于等于2時無標度網絡拓撲性質的區別。

關鍵詞： 冪指數 無標度網絡 平均度

一、引言

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

因為只有冪指數為整數時才能保證度及其相應的節點數都為整數。為了更好地研究無標度網絡的拓撲性質，本文提出了一類度互質的無標度網絡模型，這種嚴格的無標度網絡模型中的度之間只需滿足互質條件，且冪指數的數值可以取任意有意義的有理數。

從表1和圖2，能夠進一步地認識到無標度網絡在γ取不同值時，呈現出截然不同的性質。當γ>2時，網絡平均度隨著網絡規模的增大基本不變，邊數緩慢增加，網絡相對比較稀疏。而當1≤γ≤2時，網絡平均度隨著網絡規模的增大呈迅速上漲趨勢，也就是說，最小度節點所占的比例越來越小，最大度節點或者度數較大的節點所占的比例增大，網絡的邊數相對于節點快速增大，網絡越來越稠密。

四、結語

基于前人的結果，本文提出了一類度互質的無標度網絡模型，通過研究它的度分布特征，進一步驗證了冪指數大于2和冪指數不大于2的無標度網絡的拓撲性質，對進一步研究無標度網絡的拓撲性質具有一定的作用。下一步，我們力爭找到這類網絡的實際應用，并基于這種網絡模型進一步研究冪指數在不同范圍時拓撲性質及路由算法。

參考文獻：

[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]吳俊等.標度指數不大于2的無標度網絡的若干性質[J].系統科學與數學，2008，7：6.

[6]王林等.復雜網絡的度分布研究[J].西北工業大學學報，2006，24（4）：05-409.

[7]王林等.關于無標度網絡中Hub節點的研究[J].計算機應用，2010，11：63.

[8]劉艷霞.基于代數圖論的復雜網絡的拓撲性質和構造方法研究[D].華南理工大學.