馬 飛，姚 兵

(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 甘肅 蘭州 730070 )

一類作為網(wǎng)絡(luò)模型的可平面無(wú)標(biāo)度圖

馬 飛，姚 兵*

(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 甘肅 蘭州 730070 )

無(wú)標(biāo)度特性普遍存在于大量的實(shí)際網(wǎng)絡(luò)和人造網(wǎng)絡(luò)中．為了更好地研究這類無(wú)標(biāo)度網(wǎng)絡(luò)模型的拓?fù)湫再|(zhì)和內(nèi)在動(dòng)力學(xué)，大量的模型被建立，如隨機(jī)網(wǎng)絡(luò)模型和確定性網(wǎng)絡(luò)模型．鑒于以往確定性模型中的無(wú)標(biāo)度指數(shù)都是唯一不變的常數(shù)，定義了一類具有廣義自相似性的增長(zhǎng)網(wǎng)絡(luò)模型，分析了它的一些拓?fù)湫再|(zhì):平均度、聚集系數(shù)、直徑、度分布、最多葉子生成樹(shù)．得出該模型具有無(wú)標(biāo)度特性和小世界效應(yīng)，并且可以通過(guò)調(diào)整相應(yīng)的參數(shù)來(lái)獲得豐富的無(wú)標(biāo)度指數(shù)．

無(wú)標(biāo)度圖；網(wǎng)絡(luò)模型；小世界效應(yīng)

0 引 言

為了認(rèn)識(shí)自然、改造自然，學(xué)者們?cè)诿鎸?duì)大到天體，小到人類及其他動(dòng)物界，甚至微生物界之間存在的種種聯(lián)系時(shí)，形象生動(dòng)地提出了復(fù)雜網(wǎng)絡(luò)這一概念，隨之產(chǎn)生了大量的復(fù)雜網(wǎng)絡(luò)模型．Watts等[1]提出了小世界網(wǎng)絡(luò)模型，Barabsi等[2]首次提出了無(wú)標(biāo)度網(wǎng)絡(luò)模型．在此之后的十幾年，學(xué)術(shù)界對(duì)復(fù)雜網(wǎng)絡(luò)的研究熱潮不衰反增，吸引了眾多學(xué)者的不斷涌入，使得復(fù)雜網(wǎng)絡(luò)的研究不論縱向深入還是橫向拓展都取得了豐碩的成果．現(xiàn)今復(fù)雜網(wǎng)絡(luò)研究涵蓋了諸多學(xué)科領(lǐng)域，如物理、數(shù)學(xué)、計(jì)算機(jī)科學(xué)、化學(xué)、生物學(xué)、經(jīng)濟(jì)學(xué)等，在研究各領(lǐng)域中不同的研究對(duì)象時(shí)，產(chǎn)生了大量的網(wǎng)絡(luò)模型，如物聯(lián)網(wǎng)、地震網(wǎng)、食物鏈網(wǎng)、電力網(wǎng)、細(xì)胞新陳代謝網(wǎng)、神經(jīng)信號(hào)傳送網(wǎng)、股市等[3-10]．

對(duì)真實(shí)網(wǎng)絡(luò)進(jìn)行了海量的研究之后，學(xué)者們不約而同地闡釋了眾多網(wǎng)絡(luò)具有的拓?fù)涔残裕?1)小的直徑和平均距離；(2)高的聚集系數(shù)；(3)服從冪率分布(無(wú)標(biāo)度性)；(4)自相似性；(5)層次結(jié)構(gòu)．從而為復(fù)雜網(wǎng)絡(luò)的進(jìn)一步研究指明了方向．為了認(rèn)識(shí)、理解復(fù)雜網(wǎng)絡(luò)，學(xué)者們通過(guò)循環(huán)迭代的方法構(gòu)造新的隨機(jī)模型，討論它的拓?fù)湫再|(zhì)．

1 模型的迭代及其拓?fù)湫再|(zhì)

1.1 模型的迭代

在本文的網(wǎng)絡(luò)模型M(t)中，用頂點(diǎn)刻畫(huà)研究中的每個(gè)實(shí)體對(duì)象，頂點(diǎn)間的連邊表示實(shí)體對(duì)象間的相互聯(lián)系，L(t)表示M(t)的最多葉子生成樹(shù)的葉子數(shù)，文中未定義的術(shù)語(yǔ)和符號(hào)均采用圖論中標(biāo)準(zhǔn)的術(shù)語(yǔ)和符號(hào)[12]．模型M(t)可以通過(guò)迭代的方法得到，如下：

(1)當(dāng)t=0時(shí)，模型M(0)由一條活動(dòng)邊和與之關(guān)聯(lián)的兩個(gè)頂點(diǎn)組成．

(2)當(dāng)t>0時(shí)，模型M(t)可以通過(guò)對(duì)模型M(t-1) 中的活動(dòng)邊實(shí)施平行加邊運(yùn)算獲得．這里的活動(dòng)邊是指模型M(t-1)在t-1時(shí)刻新產(chǎn)生的邊，每條活動(dòng)邊至少含有1個(gè)二度頂點(diǎn)，不妨稱在t-1時(shí)刻之前的邊為休眠邊．

