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

馬 飛，姚 兵

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

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

馬 飛，姚 兵*

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

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

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

0 引 言

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

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

1 模型的迭代及其拓撲性質(zhì)

1.1 模型的迭代

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

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

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

(1)

(2)

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

圖1 模型M(t)拓撲結(jié)構(gòu)Fig.1 Model M(t) topological structures

1.2 模型的拓撲性質(zhì)

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

(3)

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

(4)

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

圖2 模型M(t)在t=0,1,d=m+n=6的拓撲結(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ò)的另一個重要參數(shù)，往往對網(wǎng)絡(luò)的隨機游走研究起到一定的作用，然而很多復(fù)雜網(wǎng)絡(luò)的直徑并不是輕松獲得的，一般來說，獲得一些網(wǎng)絡(luò)直徑的精確解是相當(dāng)困難的．模型M(t)基于對稱迭代構(gòu)造，便于獲得直徑的精確解．分析得知，模型M(t)中任意兩頂點間的距離中只有在t時刻新加入的對稱頂點間的距離最長，根據(jù)直徑的定義D(t)=max{dij|i，j∈V(t)}，其中dij表示頂點i與頂點j的距離，進一步分析得知，M(t)中的直徑D(t)可以表示為：頂點i先走到與之相鄰的在t時刻休眠邊的頂點it，頂點j先走到與之相鄰的在t時刻休眠邊的頂點jt，直徑D(t)=1+ditjt+1．根據(jù)模型的對稱性知，頂點it與頂點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 度分布 度分布是一個刻畫復(fù)雜網(wǎng)絡(luò)是否具有無標(biāo)度性質(zhì)的拓撲參數(shù)．對模型M(t)中頂點的度構(gòu)成的度譜分析可知，這是一些離散的數(shù)據(jù)，為了獲得模型M(t)的度分布，采取累積度分布的計算方法[4]：

(6)

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

(7)

在ti≥1時，

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)計算得

(9)

(10)

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

(11)

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

(12)

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

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

(14)

(15)

2 結(jié) 語

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

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

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

O157.5

A

10.7511/dllgxb201704016