自相似復雜網絡的分形特征分析

摘要:針對自相似復雜網絡的研究進展情況，闡述了自相似復雜網絡的形成過程，討論了容量維數和信息維數這兩類分形維數的優缺點和應用，并對復雜網絡的平均最短路距離、群集系數和頂點度分布等三個統計屬性進行詳細介紹，從而揭示自相似復雜網絡的分形特征。

關鍵詞:復雜網絡;自相似;容量維數;信息維數;分形特征

中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2010)21-5959-03

An Analysis of the Fractal Feature of Self-similar Complex Networks

MAO Ke-hong，LI Guang-song

(Department of Information Engineering， Guangdong Textile Polytechnic， Foshan 528041， China)

Abstract: In view of research progress of self-similar complex networks， this paper describes the formation process of self-similar complex networks， discusses the advantages and disadvantages and applications of two types of fractal dimensions which are volume dimension and information dimension， and described in detail the average shortest distance ， the cluster coefficient and the vertex degree distribution to reveal the fractal feature of self-similar complex networks.

Key words: complex networks; self-similarity; volume dimension; information dimension; fractal feature

1 自相似復雜網絡的研究進展討論

Erdos和Renyi在1960年應用隨機圖理論提出了隨機拓撲模型來研究復雜網絡。近年來許多研究復雜網絡理論的學者發現:在現實的復雜網絡中得到的許多實驗數據和結果與隨機拓撲模型并不符合，因此需要建立新的網絡模型來描述實際網絡。Watts和Strgatz于1998年提出了描述現實網絡的小世界模型，他們在文章中描述了現實網絡所具有的大聚簇和短平均路徑距離的特征。然而，現實世界中的復雜網絡，在很多情況下其實有極少數的節點擁有大量的連接，而許多節點卻只有少量連接的特點，這些特點同樣無法用隨機拓撲模型來解釋。不久后，Barabasi和Albert提出了無尺度模型，他們認為增長性和擇優連接這兩個基本原理決定了互聯網等現實復雜網絡具有無尺度性。盡管小世界模型與無尺度模型刻畫了復雜網絡的基本特征，但都是基于對現實復雜網絡進行理想化的前提下得出的結論。然而，對于復雜網絡的自相似分析特征研究則是利用網絡節點之間的互動特性來解釋網絡的微觀演化過程，如C.M.Song與S.Havlin等人利用重構化理論來揭示復雜網絡的自相似分形特征 ，R.Guimera與L.Danon在研究中利用郵件系統來揭示社區結構的自相似分形特征。以上的研究方法并不能從復雜網絡的動態增長性方面揭示復雜網絡的自相似分形特征。最近，陶少華等研究者在文獻[7]-[8]中分別研究了基于信息維數與容量維數的復雜網絡的自相似性，建立了基于自相似分型特征的網絡演化模型，并且說明動態增長的復雜網絡的確是自相似的。本文闡述了自相似復雜網絡的形成過程，討論其分形維數和統計屬性，從而揭示自相似復雜網絡的分型特征，有助于更清晰地了解自相似復雜網絡的體系結構。

2 自相似性復雜網絡的形成

在分形幾何的研究中，自相似是相似中的一種特殊情況，它是指系統的部分和整體之間具有某種相似性，這種相似性不是兩個無關事物間的偶然近似，而是在系統演化中必然出現并始終保持的 。基于這一事實，陶少華等在文獻[8]中提出了復雜網絡的自相似原理，即復雜網絡在演化的過程中將始終保持自己特征狀態的相對穩定性，從而使它的整體和部分、部分與部分之間呈現出某種相似性。自相似網絡起初是通過節點之間的關系來傳遞信息而形成的。首先，每個節點能夠自動獲得本身的信息，并且節點之間有一種相互作用，能夠彼此建立聯系并傳遞信息。若傳遞的信息具有相似性或者相同之處，則建立連接并同屬一類。在現實網絡中可以描述為一下過程:

1) 節點m對自己有認知，獲得關于自己的信息，假設它有(n1，n2，…，nk)個特征，并且節點mi向其周圍的其它節點傳遞信息，若節點彼此之間傳遞的信息具有相同之處或相似性，則建立連接。

2) 若網絡中加入新的節點qi(q1，q2，…，qk)，同時新節點與老節點彼此向對方傳遞信息，若新節點與網絡中任何一個老節點有相似性，則建立連接。

3) 若節點m的n1，n2，…，nk個特征與節點qi(q1，q2，…，qk)有相似的信息并且建立連接，則有:

即節點qk與m的相似信息都屬于m的自身特征。

此時，我們稱節點之間具有以下性質:

1) 傳遞性:若m～q且q～s，則m～s;

2) 對稱性:若m～q，則q～m;

3) 反身性:m～m。

其中，“～”表示相似性。

綜上所述，節點m具有的特征是形成相似性的基礎。在t時刻節點m與q相連，經過t時刻之后，假設演化為具有100個節點的局部網絡S1。在S1的基礎上繼續有新節點與老節點相連接，形成具有1000個節點的局部網絡S2，則S1與S2相似。隨后形成具有10000個節點的局部網絡S3，直至最終形成網絡F。則S2與S3相似，S3與F相似，因此整個網絡是自相似的。于是陶少華等人利用分形幾何中刻畫自相似集合的數學方法 得到了如下定理來刻畫自相似網絡:

定理1 S1，S2，…，Sm是子網絡集合， 若存在數c滿足條件0

S1～c1S2

S2～c2S3

…

Sm～ciF

則稱Sm是相似的，0

3 自相似網絡的分形維數

3.1 自相似復雜網絡的容量維數

由于分形具有形態的不規則性，不能用傳統的歐氏幾何語言來描述，一般集合的分形維數大于其拓撲維數，因此分形維數一般為非整數，對于它的估算，是目前自相似復雜網絡研究中的一個重要問題。而在所有不同定義的分形維數中，其中計盒維數也稱為容量維數(具體定義請參見文獻[6])則是應用得最多的。陶少華等在文獻[8]的研究中，應用容量維數來描述復雜網絡的自相似分形特征，給出了計算自相似復雜網絡的容量維數的具體方法，并用此方法分析了復雜網絡在不同階段的容量維數，得出維數相同(或相近)時，復雜網絡具有自相似分形特征。因此，我們在計算自相似復雜網絡或者自相似圖形的分形維數時，采用圓片(或方塊)去填充(或覆蓋)被計算的對象，統計覆蓋所需的方塊數來計算其分形維數。如此方法計算的分形維數我們稱為容量維數:若用長度為λ尺子去測長度為L的線段，L與λ之比為N。其中N的大小與λ的長短有關，λ越小，則N越大:。對于Dc維的物體有:

。

取對數可得自相似復雜網絡的容量維數:。

3.2 自相似性復雜網絡的信息維數

在自相似復雜網絡的分形維數計算中.最常用的是容量維數。然而容量維數的計算只考慮了覆蓋整個網絡的盒子數，而沒有考慮在一個盒子內所包含的節點的個數。顯然，應用容量維數揭示復雜網絡的自相似分形特征有一定的局限性。鑒于此，陶少華等人在文獻[7]中，對自相似容量維數的算法進行了以下改進:

1) 對每個覆蓋的盒子按照填充程度(即所包含的節點多少)進行逐個編號;

2) 統計出自相似分形結構落入第i個盒子的概率pi(λ):

由上式推導出信息公式為:

。

于是我們可以得到自相似復雜網絡的信息維數公式為:

從而可以計算信息維數用以研究復雜網絡的自相似分形特征。

在分形幾何和自相似復雜網絡理論的研究中，容量維數和信息維數是最常用的分形維數，其優點是因其算法簡單、快速、估算精確。因此在驗證自相似復雜網絡的分析特征時，得到研究者的廣泛采用。

4 量化自相似復雜網絡分形維數的三個統計屬性

