翟因虎，王銀河

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

?

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

翟因虎a,b，王銀河a

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

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

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

0　引言

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

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

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

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

網(wǎng)絡(luò)或者圖的標(biāo)號(hào)問(wèn)題的背景主要來(lái)源于實(shí)際問(wèn)題，到目前為止已有十幾種標(biāo)號(hào)被定義，其應(yīng)用范圍已深入到諸如碼論、X-射線結(jié)晶學(xué)、天文學(xué)、雷達(dá)和循環(huán)設(shè)計(jì)等領(lǐng)域。 關(guān)于圖標(biāo)號(hào)問(wèn)題，早期主要研究某種特殊圖是否具有某種標(biāo)號(hào)，如優(yōu)美標(biāo)號(hào)和協(xié)調(diào)標(biāo)號(hào)。這些標(biāo)號(hào)都是不含節(jié)點(diǎn)拓?fù)潢P(guān)系等信息的標(biāo)號(hào)方法。最近的研究表明，為了深入分析復(fù)雜網(wǎng)絡(luò)確定性模型的結(jié)構(gòu)性質(zhì)、最短路由和隨機(jī)游走等動(dòng)力學(xué)過(guò)程，可以采用包含節(jié)點(diǎn)間拓?fù)潢P(guān)系信息的標(biāo)號(hào)方法來(lái)標(biāo)記網(wǎng)絡(luò)節(jié)點(diǎn)，如阿波羅網(wǎng)絡(luò)[28]、自相似外可平面無(wú)聚類圖[29]和無(wú)標(biāo)度模塊化可平面圖[30]等確定性模型。在包含相關(guān)信息的節(jié)點(diǎn)標(biāo)號(hào)幫助下，以上作者成功地獲得復(fù)雜網(wǎng)絡(luò)確定性模型的性質(zhì)或者最短路由。受上文啟發(fā)，我們給平面Koch網(wǎng)絡(luò)找到了一種包含節(jié)點(diǎn)接入網(wǎng)絡(luò)時(shí)間和位置信息的標(biāo)號(hà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é)點(diǎn)標(biāo)號(hào)方法、最短路由、最短路徑長(zhǎng)度、節(jié)點(diǎn)和邊介數(shù)的計(jì)算，還沒(méi)有文章見(jiàn)諸報(bào)端。本文研究正多邊形Koch分形島映射成Koch演化網(wǎng)絡(luò)，給出一種有效的節(jié)點(diǎn)標(biāo)號(hào)方法，并基于此節(jié)點(diǎn)標(biāo)號(hào)分析了Koch網(wǎng)絡(luò)的主要拓?fù)湫再|(zhì)、最短路由、最短路徑長(zhǎng)度和網(wǎng)絡(luò)節(jié)點(diǎn)與邊的介數(shù)的解析解。基于本文結(jié)論，可有助于更加深入地定性定量研究上述Koch網(wǎng)絡(luò)的多種重要性質(zhì)，還可以有助于深入研究復(fù)雜網(wǎng)絡(luò)隨機(jī)模型和實(shí)證網(wǎng)絡(luò)的結(jié)構(gòu)、功能和動(dòng)力學(xué)過(guò)程。

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

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

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

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

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

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

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

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

(1)

令L(v)為節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)標(biāo)號(hào)集， Le(v)，Ll(v) 和 Lh(v)分別為與節(jié)點(diǎn)v的度相等、小于和大于關(guān)系的鄰居節(jié)點(diǎn)的標(biāo)號(hà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)造機(jī)制，可得K(1,m,t)的節(jié)點(diǎn)總數(shù)和邊總數(shù)分別為

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

(6)

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

(7)

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

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

(8)

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

(9)

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

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

(12)

可見(jiàn)網(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。由圖可見(jiàn)，子網(wǎng)絡(luò)K(1,m,t)具有很高的聚類系數(shù)，比如當(dāng)m=1時(shí)，聚類系數(shù)趨于0.820 1。m越大，聚類系數(shù)越高； t越大，聚類系數(shù)也越高； 聚類系數(shù)隨著m和t的增加而趨于常數(shù)。因?yàn)榫W(wǎng)絡(luò)K(1,1,1)為一個(gè)三角形，此時(shí)網(wǎng)絡(luò)聚類系數(shù)為1，所以圖3a在t=1，m=1存在一個(gè)尖峰。

C(n,m,t)=

(16a)

當(dāng)n>3時(shí)，

(16b)

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

3.3平均最短路徑長(zhǎng)度

