基于節點標號的Koch網絡結構性質研究

翟因虎，王銀河

(廣東工業大學 a.自動化學院，b.信息工程學院，廣州 510006)

?

基于節點標號的Koch網絡結構性質研究

翟因虎a,b，王銀河a

(廣東工業大學 a.自動化學院，b.信息工程學院，廣州 510006)

針對正多邊形Koch分形島所映射成的Koch網絡，根據節點接入網絡的時間和位置信息給節點標號。在節點標號的基礎上，研究網絡的最短路由及計算最短路徑長度；并分析網絡的主要結構性質，如節點的度、度分布和累積度分布函數，以及網絡的聚類系數、平均最短路徑長度、度關聯函數和介數中心性，得出結構性質的解析解。結果表明，所構建的Koch網絡是無標度和小世界的；其聚類系數趨向于比較大的常數值；平均路徑長度與網絡節點數的對數呈正比關系，度相關函數、點介數和邊介數都隨節點度的變化而指數變化。

Koch網絡；節點標號；網絡性質；最短路由

0　引言

如何適當地構建網絡模型是復雜網絡研究中最根本問題之一，因為復雜網絡的拓撲結構與網絡的動力學行為和功能是密切相關相互影響的。我們生活中存在各種復雜的社會和技術網絡，如社交網絡、科研合作網絡、交通網絡、疾病傳播網絡、基因調控網絡、細胞代謝網絡、食物鏈網絡、腦神經網絡和生態網絡等，為了深入研究和理解這些網絡，必須構造與實際網絡拓撲結構本質相似或同構的網絡模型。Watts和Strogatz在1998年提出了小世界網絡WS模型[1]，它具有較小最短路徑和較大集聚系數，成功解釋了社會學的“六度分離”現象；Barabasi和Albert在1999年提出了無標度網絡BA模型[2]，它具有冪律度分布，符合大多數復雜網絡的基本特性，從而與Watts等共同開創了復雜網絡研究的先河。自此之后，關于復雜網絡及其模型的研究就如雨后春筍般蓬勃發展。由于BA無標度網絡模型和WS小世界網絡模型與許多現實網絡特性存在一些偏離，很多研究人員提出了多種推廣的隨機模型，使得這些隨機模型生成的網絡更接近現實。但是，上述隨機模型模擬實際網絡時存在一些問題，比如隨機加邊或隨機重連等網絡生成機制與實際網絡的演化過程不相符，所生成的網絡模型不直觀，網絡結構性質的分析必須使用統計物理等高深的理論工具且對節點數目巨大的網絡計算量災難性增加，關于網絡功能和動力學的結論難于定性定量分析等。

而以確定性方式生成的網絡，不但形象直觀，而且使人更容易了解網絡的生成特點以及節點間的相互作用關系，更重要的是，容易得到復雜網絡結構性質、功能和動力學的精確解析解，對復雜網絡的深入研究具有特殊的價值和意義。循著這個思路，2000年以來，具有不同性質的確定性網絡模型逐漸被提出和研究[3]。比如第一個小世界網絡確定性模型被Comellas等提出[4]。確定性均勻遞歸樹是最簡單的確定性模型之一，累積度分布以指數形式衰減，平均路徑長度隨著網絡的規模呈現對數形式增長，為正相關的小世界網絡，節點介數服從指數為2的冪律分布，特別是鄰接矩陣的所有特征值互不相同，這一性質是獨一無二的，是目前其它的網絡所不具備的[3,5]。第一個層次網絡確定性模型被Barabasi等提出和研究[6]，該網絡是無標度的、冪律指數為2；這類網絡模型節點度服從冪律分布，節點的集聚系數與其度成反比，層次網絡模型為人們研究復雜網絡提供了新的視角和方法，該確定性層次網絡發表后不久，便引起了廣泛關注。周濤等[7]研究了整數網絡，發現其聚類系數趨于0.34且出度服從冪率分布。方錦清等[8]研究了Farey有理數樹狀網絡，證明網絡度分布服從指數分布。

