傅秀軍 彭彩霞 段雪晴

(華南理工大學 物理與光電學院， 廣東 廣州 510640)

基于彭羅斯拼圖的部分隨機復雜網(wǎng)絡的統(tǒng)計性質*

傅秀軍 彭彩霞 段雪晴

(華南理工大學 物理與光電學院， 廣東 廣州 510640)

為擴展復雜網(wǎng)絡模型并探討網(wǎng)絡的新特征,研究了隨機復雜網(wǎng)絡的統(tǒng)計性質.在以兩種菱形為結構單元的彭羅斯拼圖的基礎上,增加頂點的隨機連接,其連接概率與頂點的類型有關,由此構造出部分隨機的復雜網(wǎng)絡.用解析和數(shù)值方法計算了網(wǎng)絡的主要特征參數(shù).結果表明：度分度、節(jié)點間平均距離和網(wǎng)絡集群系數(shù)與一般隨機網(wǎng)絡接近,但具體變化規(guī)律有所不同.由此可見,準周期復雜網(wǎng)絡既有一般網(wǎng)絡的共性,也有更為豐富的其他特征.

彭羅斯拼圖；準周期結構；復雜網(wǎng)絡；統(tǒng)計性質

復雜網(wǎng)絡的研究從傳統(tǒng)的規(guī)則圖形開始，發(fā)展出ER隨機網(wǎng)絡[1- 2]、WS小世界網(wǎng)絡[3- 4]、BA無標度網(wǎng)絡[5- 6]等各種模型，揭示了理論上和現(xiàn)實中豐富的網(wǎng)絡性質.1960 年，Erdos和Rényi為了描述通信和生命科學中的網(wǎng)絡，根據(jù)隨機圖理論提出了隨機拓撲模型來研究復雜網(wǎng)絡[1- 2]，發(fā)現(xiàn)了隨機網(wǎng)絡具有小集群系數(shù)、小平均距離的特征.之后的研究進一步證明了隨機網(wǎng)絡的度分布是泊松分布[7].然而實驗研究發(fā)現(xiàn)，自然界中許多復雜網(wǎng)絡的統(tǒng)計性質并不同于規(guī)則網(wǎng)絡和隨機網(wǎng)絡，真實網(wǎng)絡大都具有大的集群系數(shù)和小的平均距離等統(tǒng)計特征.因此，Watts等[3- 4]提出了描述現(xiàn)實網(wǎng)絡的小世界網(wǎng)絡模型.Barabási等[5- 6]提出了無標度網(wǎng)絡模型，其節(jié)點度服從冪函數(shù)分布[7- 9]，能反映許多真實網(wǎng)絡的性質.

復雜網(wǎng)絡在傳統(tǒng)的研究中均基于圖論，而初期的圖論專注于一些規(guī)則圖形，其中最具代表性的是二維周期結構，比如正方、三角和六角格子等，這與傳統(tǒng)的固體物理主要研究周期晶體相類似.然而自從1984年準晶體在實驗中被發(fā)現(xiàn)后[10]，對準周期結構的研究也引起了人們的廣泛關注[11- 15]，特別是彭羅斯拼圖(Penrose tiling)[16- 18].作為二維準晶的典型模型，其成功地描述了準晶結構，被廣泛地應用于準晶體物理性質的研究中.準周期結構與周期結構都是規(guī)則的，最大不同在于準周期結構在任何尺度上都不會簡單重復，且具有分形系統(tǒng)類似的自相似性.

將準周期結構應用于復雜網(wǎng)絡，探討其新的特性，是一項有意義的工作.文中從彭羅斯拼圖出發(fā)，構造復雜網(wǎng)絡，在原有的準周期結構上增加隨機連接，其連接概率取決于節(jié)點的類型，研究由此演化出的網(wǎng)絡的統(tǒng)計性質.

1 彭羅斯拼圖的基本性質及網(wǎng)絡模型的構造

彭羅斯拼圖是最早用來描述二維準晶體結構的幾何模型，它具有晶體點陣的長程有序性，但不具備平移對稱性[19].彭羅斯拼圖由兩種基本單元組成，一種是銳角為72°的胖菱形，另一種是銳角為36°的瘦菱形，如圖1(a)所示.在完整的彭羅斯拼圖中，頂點類型共有8種，按照de Bruijn的叫法，這8種頂點分別稱為S、 K、 Q、D、 J、 S3、 S4和S5[20],如圖1(b)所示.

圖1 由兩種菱形構成的彭羅斯拼圖及其8種頂點

Fig.1 Penrose tiling composed of two kinds of rhombi and its eight types of vertex

為了簡便，將這8種頂點分別記作a、b、c、d、e、f、g和 h.在無限大彭羅斯拼圖中，這8種頂點所占比例q(·)分別為[21]

