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

傅秀軍 彭彩霞 段雪晴

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

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

傅秀軍 彭彩霞 段雪晴

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

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

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

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

復(fù)雜網(wǎng)絡(luò)在傳統(tǒng)的研究中均基于圖論，而初期的圖論專注于一些規(guī)則圖形，其中最具代表性的是二維周期結(jié)構(gòu)，比如正方、三角和六角格子等，這與傳統(tǒng)的固體物理主要研究周期晶體相類似.然而自從1984年準(zhǔn)晶體在實(shí)驗(yà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ò)，探討其新的特性，是一項(xiàng)有意義的工作.文中從彭羅斯拼圖出發(fā)，構(gòu)造復(fù)雜網(wǎng)絡(luò)，在原有的準(zhǔn)周期結(jié)構(gòu)上增加隨機(jī)連接，其連接概率取決于節(jié)點(diǎn)的類型，研究由此演化出的網(wǎng)絡(luò)的統(tǒng)計(jì)性質(zhì).

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

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

圖1 由兩種菱形構(gòu)成的彭羅斯拼圖及其8種頂點(diǎn)

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

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

(1)

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

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

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

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

(2)

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

圖4 按照不同頂點(diǎn)類型統(tǒng)計(jì)的度分布(對應(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))

眾所周知，隨機(jī)網(wǎng)絡(luò)的度分布為泊松分布，該結(jié)論有嚴(yán)格的證明[7,22]：

(3)

(4)

(5)

網(wǎng)絡(luò)出現(xiàn)多個(gè)峰值時(shí)是p1較大、p2較小的情況.顯然當(dāng)p2足夠小時(shí)，Q2與伯努利試驗(yàn)的二項(xiàng)分布概率解析形式相同，故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取不同的值時(shí)，表示不同頂點(diǎn)類型的概率解析式.

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

(12)

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

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

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

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

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

圖6 網(wǎng)絡(luò)的平均距離與網(wǎng)絡(luò)節(jié)點(diǎn)數(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é)點(diǎn)的鄰點(diǎn)也互為鄰點(diǎn)的比例情況，可用來衡量小集團(tuán)結(jié)構(gòu)的完美程度.文中關(guān)注的是集群系數(shù)與節(jié)點(diǎn)度的關(guān)系，該方面的研究顯示，大多情況下滿足冪函數(shù)關(guān)系[23- 26]：

C(k)∝k-α

(13)

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

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

圖7 網(wǎng)絡(luò)的集群系數(shù)與節(jié)點(diǎn)度的關(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.后一種情況與這些實(shí)際網(wǎng)絡(luò)的結(jié)果有著明顯的區(qū)別.

5 結(jié)論

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