復雜性問題的研究方法總結起來主要有：分子動力學、混沌、分形、復雜網絡等。于是自然有人要問：這些復雜性問題的研究方法之間有什么聯系呢？由經典分形(如Apollo分形墊、Sierpinski分形墊、Koch曲線)映射為復雜網絡，可以把復雜性問題的兩大重要分支——分形和復雜網絡聯系起來[3]。Apollo分形墊映射成的復雜網絡得到了廣泛的研究，這是一種無標度小世界網絡，聚類系數高達0.828，冪指數為2.85[9-10]。Sierpinski分形墊映射成的復雜網絡是最大可平面圖，冪率指數為2+ln3/ln2，聚類系數趨于0.598的小世界網絡[11-12]。章忠志等還對諸多分形映射成確定性模型的結構性質、功能和動力學過程進行了開創性的研究[12-21]，這些分形網絡都為小世界、無標度網絡，具有較高的聚類系數，適合作為實證網絡的研究模型。

Koch網絡是根據經典的Koch分形曲線構造的，該網絡的性質與許多真實世界網絡相似，同時具有無標度、小世界和高聚類系數等實際網絡的特性，有著重要的研究價值[17-21]。章忠志等研究了平面Koch網絡的構造與結構性質的分析、Laplace譜的分析解和網絡中的隨機游走，結果表明網絡是無標度的、度分布臨界指數范圍為[2，3]，聚類系數大概為0.9左右，度相關近似為指數為負數的冪率分布，并分析了這類網絡的隨機游走動力學過程[17-21]。鑒于Koch網絡的重要作用，不少作者對Koch網絡進行了諸多有益的拓展研究，主要體現在構造機理不變，把三角形基本單元變換為其它不同種類的結構單元。劉甲雪等研究了以四面體為基本單元的立體Koch網絡[22]，發現聚類系數趨于0.870 435，平均路徑長度的增長行為同平面Koch 網絡的十分近似，但是其度分布臨界指數γ>3，立體Koch 網絡具有度關聯性，但是不能構建任意的無度關聯性的無標度網絡。傅新楚等研究了正八面體Koch網絡的結構性質[23]，發現這種網絡是無標度的、且度分布臨界指數γ>3，是一種聚類系數趨于0.68的同配網絡，投影在平面上時構成一種特殊的最近鄰耦合Koch網絡。孫偉剛等研究了正多邊形Koch網絡的結構性質和隨機游走，網絡是無標度的、且度分布臨界指數為γ=ln(m+1)/ln2+1，其中m為正整數；當m>3時聚類系數為0，當m=3就是平面Koch網絡[24-25]。孫偉剛等還研究了正多面體Koch網絡，網絡是無標度的、度分布臨界指數范圍為[2，3]，與平面Koch網絡相同；具有很高的聚類系數；平均路徑長度與網絡大小對數成正比，是一種異配網絡[26]。張紅娟等把邊權導入了多邊形Koch網絡，構成了有權網絡，并對其上的隨機游動進行了研究[27]。

網絡或者圖的標號問題的背景主要來源于實際問題，到目前為止已有十幾種標號被定義，其應用范圍已深入到諸如碼論、X-射線結晶學、天文學、雷達和循環設計等領域。 關于圖標號問題，早期主要研究某種特殊圖是否具有某種標號，如優美標號和協調標號。這些標號都是不含節點拓撲關系等信息的標號方法。最近的研究表明，為了深入分析復雜網絡確定性模型的結構性質、最短路由和隨機游走等動力學過程，可以采用包含節點間拓撲關系信息的標號方法來標記網絡節點，如阿波羅網絡[28]、自相似外可平面無聚類圖[29]和無標度模塊化可平面圖[30]等確定性模型。在包含相關信息的節點標號幫助下，以上作者成功地獲得復雜網絡確定性模型的性質或者最短路由。受上文啟發，我們給平面Koch網絡找到了一種包含節點接入網絡時間和位置信息的標號方法,以便更加深入地研究Koch網絡的不容易用迭代方法推導得到的重要性質。

