翟因虎，王銀河

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

?

基于節(jié)點標(biāo)號的Koch網(wǎng)絡(luò)結(jié)構(gòu)性質(zhì)研究

翟因虎a,b，王銀河a

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

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

Koch網(wǎng)絡(luò)；節(jié)點標(biāo)號；網(wǎng)絡(luò)性質(zhì)；最短路由

0　引言

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

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

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

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

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

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

1　Koch網(wǎng)絡(luò)模型

Koch分形島的生成方式為：1)當(dāng)?shù)螖?shù)t=0時，分形島為正n邊形，即啟動子為正n邊形(其中n∈?+)； 2)t每次增加1時，分形島的每條直線段都均勻分割為2m+1(其中m∈?+)整數(shù)段并依次編號，再把標(biāo)號為偶數(shù)的直線段替換為等邊三角形，然后去掉此標(biāo)號為偶數(shù)的直線段，也就是生成子為上述迭代方式；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)，其中紅色線段對應(yīng)t=0，黑色線段對應(yīng)t=1，藍色線段對應(yīng)t=2。

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

2　Koch網(wǎng)絡(luò)的節(jié)點標(biāo)號與最短路由

2.1網(wǎng)絡(luò)的節(jié)點標(biāo)號

2.2網(wǎng)絡(luò)的最短路由

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

定義L(n,m,t)為網(wǎng)絡(luò)K(n,m,t)中所有節(jié)點標(biāo)號的集合，則有

(1)

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

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網(wǎng)絡(luò)的結(jié)構(gòu)性質(zhì)

根據(jù)Koch網(wǎng)絡(luò)的構(gòu)造機制，可得K(1,m,t)的節(jié)點總數(shù)和邊總數(shù)分別為

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

(6)

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

(7)

若節(jié)點v在ti時刻加入網(wǎng)絡(luò)，在t時刻的節(jié)點度為

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

(8)

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

(9)

可見子網(wǎng)絡(luò)K(1,m,t)具有稀疏的網(wǎng)絡(luò)結(jié)構(gòu)，符合真實網(wǎng)絡(luò)的特點。

網(wǎng)絡(luò)K(n,m,t)的節(jié)點與邊總數(shù)為

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

(10)

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

(11)

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

(12)

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

3.1度分布

(13)

(14)

3.2聚類系數(shù)

(15)

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

C(n,m,t)=

(16a)

當(dāng)n>3時，

(16b)

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

3.3平均最短路徑長度

(17)

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

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)

網(wǎng)絡(luò)K(n,m,t)的平均路徑長度為

d(n,m,t)=

(25)

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

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

(26)

(27a)

當(dāng)n為偶數(shù)時，

(27b)

其中,s(1,m,t)見式(20)。當(dāng)n為偶數(shù)時

(28a)

當(dāng)n為奇數(shù)時，

(28b)

當(dāng)t→∞時，

(29)

當(dāng)m→∞時，

(30)

當(dāng)n→∞時，

(31)

圖5b所示為網(wǎng)絡(luò)K(3,m,t)的平均最短路徑長度d(3,m,t)，顯然網(wǎng)絡(luò)K(n,m,t)的平均路徑長度d(n,m,t)性質(zhì)與子網(wǎng)絡(luò)K(1,m,t)一致，都是與t線性相關(guān)；當(dāng)m較大時，與m基本上線性相關(guān)?？梢姡琄och網(wǎng)絡(luò)性質(zhì)主要決定于網(wǎng)絡(luò)迭代生成的方式。

3.4網(wǎng)絡(luò)直徑

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

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

(32)

(33)

當(dāng)正多邊形邊數(shù)n為有限值時，網(wǎng)絡(luò)K(n,m,t+1)直徑與網(wǎng)絡(luò)大小對數(shù)成正比。

3.5度相關(guān)性

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

(34)

(35)

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

(36)

3.6節(jié)點的介數(shù)中心性

網(wǎng)絡(luò)節(jié)點的重要性可以通過節(jié)點的中心性來衡量。定義節(jié)點v的介數(shù)中心性為

(37)

(38)

(39a)

(39b)

(40)

(41a)

(41b)

4　結(jié)論

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

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

[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]章忠志， 周水庚， 方錦清. 復(fù)雜網(wǎng)絡(luò)確定性模型研究的最新進展[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 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組織的網(wǎng)絡(luò)金字塔[J].物理學(xué)報，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分形墊的確定性復(fù)雜網(wǎng)絡(luò)演化模型研究[J].物理學(xué)報，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] 劉甲雪，孔祥木.無標(biāo)度立體Koch網(wǎng)絡(luò)的建立及其結(jié)構(gòu)性質(zhì)研究[J].物理學(xué)報，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.

(責(zé)任編輯李進)

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

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

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

TP1；N94

A