(1)

構造隨機復雜網(wǎng)絡模型一般是先給出一定數(shù)目的節(jié)點，然后各節(jié)點之間以一定概率隨機連接，圖2是將10個節(jié)點隨機連接的示意圖.若直接將彭羅斯拼圖中的頂點看作網(wǎng)絡的節(jié)點，菱形邊看作連邊，則為準周期規(guī)則網(wǎng)絡.在已有菱形邊連接的基礎上，文中根據(jù)頂點類型引入隨機連接，則可構造出部分隨機的復雜網(wǎng)絡模型.基本構造思想是：同種類型頂點間的連接概率為p1，不同種類型頂點間的連接概率為p2，不考慮距離的限制.由此構造出的模型突破了原來彭羅斯拼圖的局域性限制，更接近于眾多的實際復雜網(wǎng)絡.

圖2 10個節(jié)點隨機連接構成的復雜網(wǎng)絡Fig.2 A complex network randomly connected by 10 nodes

2 網(wǎng)絡的度分布性質

由彭羅斯拼圖的頂點性質可知，若沒有額外的連接，網(wǎng)絡節(jié)點的度只有k=3,4,5,6,7這5種情況.對應于彭羅斯拼圖中頂點c和d的度為3，頂點b的度為4，頂點a、e和h的度為5，頂點g的度為6,頂點f度為7.因此，若不考慮邊界效應，規(guī)則彭羅斯網(wǎng)絡的度分布情況為

(2)

當增加了頂點的隨機連接，且同類間連接與不同類間連接概率p1與p2相差較大時，網(wǎng)絡的度分布會有明顯的變化.首先給出數(shù)值計算結果，如圖3所示，分別為p1=0.8、p2=0.2和p1=0.2、p2=0.8的情況.

圖3 網(wǎng)絡的度分布Fig.3 Degree distribution of the networks

研究發(fā)現(xiàn)，在以上兩種網(wǎng)絡中，度分布函數(shù)均出現(xiàn)5個峰值，圍繞每個峰值的度分布均類似于小世界隨機網(wǎng)絡.當p1?p2時，度平均值大的峰值較高；當p1?p2時，度平均值大的峰值較低.考慮到此網(wǎng)絡是按照8種頂點類型以一定規(guī)律連接而構造的，出現(xiàn)5個峰值的原因應該是某些構型的度簡并.為了探究這個問題，將各個類型頂點的度分開進行統(tǒng)計，結果發(fā)現(xiàn)，最小平均度的節(jié)點是來源于4種頂點(a、f、 g和 h)的貢獻，它們各自形成獨立的峰，位置基本上是重疊的，如圖4所示.第i類頂點的數(shù)目Ni與度分布的關系可分析如下：當p1?p2且Ni較大時，則大部分i類節(jié)點都相連，而i類與其他類型的節(jié)點連接概率小.所以節(jié)點i的度很大程度上由同種類型連接度決定，不同種類型節(jié)點連接度有一定的調節(jié)作用.這樣導致該類型度分布在較小的范圍內，且大于其他節(jié)點類型對應的的度分布概率.設Ni、Nj為任意兩種節(jié)點類型的數(shù)目，只有當Ni、Nj滿足一定條件時，兩種類型的度分布情況才相互獨立且無重疊.

圖4 按照不同頂點類型統(tǒng)計的度分布(對應于圖3(a)最小的峰值)

Fig.4 Degree distribution calculated for different types of vertexes(The figure corresponds to the lowest peak in Fig.3(a))

眾所周知，隨機網(wǎng)絡的度分布為泊松分布，該結論有嚴格的證明[7,22]：

(3)

(4)

(5)

網(wǎng)絡出現(xiàn)多個峰值時是p1較大、p2較小的情況.顯然當p2足夠小時，Q2與伯努利試驗的二項分布概率解析形式相同，故Q2滿足泊松分布的解析形式,即

(6)

(7)

(8)

由式(4)-(6)、(8)得到

(9)

若m∈M2，其度為k2，k2=k21+k22，同理可得到

(10)

同理可得到p(k3)、p(k4)、p(k5)、p(k6)、p(k7)和p(k8)的解析式，可寫成普遍形式：

(11)

其中t=1,2,3,4,5,6,7,8，當t取不同的值時，表示不同頂點類型的概率解析式.

同理，若是p1較大、p2較小的情況，則Q1近似泊松分布，網(wǎng)絡的度分布表達式可寫為

(12)

3 網(wǎng)絡節(jié)點的平均距離