目前，關于Koch網絡的研究更多的偏重于拓展網絡構成基本單元的類別，而關于一些Koch網絡的深入研究，比如正多邊形Koch分形島映射成的復雜Koch網絡的主要結構性質、Koch網絡的節點標號方法、最短路由、最短路徑長度、節點和邊介數的計算，還沒有文章見諸報端。本文研究正多邊形Koch分形島映射成Koch演化網絡，給出一種有效的節點標號方法，并基于此節點標號分析了Koch網絡的主要拓撲性質、最短路由、最短路徑長度和網絡節點與邊的介數的解析解。基于本文結論，可有助于更加深入地定性定量研究上述Koch網絡的多種重要性質，還可以有助于深入研究復雜網絡隨機模型和實證網絡的結構、功能和動力學過程。

1　Koch網絡模型

Koch分形島的生成方式為：1)當迭代次數t=0時，分形島為正n邊形，即啟動子為正n邊形(其中n∈?+)； 2)t每次增加1時，分形島的每條直線段都均勻分割為2m+1(其中m∈?+)整數段并依次編號，再把標號為偶數的直線段替換為等邊三角形，然后去掉此標號為偶數的直線段，也就是生成子為上述迭代方式；3)如此迭代t次，即得到Koch分形島S(n,m,t)。顯然，單獨一條直線段生成的分形為基本分形S(1,m,t)，且分形島S(n,m,t)為n個基本分形S(1,m,t)依次相連而成。圖1外圈所示的圖形為Koch分形島S(6,2,2)，其中紅色線段對應t=0，黑色線段對應t=1，藍色線段對應t=2。

把上述Koch分形島S(n,m,ti)(ti=0,1,2,…,t)中的直線段映射為網絡節點，把兩直線段之間的連接關系映射為相應兩節點之間的連邊，就可以得到Koch網絡K(n,m,t)。一條直線上生成的分形S(1,m,t)映射成子網絡K(1,m,t)，n個子網絡K(1,m,t)的Hub節點依次相連就構成Koch網絡K(n,m,t)。圖1內圈所示的圖形為網絡K(6,2,2)，其中紅色節點為t=0時紅色線段映射而成，黑色節點為t=1時黑色線段映射而成，藍色節點為t=2時藍色線段映射而成，直線段之間的相交對應相應節點間的連線。圖1中網絡K(6,2,2)由6個相同的子網絡K(1,2,2)組成。可見，為了研究網絡K(n,m,t)，必須先研究子網絡K(1,m,t)。

2　Koch網絡的節點標號與最短路由

2.1網絡的節點標號

2.2網絡的最短路由

定義M(i)為i時刻接入網絡節點的標號集合，顯然M(0)={1,2,…,n}且M(i)={gb1b2b3…bi.l(i)}。

定義L(n,m,t)為網絡K(n,m,t)中所有節點標號的集合，則有

(1)

令L(v)為節點v的鄰居節點標號集， Le(v)，Ll(v) 和 Lh(v)分別為與節點v的度相等、小于和大于關系的鄰居節點的標號集合。顯然

L(v)=Ll(v)∪Lh(v)∪Le(v)

(2)

其中

Ll(v)={gb1b2…bi0.lv(i+1),gb1b2…bi01.lv(i+2),

…,gb1b2…bi01…1.lv(t)}

(3)

(4)

Le(v)={gb1b2b3…bi.le(i)}

(5)

3　Koch網絡的結構性質

根據Koch網絡的構造機制，可得K(1,m,t)的節點總數和邊總數分別為

N(1,m,t)=2×((3m+1)t-1)/3+1

(6)

E(1,m,t)=(3m+1)t-1

(7)