平均最短路徑距離(l)、群集系數(c)、頂點度分布(p(k))是復雜網絡的三個統計屬性，許多學者在研究中均采用次三個統計屬性來量化分形維數，從而揭示自相似復雜網絡的演化過程。下面我們簡單介紹它們的定義:

假設一個包含n個節點的網絡，我們稱l是復雜網絡中節點之間的平均最短路徑距離:

其中，dij是從節點i到節點j的最短距離。

群集系數是自相似復雜網絡的另一個重要的統計屬性，它刻畫了自相似復雜網絡的小聚集形態。群集系數可用以下公式來量化:，其中Ci為節點i的局部群集系數(i=1，2，…，n)。而Ci的計算式子如下:。對于此公式的理解是，網絡節點i，它通過ki條邊與其它ki個網絡節點相連接。如果這ki個鄰居是群集的一部分，則在它們之間有ki(ki-1/2)條邊相連接。于是，ki個鄰居之間實際有的邊數Ei與總邊數ki(ki-1/2)之比就給出了節點i的局部聚集系數Ci。

頂點度分布用分布函數p(k)來表示，即網絡中度數為k的頂點個數占頂點總個數的比例。

量化自相似復雜網絡的分形維數過程可以描述如下:當形成一個小的局部復雜網絡時，我們就來計算它的平均最短路徑距離l1，群集系數c1與頂點度分布p(k1)。繼續增加節點形成大的局部復雜網絡時，計算它的平均最短距離l2，群集系數C2與頂點度分布p(k2)。再繼續增加節點形成一個更大的局部復雜網絡時，同樣計算它的平均最短距離l3，群集系數C3與頂點度分布p(k3)。然后以l1為方塊去覆蓋整個復雜網絡的平均路徑長度l，計算需要l1的塊數N(l1)。于是，可以得到自相似容量維數為。然后以l1與l2去覆蓋整個復雜網絡的平均路徑長度，計算需要多少塊l2與l3，分別計算出它們的自相似容量維數，Dc2和Dc3。如果Dc1，Dc2與Dc3是取相同值或相近值，則說明此復雜網絡是自相似的。

同理，利用局部復雜網絡的群集系數與頂點度分布作為方塊來覆蓋整體復雜網絡，也可以分別計算出自相似復雜網絡的容量維數。因此，我們可以從自相似復雜網絡的三個統計屬性來量化其分形維數，并加以分析驗證復雜網絡確實具有自相似分形特征。

5 結束語

自相似復雜網絡的分形特征是基于分形幾何理論與復雜網絡理論結合的研究結果，引起了眾多研究者的關注，而基于分形維數和平均最短路徑距離、群集系數、頂點度分布等統計屬性來揭示自相似復雜網絡的分形特征是非常重要的研究方法。因此，本文分析了自相似復雜網絡的形成過程以及其分形維數、統計屬性，有助于人們了解復雜網絡的分形特征的體系結構。

參考文獻:

[1] Erdos Prey A. On the evolution of Random Graphs [J].Publ Math Inst Hung Acad Sci， 1960， 5:17-61.

[2] Watts D J， Strogatz S H. Collective Dynamics of \"Small-world\" Networks [J].Nature， 1998， 393:440-442.

[3] Barabasi A L， Albertr. Emergence of Scaling in Random Networks [J].Science，1999，286(15): 509-5l2.

[4] Song Chao-ming， Havlin S， Makse H A. Complex networks are self-similar [J]. Nature， 2004，433.

[5] Guimera R， Danon L， Dlaz-Guilera A，et a1.Self-similar community structure in a network of human interactions [J]. Physical Review E， 2003，68.

[6] Falconer K J. Fractal Geometry: Mathematical Foundations and Applications [M]. New York: John Wiley and Sons， 1990.

[7] 陶少華.基于信息維數的復雜網絡自相似性研究[J].計算機工程與應用， 2007， 43(15):108-110.

[8] 陶少華.基于容量維數的復雜網絡自相似性研究[J].計算機工程， 2008， 34(2):175-177.

[9] 方愛麗，孫麗瑤.復雜網絡的分形特征及其實證研究[J].計算機工程， 2009， 45(20):52-56.

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文