(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é)點(diǎn)X處共有m+1個(gè)子網(wǎng)絡(luò)Ki(1,m,t)(i=1,2,…,m+1)相互連接(注意節(jié)點(diǎn)X同時(shí)屬于上述m+1個(gè)子網(wǎng)絡(luò))；在節(jié)點(diǎn)Y1到Y(jié)2m處，分別連接子網(wǎng)絡(luò)Ki(1,m,t)(i=m+2, m+3,…,3m+1)(注意Yi點(diǎn)屬于子網(wǎng)絡(luò)Ki+1+m(1,m,t), i=1,2,…,2m)。由于節(jié)點(diǎn)X是重合點(diǎn)，可得K(1,m,t+1)與任意子網(wǎng)絡(luò)Ki(1,m,t)所有節(jié)點(diǎn)最短路徑和的關(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)

又因?yàn)橛墒?18)可以得到

(22)

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

(23)

所以，

(24)

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

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ù)時(shí)，

(27b)

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

(28a)

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

(28b)

當(dāng)t→∞時(shí)，

(29)

當(dāng)m→∞時(shí)，

(30)

當(dāng)n→∞時(shí)，

(31)

圖5b所示為網(wǎng)絡(luò)K(3,m,t)的平均最短路徑長(zhǎng)度d(3,m,t)，顯然網(wǎng)絡(luò)K(n,m,t)的平均路徑長(zhǎng)度d(n,m,t)性質(zhì)與子網(wǎng)絡(luò)K(1,m,t)一致，都是與t線性相關(guān)；當(dāng)m較大時(shí)，與m基本上線性相關(guān)。可見(jiàn)，Koch網(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)的生成機(jī)制可知，Diam(1,m,t+1)=Diam(1,m,t)+2，所以

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

(32)

(33)

當(dāng)正多邊形邊數(shù)n為有限值時(shí)，網(wǎng)絡(luò)K(n,m,t+1)直徑與網(wǎng)絡(luò)大小對(duì)數(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é)點(diǎn)傾向于和度值小的節(jié)點(diǎn)連接，網(wǎng)絡(luò)被看作是反向匹配的。

(36)

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

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

(37)

(38)

(39a)

(39b)

(40)

(41a)

(41b)

4　結(jié)論

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

平面Koch網(wǎng)絡(luò)是一種節(jié)點(diǎn)數(shù)目和邊數(shù)目都是指數(shù)增加的演化網(wǎng)絡(luò)，網(wǎng)絡(luò)直徑與網(wǎng)絡(luò)規(guī)模的對(duì)數(shù)成正比，同時(shí)具備無(wú)標(biāo)度、小世界和高聚類系數(shù)等特性，并且是負(fù)指數(shù)度相關(guān)的異配網(wǎng)絡(luò)，這些性質(zhì)與不少實(shí)際網(wǎng)絡(luò)如因特網(wǎng)等相同，這說(shuō)明平面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ò)等，針對(duì)這些確定性模型還只是進(jìn)行了比較初步的研究，尚未得到最短路由、最短路徑長(zhǎng)度和介數(shù)中心性等網(wǎng)絡(luò)性質(zhì)和一些動(dòng)力學(xué)過(guò)程的解析解，值得使用本文研究的節(jié)點(diǎn)標(biāo)號(hào)法進(jìn)行更進(jìn)一步的相關(guān)研究。鑒于復(fù)雜演化Koch網(wǎng)絡(luò)結(jié)構(gòu)性質(zhì)與很多實(shí)際網(wǎng)絡(luò)相同，可以利用此網(wǎng)絡(luò)能夠解析求解的優(yōu)點(diǎn)，對(duì)節(jié)點(diǎn)數(shù)目巨大的復(fù)雜網(wǎng)絡(luò)中很多重要的結(jié)論如隨機(jī)游走、譜特性、相繼故障、博弈、同步與控制、傳播、網(wǎng)絡(luò)參數(shù)辨識(shí)進(jìn)行更加深入的定量研究和發(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ìn)展[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]李永，方錦清，劉強(qiáng). 多種確定性廣義Farey組織的網(wǎng)絡(luò)金字塔[J].物理學(xué)報(bào)，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] 邢長(zhǎng)明，劉方愛(ài).基于Sierpinski分形墊的確定性復(fù)雜網(wǎng)絡(luò)演化模型研究[J].物理學(xué)報(bào)，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] 劉甲雪，孔祥木.無(wú)標(biāo)度立體Koch網(wǎng)絡(luò)的建立及其結(jié)構(gòu)性質(zhì)研究[J].物理學(xué)報(bào)，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é)任編輯李進(jìn))

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

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

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

TP1；N94

A