若節點v在ti時刻加入網絡，在t時刻的節點度為

k=kv(1,m,ti)=2×(m+1)t-ti

(8)

其中，當ti=0時，kv(1,m,0)=2(m+1)t-2。每步迭代后K(1,m,t)節點數目的增量，即K(1,m,t)中與節點v度相同的節點數目為Lv(1,m,ti)=2m×(3m+1)ti-1，則K(1,m,t)的度平均為

(9)

可見子網絡K(1,m,t)具有稀疏的網絡結構，符合真實網絡的特點。

網絡K(n,m,t)的節點與邊總數為

N(n,m,t)=n×(2×(3m+1)t+1)/3

(10)

E(n,m,t)=n×m×(3m+1)t-1

(11)

網絡K(n,m,t)中ti時刻加入網絡的節點v在t時刻的度為k=kv(n,m,ti)=2(m+1)t-ti，與式(9)相同，網絡中度相等節點的數目為Lv(n,m,ti)=2nm×(3m+1)ti-1，且Lv(n,m,0)=n，則 K(n,m,t)的度平均〈k〉為

(12)

可見網絡K(n,m,t)是與網絡K(1,m,t)一樣的稀疏網絡，度平均都是基本相同的。

3.1度分布

(13)

(14)

3.2聚類系數

(15)

圖3a為子網絡K(1,m,t)的聚類系數圖，其中m和t的取值范圍都為1到20。由圖可見，子網絡K(1,m,t)具有很高的聚類系數，比如當m=1時，聚類系數趨于0.820 1。m越大，聚類系數越高； t越大，聚類系數也越高； 聚類系數隨著m和t的增加而趨于常數。因為網絡K(1,1,1)為一個三角形，此時網絡聚類系數為1，所以圖3a在t=1，m=1存在一個尖峰。

C(n,m,t)=

(16a)

當n>3時，

(16b)

C(n,m,t)如圖3b所示，可見網絡K(n,m,t)與子網絡K(1,m,t)一樣，都具有很高的聚類系數，并隨著m和t的增加而趨于常數。

3.3平均最短路徑長度

(17)

為了求出Dtotal(1,m,t)，必須先研究如圖4a所示的網絡K(1,m,t+1)構成圖。網絡K(1,m,t+1)中，在節點X處共有m+1個子網絡Ki(1,m,t)(i=1,2,…,m+1)相互連接(注意節點X同時屬于上述m+1個子網絡)；在節點Y1到Y2m處，分別連接子網絡Ki(1,m,t)(i=m+2, m+3,…,3m+1)(注意Yi點屬于子網絡Ki+1+m(1,m,t), i=1,2,…,2m)。由于節點X是重合點，可得K(1,m,t+1)與任意子網絡Ki(1,m,t)所有節點最短路徑和的關系

Dtotal(1,m,t+1)=

(3m+1)×Dtotal(1,m,t)+

Ω(1,m,t)

(18)

Ω(1,m,t)=(3m2+m)×s(1,m,t)×(3×N(1,m,t)-1)-2m2×N(1,m,t)+

(6m2-m)×N2(1,m,t)

(19)

由圖4a易知s(1,m,t+1)=(m+1)×s(1,m,t)+2m×(s(1,m,t)+N(1,m,t)-1)+2m，且s(1,m,2)=2m×(5m+2)，所以可以解出

s(1,m,t)=((12mt+6m+2)×(3m+1)t-1-2)/9

(20)

把式(6)和(20)代入式(19)得

(21)

又因為由式(18)可以得到

(22)

且Dtotal(1,m,1)=4m2-m，再把式(21)代入(22)可以解出

(23)

所以，

(24)

網絡K(n,m,t)的平均路徑長度為

d(n,m,t)=

(25)

又由圖4b所示K(n,m,t)的結構示意圖，可得

Dtotal(n,m,t)=n×Dtotal(1,m,t)+Ω(n,m,t)