(1)

(2)

通過(guò)上述迭代構(gòu)造出的模型M(t)是可平面的，如果加邊參數(shù)d同時(shí)滿足d=m+n，m表示一條活動(dòng)邊上方加邊的條數(shù)，n表示一條活動(dòng)邊下方加邊的條數(shù)，這樣便可以得到一族可平面的廣義自相似網(wǎng)絡(luò)模型．隨著時(shí)間的推移，這一族網(wǎng)絡(luò)模型將是相當(dāng)復(fù)雜的[8]．圖1為模型M(t)在t=0，1，2，d=m+n=2(m=n=1)的拓?fù)浣Y(jié)構(gòu).

圖1 模型M(t)拓?fù)浣Y(jié)構(gòu)Fig.1 Model M(t) topological structures

1.2 模型的拓?fù)湫再|(zhì)

1.2.1 平均度 網(wǎng)絡(luò)的平均度〈k〉為邊個(gè)數(shù)的2倍與頂點(diǎn)個(gè)數(shù)之比，即

(3)

隨著時(shí)間的推移，模型M(t)的頂點(diǎn)和邊數(shù)目越來(lái)越大，不難發(fā)現(xiàn)，當(dāng)t→∞時(shí)，整個(gè)模型M(t)的平均度趨于一固定常數(shù)3，即

(4)

位于活動(dòng)邊xy上下不同位置的新頂點(diǎn)和新邊會(huì)影響以后進(jìn)入網(wǎng)絡(luò)的新頂點(diǎn)和新邊的位置，從而導(dǎo)致模型M(t)的拓?fù)浣Y(jié)構(gòu)的復(fù)雜性(圖2)．

圖2 模型M(t)在t=0,1,d=m+n=6的拓?fù)浣Y(jié)構(gòu)Fig.2 Model M(t) topological structures at t=0, 1, d=m+n=6

1.2.3 直徑 直徑作為研究復(fù)雜網(wǎng)絡(luò)的另一個(gè)重要參數(shù)，往往對(duì)網(wǎng)絡(luò)的隨機(jī)游走研究起到一定的作用，然而很多復(fù)雜網(wǎng)絡(luò)的直徑并不是輕松獲得的，一般來(lái)說(shuō)，獲得一些網(wǎng)絡(luò)直徑的精確解是相當(dāng)困難的．模型M(t)基于對(duì)稱迭代構(gòu)造，便于獲得直徑的精確解．分析得知，模型M(t)中任意兩頂點(diǎn)間的距離中只有在t時(shí)刻新加入的對(duì)稱頂點(diǎn)間的距離最長(zhǎng)，根據(jù)直徑的定義D(t)=max{dij|i，j∈V(t)}，其中dij表示頂點(diǎn)i與頂點(diǎn)j的距離，進(jìn)一步分析得知，M(t)中的直徑D(t)可以表示為：頂點(diǎn)i先走到與之相鄰的在t時(shí)刻休眠邊的頂點(diǎn)it，頂點(diǎn)j先走到與之相鄰的在t時(shí)刻休眠邊的頂點(diǎn)jt，直徑D(t)=1+ditjt+1．根據(jù)模型的對(duì)稱性知，頂點(diǎn)it與頂點(diǎn)jt的距離ditjt是模型M(t-1) 的直徑，故D(t)=D(t-1)+2，t≥2，因D(1)=1，M(t)的直徑為

D(t)=3+2(t-1)

(5)

1.2.4 度分布 度分布是一個(gè)刻畫(huà)復(fù)雜網(wǎng)絡(luò)是否具有無(wú)標(biāo)度性質(zhì)的拓?fù)鋮?shù)．對(duì)模型M(t)中頂點(diǎn)的度構(gòu)成的度譜分析可知，這是一些離散的數(shù)據(jù)，為了獲得模型M(t)的度分布，采取累積度分布的計(jì)算方法[4]：

(6)

其中V(t，k′)表示在t時(shí)刻M(t)中度為k′的頂點(diǎn)集合，下面做詳細(xì)的論證．在t=0時(shí)，M(0)有兩個(gè)度為1的頂點(diǎn)，之后的每一次迭代中新加入的頂點(diǎn)的度都是2．為了簡(jiǎn)化敘述，采用符號(hào)k(i，t)，kg(i，t)，kp(i，t)表示在t≥ti時(shí)與頂點(diǎn)i相關(guān)聯(lián)的邊的數(shù)目、活動(dòng)邊的數(shù)目、休眠邊的數(shù)目．顯然有k(i，t)=kg(i，t)+kp(i，t)．鑒于模型M(t)的構(gòu)造，可以得到：當(dāng)i=0時(shí)，模型M(t)中的兩個(gè)屬于M(0)的初始頂點(diǎn)的度為

(7)

在ti≥1時(shí)，

kp(i，t+1)=kg(i，t)+kp(i，t)，kg(i，ti)=2

