傅秀軍 彭彩霞 段雪晴

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

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

傅秀軍 彭彩霞 段雪晴

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

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

彭羅斯拼圖；準(zhǔn)周期結(jié)構(gòu)；復(fù)雜網(wǎng)絡(luò)；統(tǒng)計性質(zhì)

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

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

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

1 彭羅斯拼圖的基本性質(zhì)及網(wǎng)絡(luò)模型的構(gòu)造

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

圖1 由兩種菱形構(gòu)成的彭羅斯拼圖及其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)

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

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

2 網(wǎng)絡(luò)的度分布性質(zhì)

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

(2)

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

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

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

圖4 按照不同頂點類型統(tǒng)計的度分布(對應(yī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)絡(luò)的度分布為泊松分布，該結(jié)論有嚴(yán)格的證明[7,22]：

(3)

(4)

(5)

網(wǎng)絡(luò)出現(xiàn)多個峰值時是p1較大、p2較小的情況.顯然當(dāng)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，當(dāng)t取不同的值時，表示不同頂點類型的概率解析式.

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

(12)

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

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

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

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

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

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

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

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

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

C(k)∝k-α

(13)

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

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

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

Fig.7 Relationship between cluster coefficient and degree of nodes

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

5 結(jié)論

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

[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] 劉有延,傅秀軍.準(zhǔn)晶體 [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] 傅秀軍.準(zhǔn)晶體覆蓋模型的結(jié)構(gòu)和電子性質(zhì) [D].廣州：華南理工大學(xué),2004.

[22] 何大韌,劉宗華,汪秉宏.復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò) [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

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

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

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

O 414.2

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