(26)

(27a)

當n為偶數時，

(27b)

其中,s(1,m,t)見式(20)。當n為偶數時

(28a)

當n為奇數時，

(28b)

當t→∞時，

(29)

當m→∞時，

(30)

當n→∞時，

(31)

圖5b所示為網絡K(3,m,t)的平均最短路徑長度d(3,m,t)，顯然網絡K(n,m,t)的平均路徑長度d(n,m,t)性質與子網絡K(1,m,t)一致，都是與t線性相關；當m較大時，與m基本上線性相關。可見，Koch網絡性質主要決定于網絡迭代生成的方式。

3.4網絡直徑

顯然，Diam(1,m,0)=0，Diam(1,m,1)=2，且由網絡K(1,m,t+1)的生成機制可知，Diam(1,m,t+1)=Diam(1,m,t)+2，所以

Diam(1,m,t)=2t～t

(32)

(33)

當正多邊形邊數n為有限值時，網絡K(n,m,t+1)直徑與網絡大小對數成正比。

3.5度相關性

4m×(t-ti)×(m+1)t-ti-1)/2(m+1)t-ti

(34)

(35)

可得knn(1,k)～k-ω，即knn(1,k)隨k的增大而減小，表示度值大的節點傾向于和度值小的節點連接，網絡被看作是反向匹配的。

(36)

3.6節點的介數中心性

網絡節點的重要性可以通過節點的中心性來衡量。定義節點v的介數中心性為

(37)

(38)

(39a)

(39b)

(40)

(41a)

(41b)

4　結論

本文針對正多邊形Koch分形島映射成的復雜演化Koch網絡，給出一種包含節點接入網絡時間與精確位置信息的節點標號方法；并基于節點標號，研究了任意節點間的最短路由算法；并推導Koch網絡的多種重要結構性質的解析解。結果表明：1)Koch網絡的結構性質主要取決于分形的生成子，即Koch分形映射為復雜網絡的映射方式，與分形的啟動子基本無關。也就是說，Koch網絡的結構性質主要決定于網絡的迭代生成方式，與正多邊形的邊數基本無關。2)由Koch網絡的主要結構性質的解析解可知，Koch網絡是無標度網絡，其冪指數為(2，3]；網絡具有小世界特性，平均最短路徑長度與網絡大小的對數成比例；網絡具有很高的聚類系數，聚類系數隨著迭代結構參數m和迭代步數t的增加而趨于常數；網絡直徑與網絡大小的對數成比例；度相關函數隨節點度的增大而減小，表示度值大的節點傾向于和度值小的節點連接，網絡被看作是反向匹配的；節點的點介數和邊介數中心性都與節點度成指數關系。3)Koch網絡可以采用一種基于節點接入網絡時間和位置信息的方法進行標號，從而可以方便研究網絡的最短路由、最短路徑長度和介數中心性等網絡性質的解析解，這也是本文的主要創新點。4)論文[17]中Koch網絡為本文中n=3時的特例。

平面Koch網絡是一種節點數目和邊數目都是指數增加的演化網絡，網絡直徑與網絡規模的對數成正比，同時具備無標度、小世界和高聚類系數等特性，并且是負指數度相關的異配網絡，這些性質與不少實際網絡如因特網等相同，這說明平面Koch網絡是可以作為研究大型復雜網絡定量性質的網絡模型。另外，平面Koch網絡存在諸多的變形和拓展，如正多邊形Koch網絡、正多面體Koch網絡、有權正多邊形Koch網絡等，針對這些確定性模型還只是進行了比較初步的研究，尚未得到最短路由、最短路徑長度和介數中心性等網絡性質和一些動力學過程的解析解，值得使用本文研究的節點標號法進行更進一步的相關研究。鑒于復雜演化Koch網絡結構性質與很多實際網絡相同，可以利用此網絡能夠解析求解的優點，對節點數目巨大的復雜網絡中很多重要的結論如隨機游走、譜特性、相繼故障、博弈、同步與控制、傳播、網絡參數辨識進行更加深入的定量研究和發現。