kg(i，t+1)=2dkg(i，t)，kp(i，ti)=0

(8)

由式(8)計(jì)算得

(9)

(10)

在ti時(shí)刻，考察度為k的頂點(diǎn)的度分布，由式(10)可得

(11)

聯(lián)立式(6)、(7)、(11)，得到網(wǎng)絡(luò)模型M(t)的累積度分布為

(12)

當(dāng)t很大時(shí)，由式(11)知，式(12)可簡(jiǎn)化為

當(dāng)k?1時(shí)，將獲得如下表達(dá)式：

(14)

(15)

2 結(jié) 語(yǔ)

理論分析表明，本文建立的模型具有無(wú)標(biāo)度特性和小世界效應(yīng)．在最近的生物網(wǎng)絡(luò)研究中，有學(xué)者發(fā)現(xiàn)了一類特殊的現(xiàn)象：網(wǎng)絡(luò)中每個(gè)頂點(diǎn)的鄰居頂點(diǎn)集中任何頂點(diǎn)彼此之間沒(méi)有邊相連(聚集系數(shù)〈c〉=0)[8,13]，而且這樣的網(wǎng)絡(luò)具有較強(qiáng)的魯棒性．在實(shí)際生活中，可以提高對(duì)蓄意攻擊的預(yù)防性，加強(qiáng)網(wǎng)絡(luò)的安全性．本文的模型正好吻合這一現(xiàn)象，有力推動(dòng)對(duì)該類特殊網(wǎng)絡(luò)的進(jìn)一步研究，這也提醒人們?cè)诮窈蟮难芯恐懈雨P(guān)注此類復(fù)雜網(wǎng)絡(luò)．復(fù)雜網(wǎng)絡(luò)的研究正在如火如荼地進(jìn)行著，研究成果層出不窮，研究方法也在日趨完善，日后將關(guān)注網(wǎng)絡(luò)研究中的熵與隨機(jī)游走等問(wèn)題[8,10]．

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

[3]WATTS D J. Small Worlds:The Dynamics of Networks between Order and Randomness [M]. New Jersey:Princeton University Press, 1999.

[4]ZHANG Zhongzhi, ZHOU Shuigeng, FANG Lujun,etal. Maximal planar scale-free Sierpinski networks with small-world effect and power-law strength-degree correlation [J]. EPL, 2007, 79(3):417-429.

[5]YAO Bing, YAO Ming, CHEN Xiangen,etal. Research on edge-growing models related with scale-free small-world networks [J]. Applied Mechanics and Materials, 2014(513-517):2444-2448.

[6]ZHANG Z Z, WU B, COMELLAS F. The number of spanning trees in Apollonian networks [J]. Discrete Applied Mathematics, 2014, 169:206-213.

[7]TEUFL E, WAGNER S. Resistance scaling and the number of spanning trees in self-similar lattices [J]. Journal of Statistical Physics, 2011, 142(4):879-897.

[8]MIRALLES A, COMELLAS F, CHEN L C,etal. Planar unclustered scale-free graphs as models for technological and biological networks [J]. Physica A:Statistical Mechanics and its Applications, 2010, 389(9):1955-1964.

[9]SONG C M, KOREN T, WANG P,etal. Modelling the scaling properties of human mobility [J]. Nature Physics, 2010, 6(10):818-823.

[10]YAN G, TSEKENIS G, BARZEL B,etal. Spectrum of controlling and observing complex networks [J]. Nature Physics, 2015, 11(9):779-786.

[11]DEL GENIO C I, GROSS T, BASSLER K E. All scale-free networks are sparse [J]. Physical Review Letters, 2011, 107(17):178701.

[12]BONDY J A, MURTY U S R. Graph Theory with Applications [M]. London:The Macmillan Press Ltd., 1976.

[13]COMELLAS F, ZHANG Zhongzhi, CHEN Lichao. Self-similar non-clustered planar graphs as models for complex networks[J]. Journal of Physics A Mathematical & Theoretical, 2009, 42(4):461-471.

A planar scale-free graphs as network models

MA Fei,YAO Bing*

(College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China )

The scale-free feature is popular in amounts of real-life and artificial complex networks. In order to study the topological properties and intrinsic dynamics of this kind of scale-free network model, lots of models are presented, such as random network models and deterministic ones. Considering that the scale-free exponent is an unique constant in those previous deterministic models, a generalized self-similarity growing network model is proposed. Its topological properties, including average degree, clustering coefficient, diameter, degree distribution, maximum-leaf-spanning-tree are analyzed. It shows that this model has scale-free characteristics and small-world effects, and the scale-free exponent can be enriched by adjusting corresponding parameters.

scale-free graph; network model; small-world effect

1000-8608(2017)04-0436-05

2016-09-28；

2017-03-13．

國(guó)家自然科學(xué)基金資助項(xiàng)目(61163054，61662066，61363060).

馬 飛(1992-)，男，碩士生，E-mail：mafei123987@163.com；姚 兵*(1956-)，男，教授，E-mail：yybb918@163.com.

O157.5

A

10.7511/dllgxb201704016