一類作為網絡模型的可平面無標度圖

馬 飛，姚 兵

(西北師范大學 數學與統計學院, 甘肅 蘭州 730070 )

一類作為網絡模型的可平面無標度圖

馬 飛，姚 兵*

(西北師范大學 數學與統計學院, 甘肅 蘭州 730070 )

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

無標度圖；網絡模型；小世界效應

0 引 言

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

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

1 模型的迭代及其拓撲性質

1.1 模型的迭代

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

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

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

(1)

(2)

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

圖1 模型M(t)拓撲結構Fig.1 Model M(t) topological structures

1.2 模型的拓撲性質

1.2.1 平均度 網絡的平均度〈k〉為邊個數的2倍與頂點個數之比，即

(3)

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

(4)

位于活動邊xy上下不同位置的新頂點和新邊會影響以后進入網絡的新頂點和新邊的位置，從而導致模型M(t)的拓撲結構的復雜性(圖2)．

圖2 模型M(t)在t=0,1,d=m+n=6的拓撲結構Fig.2 Model M(t) topological structures at t=0, 1, d=m+n=6

1.2.3 直徑 直徑作為研究復雜網絡的另一個重要參數，往往對網絡的隨機游走研究起到一定的作用，然而很多復雜網絡的直徑并不是輕松獲得的，一般來說，獲得一些網絡直徑的精確解是相當困難的．模型M(t)基于對稱迭代構造，便于獲得直徑的精確解．分析得知，模型M(t)中任意兩頂點間的距離中只有在t時刻新加入的對稱頂點間的距離最長，根據直徑的定義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．根據模型的對稱性知，頂點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 度分布 度分布是一個刻畫復雜網絡是否具有無標度性質的拓撲參數．對模型M(t)中頂點的度構成的度譜分析可知，這是一些離散的數據，為了獲得模型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相關聯的邊的數目、活動邊的數目、休眠邊的數目．顯然有k(i，t)=kg(i，t)+kp(i，t)．鑒于模型M(t)的構造，可以得到：當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)

聯立式(6)、(7)、(11)，得到網絡模型M(t)的累積度分布為

(12)

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

當k?1時，將獲得如下表達式：

(14)

(15)

2 結 語

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

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

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

O157.5

A

10.7511/dllgxb201704016