[1]Watts D J， Strogatz S H. Collective dynamics of ‘small-world’networks[J]. nature， 1998， 393(6684)： 440-442.

[2]Barabási A L， Albert R. Emergence of scaling in random networks[J]. science， 1999， 286(5439)： 509-512.

[3]章忠志， 周水庚， 方錦清. 復雜網絡確定性模型研究的最新進展[J]. 復雜系統與復雜性科學， 2008， 5(4)：29-46.

Zhang Zhongzhi， Zhou Shuigeng， Fan Jinqing. Recent progress of deterministic models forcomplex networks[J]. Complex Systems and Complexity Science， 2008， 5(4):29-46.

[4]Comellas F， Ozon J， Peters J G. Deterministic small-world communication networks[J]. Information Processing Letters， 2000， 76(1)： 83-90.

[5]Zhang Z， Zhou S， Qi Y， et al. Topologies and Laplacian spectra of a deterministic uniform recursive tree[J]. The European Physical Journal B-Condensed Matter and Complex Systems， 2008， 63(4)： 507-513.

[6]Barabási A L， Ravasz E， Vicsek T. Deterministic scale-free networks[J]. Physica A： Statistical Mechanics and its Applications， 2001， 299(3)： 559-564.

[7]Zhou T， Wang B H， Hui P M， et al. Topological properties of integer networks[J]. Physica A： Statistical Mechanics and its Applications， 2006， 367： 613-618.

[8]李永，方錦清，劉強. 多種確定性廣義Farey組織的網絡金字塔[J].物理學報，2010，05：2991-3000.

Li Yong， Fan Jingqing， Liu Qiang. Determinate generalized Farey organized network pyramid[J]. Acta Physica Sinina， 2010，05：2991-3000.

[9]Andrade Jr J S, Herrmann H J, Andrade R F S, et al. Apollonian networks: simultaneously scale-free, small world, euclidean, space filling, and with matching graphs[J]. Physical Review Letters, 2005, 94(1): 018702.

[10] Zhang Z, Chen L, Zhou S, et al. Exact analytical solution of average path length for Apollonian networks[J]. arXiv preprint arXiv:0706.3491, 2007.[DB/OL].[2014-05-06]. http://arxiv.org/abs/0706.3491.

[11] 邢長明，劉方愛.基于Sierpinski分形墊的確定性復雜網絡演化模型研究[J].物理學報，2010，59(3)：1608-1614.

Xing Chang-ming， Liu Fan-ai. [J]. Research on the determinstic complex network model based on the Sierpinski network[J]. ACTA PHYSICA SININA， 2010，59(3)：1608-1614.

[12] Zhang Z, Zhou S, Fang L, et al. Maximal planar scale-free Sierpinski networks with small-world effect and power law strength-degree correlation[J]. EPL (Europhysics Letters), 2007, 79(3): 38007.

[13] Zhang ZH ZH， Qi Y， Zhou SH G，et al. Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees[J]. Physical Review E， 2010， 81：016114.

[14] Zhang ZH ZH， Yang Y H， Gao SH Y. Role of fractal dimension in random walks on scale-free networks[J]. European Physical Journal B， 2011， 84：331-338.

[15] Wu B， Zhang ZH ZH， Chen G R. Properties and applications of Laplacian spectra for the Koch networks[J]. Journal of Physics A： Mathematical and Theoretical， 2012， 45：025102.

[16] Zhang ZH ZH， Shan T， Chen G R. Random walks on weighted networks[J]. Physical Review E， 2013， 87：012112.

[17] Zhang Z， Wu B， Comellas F. The number of spanning trees in Apollonian networks[J]. Discrete Applied Mathematics， 2014， 169： 206-213.