網(wǎng)絡節(jié)點的平均距離()可以用來衡量網(wǎng)絡連通的難易程度，這里在計算平均距離時考慮邊權，權值為節(jié)點之間的幾何距離的整數(shù)倍.連接兩節(jié)點i和j的邊權由下式?jīng)Q定：ωij=(ki+kj)/2，其中ki和kj分別是原始彭羅斯拼圖網(wǎng)絡中節(jié)點i和節(jié)點j的度.研究發(fā)現(xiàn)，平均距離與連接同類節(jié)點的概率p1、連接異類節(jié)點的概率p2都呈遞減關系.但p1和p2的影響有所不同：當p1固定而p2增加時，平均距離的變化率比p2固定而p1增加時要大.圖5是p1或p2固定、另外一個概率變化時，平均距離的變化關系.

圖5 網(wǎng)絡平均距離與不同連接概率的關系

Fig.5 Average distance of the network versus the connecting probability

進一步研究平均距離與節(jié)點數(shù)目N的關系.圖6是對同類型節(jié)點連接概率為p1=0.8、不同類型節(jié)點連接概率為p2=0.2時演化出的網(wǎng)絡的計算結果.當N較小時，隨著N的增加平均距離呈現(xiàn)減小的趨勢；N在500～700左右時，隨著N的增大，平均距離出現(xiàn)上下明顯的波動；當N大于700時，隨著N的增加，平均距離沒有明顯的變化，近似接近于一個常數(shù)，這個常數(shù)約為5.25.這是由于，當網(wǎng)絡達到一定規(guī)模時，其邊界效應的影響已不明顯.

圖6 網(wǎng)絡的平均距離與網(wǎng)絡節(jié)點數(shù)目的關系

Fig.6 Relationship between the average distance and the total node number of the network

4 網(wǎng)絡的集群系數(shù)

復雜網(wǎng)絡的集群系數(shù)是用來描述復雜網(wǎng)絡中節(jié)點的鄰點也互為鄰點的比例情況，可用來衡量小集團結構的完美程度.文中關注的是集群系數(shù)與節(jié)點度的關系，該方面的研究顯示，大多情況下滿足冪函數(shù)關系[23- 26]：

C(k)∝k-α

(13)

α稱為層次指數(shù).普遍認為這個規(guī)律可說明網(wǎng)絡存在“層次結構”，可理解為網(wǎng)絡的節(jié)點聚合成許多小群體，而這些小群體又在某一個層次上聚合成較大的群體，形成一個個分層次的群體結構[2- 3,7].

當p1>p2時，從整體上看，節(jié)點度大的平均集群系數(shù)也大，但是在某個局部來看，卻正好相反，如圖7(a)所示.而對于p1

圖7 網(wǎng)絡的集群系數(shù)與節(jié)點度的關系

Fig.7 Relationship between cluster coefficient and degree of nodes

根據(jù)以上結果可以看出，對于p1=0.8、p2=0.2演化出的網(wǎng)絡，在不同的局部范圍內，度值k越大則α越大，整體的α取值范圍為0.020 8～0.515 7.而對于p1=0.2、p2=0.8演化出的網(wǎng)絡，度值k越大則α越小，整體的α取值范圍為-0.277 2～-0.029 1.后一種情況與這些實際網(wǎng)絡的結果有著明顯的區(qū)別.

5 結論

文中從彭羅斯拼圖出發(fā)，構造和研究了部分隨機復雜網(wǎng)絡模型的統(tǒng)計特征.首先按照彭羅斯拼圖中頂點的8種類型，分別以不同的概率連接同類和異類頂點而構成網(wǎng)絡.研究發(fā)現(xiàn)：其度分布為多個泊松分布或者近似泊松分布的疊加組合，其位置可通過調節(jié)兩個連接概率的值而改變；節(jié)點間的平均距離隨著節(jié)點總數(shù)N的增大出現(xiàn)一些波動，但當N足夠大時，平均距離接近于常數(shù)5.25；網(wǎng)絡的集群系數(shù)與節(jié)點度函數(shù)關系曲線為若干線段，滿足C(k)∝k-α的冪函數(shù)關系，層次指數(shù)α的取值范圍是不連續(xù)的，且有正值和負值.由此可知，作為二維準晶體模型的彭羅斯拼圖亦可用于復雜網(wǎng)絡的研究——一方面構造出新的網(wǎng)絡模型，發(fā)現(xiàn)一些相應網(wǎng)絡的特性，另一方面也可以通過復雜網(wǎng)絡的特性來進一步認識準周期結構的性質.

[1] ERDOS P,RéNYI A.On the evolution of random graphs [J].Publication of the Mathematical Institute of the Hungarian Academy Sciences,1960,5(1)：17- 60.

[2] ERDOS P,RéNYI A.On random graphs I [J].Publicationes Mathematicae-Debrecen,1959,6(1)：290- 297.

[3] WATTS D J,STROGATZ S H.Collective dynamics of small-world networks [J].Nature,1998,393(6684)：440- 442.