[18] Zhang Z， Gao S， Chen L， et al. Mapping Koch curves into scale-free small-world networks[J]. Journal of Physics A： Mathematical and Theoretical， 2010， 43(39)： 395101.

[19] Zhang Z， Zhou S， Xie W， et al. Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect[J]. Physical Review E， 2009， 79(6)： 061113.

[20] Zhang Z, Gao S, Xie W. Impact of degree heterogeneity on the behavior of trapping in Koch networks[J]. Chaos: an Interdisciplinary Journal of Nonlinear Science, 2010, 20(4): 043112.

[21] Zhang Z, Gao S. Scaling of mean first-passage time as efficiency measure of nodes sending information on scale-free Koch networks[J]. The European Physical Journal B-Condensed Matter and Complex Systems, 2011, 80(2): 209-216.

[22] 劉甲雪，孔祥木.無標度立體Koch網絡的建立及其結構性質研究[J].物理學報，2010，4：2244-2249.

Liu Jia-xue， Kong Xiang-mu. Establishment and structure properties on scale-free Koch network[J]. Acta Physica Sinna， 2010，4：2244-2249.

[23] Chen R, Fu X, Wu Q. On topological properties of the octahedral Koch network[J]. Physica A: Statistical Mechanics and its Applications, 2012, 391(3): 880-886.

[24] Zhang J, Sun W. The structural properties of the generalized Koch network[J]. Journal of Statistical Mechanics: Theory and Experiment, 2010, (7): P07011.

[25] Zhang J Y, Sun W G, Chen G R. Exact scaling for the mean first-passage time of random walks on a generalized Koch network with a trap[J]. Chinese Physics B, 2012, 21(3): 8901.

[26] Sun W, Zhang J, Wu Y. Novel evolving small-world scale-free Koch networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2011, 2011(3): P03021.

[27] Wu Z K, Hou B Y, Zhang H S, et al. Scaling of average weighted shortest path and average receiving time on weighted expanded Koch networks[J]. International Journal of Modern Physics B, 2014, 28(28):2699-2700.

[28] Zhang Z， Comellas F， Fertin G， et al. Vertex labeling and routing in expanded Apollonian networks[J]. Journal of Physics A： Mathematical and Theoretical， 2008， 41(3)： 035004.

[29] Comellas F， Miralles A. Vertex labeling and routing in self-similar outerplanar unclustered graphs modeling complex networks[J]. Journal of Physics A： Mathematical and Theoretical， 2009， 42(42)： 425001.

[30] Comellas F， Miralles A. Label-based routing for a family of scale-free， modular， planar and unclustered graphs[J]. Journal of Physics A： Mathematical and Theoretical， 2011， 44(20)： 205102.

(責任編輯李進)

The Structural Properties of Koch Networks Based on Node Labels

ZHAI Yinhua,b， WANG Yinhea

(a.School of Automation， b.School of Information Engineering， Guangdong University of Technology， Guangzhou 510006， China)

The Koch Fractal Island， which is starting from a regular polygon， is mapped to complex evolving Koch networks. The informative labels are given to nodes， the labels are based on the time and location when nodes are accessing to Koch networks. By the advantages of the informative labels， we get the exact solution of main structural properties of Koch networks， including degree distribution and cumulative degree distribution function， as well as the clustering coefficient， average shortest path length and the correlation function of degree， betweenness centrality and the shortest path routing and length. The results show that， Koch network is a scale-free and small-world network; its clustering coefficient tends to relatively large constant; average shortest path length is proportional to the logarithm of the size of networks; degree correlation function is exponential function relationship with node's degree.

Koch networks; node labeling; network property; shortest path routing

1672-3813(2016)03-0058-11;DOI:10.13306/j.1672-3813.2016.03.008

2015-01-15；

2015-05-21

國家自然科學基金(61273219;F030203)

翟因虎(1974-)，男，江西奉新人，博士研究生，講師，主要研究方向為復雜網絡辨識與控制等。

TP1；N94

A