[4] BARRAT A,WEIGT M.On the properties of small-world networks models [J].European Physical Journal B,2000,13(3)：547- 560.

[7] ALBERT R,BARABSI A L.Statistical mechanics of complex networks [J].Reviews of Modern Physics,2002,74(1)：47- 97.

[8] FALOUTSOS M,FALOUTSOS P,FALOUTSOS C.On power-law relationships of the internet topology [J].ACM SIGCOMM Computer Communication Review,1999,29(4)：251- 262.

[9] EBEL H,MIELSCH L I,BORBHOLDT S.Scale-free topology of e-mail networks [J].Physical Review E,2002,66(3)：035103- 035106.

[10] SHECHTMAN D S,BLECH I,GRATIAS D.Metallic phase with long-range orientational order and no translational symmetry [J].Physical Review Letters,1984,53(20)：1951- 1954.

[11] BENDERSKY L.Quasicrystal with one-dimensional translational symmetry and a tenfold rotation axis [J].Physical Review Letters,1985,55(14)：1461- 1463.

[12] WANG N,CHEN H,KUO K H.Two-dimensional quasicrystal with eight-fold rotational symmetry [J].Physical Review Letters,1987,59(9)：1010- 1013.

[13] HE L X,LI X Z,ZHANG Z.One-dimensional quasicrystal in rapidly solidified alloys [J].Physical Review Letters,1988,61(9)：1116- 1118.

[14] YANG X B,LIU Y Y,FU X J.Transmission properties of light through the Fibonacci-class multilayers [J].Physical Review B,1999,59(7)：4545- 4548.

[15] ZENG X,UNGAR G,LIU Y.Supramolecular dendritic liquid quasicrystals [J].Nature,2004,428(6979)：157- 160.

[16] GUMMELT P.Penrose tilings as coverings of congruent decagons [J].Geometria Dedicata,1996,62(1)：1- 17.

[17] PENROSE R.The role of aesthetics in pure and applied mathematical research [J].The Institute of Mathematics and Its Applications Bulletin,1974,10(7)：266- 271.

[18] MACKAY A L.Crystallography and the Penrose pattern [J].Physica A:Statistical Mechanics and Its Applications,1982,144(1)：609- 613.

[19] 劉有延,傅秀軍.準晶體 [M].上海：上?？萍冀逃霭嫔?1999:3.

[20] DE BRUIJN N G.Algebraic theory of Penrose’s non-perio-dic tilings of the planeⅠ&Ⅱ [J].Indagationes Mathe-maticae,1981,84(1)：39- 66.

[21] 傅秀軍.準晶體覆蓋模型的結構和電子性質 [D].廣州：華南理工大學,2004.

[22] 何大韌,劉宗華,汪秉宏.復雜系統(tǒng)與復雜網(wǎng)絡 [M].北京：高等教育出版社,2009:126- 131.

[23] XIAO W K,REN J,QI F.Empirical study on clique-degree distribution of networks [J].Physical Review E,2007,76(3)：037102- 037105.

[24] ALEXEI V,ROMUALDO P S,ALESSANDRO V.Large-scale topological and dynamical properties of the internet [J].Physical Review E,2002,65(6)：066130- 066141.

[25] BARABASI A L,OLTVAI Z N.Network biology：understanding the cell’s functional organization [J].Nature Reviews Genetics,2004,5(2)：101- 113.

[26] YOOK S H,OLTVAI Z N,BARABASI A L.Functional and topological characterization of protein interaction networks [J].Proteomics,2004,4(4)：928- 942.

Statistical Properties of Partially Random Complex Network Based on Penrose Tiling

FU Xiu-jun PENG Cai-xia DUAN Xue-qing

(School of Physics and Optoelectronics, South China University of Technology, Guangzhou 510640, Guangdong, China)

In order to extend the models and exploit new features for complex networks,the statistical properties of random complex networks are explored.In the investigation,first,on the basis of the Penrose tiling composed of two kinds of rhombus,random connections of the vertex are added to construct a partially random complex network in which the connecting probability depends on the vertex type.Then,the main characteristic parameters of the network are calculated by using analytical and numerical methods.It is found that the degree distribution,the ave-rage inter-node distance and the cluster coefficient of the partially random complex network are all close to those of general random networks but obey different variation laws,which means that the proposed quasi-periodic complex network possesses not only the common properties of general networks but also abundant specific features.

Penrose tiling; quasi-periodic structure; complex network; statistical property

2016- 01- 18

國家自然科學基金資助項目(11674102) Foundation item: Supported by the National Natural Science Foundation of China(11674102)

傅秀軍(1964-)，男，博士，教授，主要從事準晶體研究.E-mail：phxjfu@scut.edu.cn

1000- 565X(2017)06- 0001- 07

O 414.2

10.3969/j.issn.1000-565X.2017.06.001