熊云艷 肖文俊 毛宜軍 賴正文 韓冬 李梅生

(1. 華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 廣東 廣州 510006; 2. 廣東工貿(mào)職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)系, 廣東 廣州 510510;3. 華南理工大學(xué) 軟件學(xué)院, 廣東 廣州 510006; 4. 華南農(nóng)業(yè)大學(xué) 數(shù)學(xué)與信息學(xué)院, 廣東 廣州 510642)

復(fù)雜網(wǎng)絡(luò)度序列長(zhǎng)度分析*

熊云艷1,2肖文俊3毛宜軍4?賴正文1韓冬1李梅生1

(1. 華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 廣東 廣州 510006; 2. 廣東工貿(mào)職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)系, 廣東 廣州 510510;3. 華南理工大學(xué) 軟件學(xué)院, 廣東 廣州 510006; 4. 華南農(nóng)業(yè)大學(xué) 數(shù)學(xué)與信息學(xué)院, 廣東 廣州 510642)

針對(duì)度分布符合泊松分布的復(fù)雜網(wǎng)絡(luò)模型,文中從理論的角度證明了其度序列(1≤k1

復(fù)雜網(wǎng)絡(luò);節(jié)點(diǎn)度序列;泊松分布

人們對(duì)網(wǎng)絡(luò)的早期研究主要基于規(guī)則圖論及隨機(jī)圖論,但經(jīng)過(guò)深入研究,人們發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)是介于規(guī)則網(wǎng)絡(luò)及隨機(jī)網(wǎng)絡(luò)[1]之間的網(wǎng)絡(luò)模型.從理論的角度,典型的復(fù)雜網(wǎng)絡(luò)模型包括小世界網(wǎng)絡(luò)模型[2-3]、無(wú)標(biāo)度網(wǎng)絡(luò)模型[4]、局域世界演化網(wǎng)絡(luò)模型[5]、層次網(wǎng)絡(luò)模型[6]、確定性的小世界網(wǎng)絡(luò)模型[7]等;從現(xiàn)實(shí)網(wǎng)絡(luò)的角度,社交網(wǎng)絡(luò)、信息網(wǎng)絡(luò)、技術(shù)網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等都是屬于復(fù)雜網(wǎng)絡(luò)模型.

一般來(lái)說(shuō),復(fù)雜網(wǎng)絡(luò)的演化基于一定的連接規(guī)則及增長(zhǎng)規(guī)則.連接規(guī)則闡述了節(jié)點(diǎn)加入復(fù)雜網(wǎng)絡(luò)的連接方式,增長(zhǎng)規(guī)則說(shuō)明了網(wǎng)絡(luò)規(guī)模是逐漸增大的.如小世界網(wǎng)絡(luò)模型是介于規(guī)則網(wǎng)絡(luò)與隨機(jī)網(wǎng)絡(luò)之間的典型的復(fù)雜網(wǎng)絡(luò)模型,它采用了隨機(jī)化重連的機(jī)制,當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)比較多時(shí),其度分布符合泊松分布[2-3];無(wú)標(biāo)度網(wǎng)絡(luò)模型采用了增長(zhǎng)和優(yōu)先連接的機(jī)制,其度分布滿足冪律分布[4];部分規(guī)則圖模型如凱萊圖模型則采用一定的運(yùn)算規(guī)則進(jìn)行連接,網(wǎng)絡(luò)規(guī)模通常也是按照運(yùn)算規(guī)則增長(zhǎng),網(wǎng)絡(luò)節(jié)點(diǎn)度分布相對(duì)較為簡(jiǎn)單[8].

依據(jù)邊的方向性,復(fù)雜網(wǎng)絡(luò)可以分為有向網(wǎng)絡(luò)與無(wú)向網(wǎng)絡(luò),本文主要研究無(wú)向網(wǎng)絡(luò).無(wú)向復(fù)雜網(wǎng)絡(luò)模型的特性主要包括基本幾何特性和靜態(tài)特性,基本幾何特性包括平均度、度分布、聚集系數(shù)、網(wǎng)絡(luò)直徑、最短路徑和網(wǎng)絡(luò)中心性等,靜態(tài)特性包括聯(lián)合度分布、度-度相關(guān)性、聚-度相關(guān)性、介數(shù)、核數(shù)、緊密度、中心性和連通度等[9-10].不同的網(wǎng)絡(luò)生成機(jī)制可以生成不同的復(fù)雜網(wǎng)絡(luò)模型,但生成網(wǎng)絡(luò)模型的特性與網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)直接相關(guān).

通過(guò)對(duì)典型的度分布符合指數(shù)分布、冪律分布、泊松分布的復(fù)雜網(wǎng)絡(luò)模型進(jìn)行仿真研究,結(jié)合現(xiàn)實(shí)網(wǎng)絡(luò)的特性分析,文中發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)度序列長(zhǎng)度也是刻畫(huà)復(fù)雜網(wǎng)絡(luò)特性的一個(gè)參數(shù),并從理論的角度證明了度序列長(zhǎng)度與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的關(guān)系.

1 相關(guān)工作

無(wú)權(quán)的復(fù)雜網(wǎng)絡(luò)可以通過(guò)有向圖或者無(wú)向圖G(V,E)來(lái)描述,其中V表示復(fù)雜網(wǎng)絡(luò)的頂點(diǎn)集合、E表示復(fù)雜網(wǎng)絡(luò)的邊集合.描述復(fù)雜網(wǎng)絡(luò)的主要參數(shù)有N(復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)數(shù),N=|V|)、M(復(fù)雜網(wǎng)絡(luò)的邊數(shù),M=|E|)、d(v)(節(jié)點(diǎn)v的度,v(復(fù)雜網(wǎng)絡(luò)的平均度,d(v)/N)、nki(度為ki的節(jié)點(diǎn)數(shù))、P(ki)(度的分布概率或者度為ki的節(jié)點(diǎn)所占總節(jié)點(diǎn)的比例,P(ki)=nki/N)、l(不相等節(jié)點(diǎn)度序列的長(zhǎng)度,1≤k1

筆者在前期工作已經(jīng)證明了度分布符合冪律分布、指數(shù)分布、擴(kuò)展冪律分布(冪律及指數(shù)混合分布)的復(fù)雜網(wǎng)絡(luò)模型的度序列長(zhǎng)度l是log2N級(jí)別的[11-14],其主要結(jié)論如下:

(1)度分布符合冪律分布的復(fù)雜網(wǎng)絡(luò)模型

BA模型[4]是典型的無(wú)標(biāo)度復(fù)雜網(wǎng)絡(luò)模型,按照無(wú)標(biāo)度復(fù)雜網(wǎng)絡(luò)模型及度分布的概念(以度分布的頻率代替概率),無(wú)標(biāo)度復(fù)雜網(wǎng)絡(luò)的度分布概率定義為

(1)

(2)度分布符合擴(kuò)展冪律分布的復(fù)雜網(wǎng)絡(luò)模型

如果一個(gè)網(wǎng)絡(luò)模型的度分布符合擴(kuò)展冪律分布規(guī)律,則其度分布概率定義為

(2)

式中:i=1,2,…,l;c2、γ2、q為常數(shù).文獻(xiàn)[12]已證明

l-1≤log2N/log2q

(3)

從式(3)可知:當(dāng)q=2時(shí),式(3)與BA模型中度序列長(zhǎng)度的結(jié)論是一致的;當(dāng)q>2時(shí),因?yàn)閝為常數(shù),log2N/log2q≈(log2N)ε,所以式(3)可以表示為l≤(log2N)ε,可知l與log2N是同級(jí)別的.

(3)度分布符合指數(shù)分布的復(fù)雜網(wǎng)絡(luò)模型

度分布符合指數(shù)分布的復(fù)雜網(wǎng)絡(luò)模型往往采用遞歸的方式生成,其度分布概率定義為

(4)

式中:i=1,2,…,l;c3為常數(shù).從文獻(xiàn)[12]的證明過(guò)程可以推導(dǎo)出l是log2N級(jí)別的,即l≤O(log2N).

上述結(jié)論表明:只要度分布符合以上3類度分布的復(fù)雜網(wǎng)絡(luò)模型,在網(wǎng)絡(luò)演化的過(guò)程中,其網(wǎng)絡(luò)度序列長(zhǎng)度l的增長(zhǎng)相比節(jié)點(diǎn)數(shù)N的增長(zhǎng)是非常緩慢的;如果采用一定的網(wǎng)絡(luò)生成模型,其度序列長(zhǎng)度l與網(wǎng)絡(luò)的直徑是相關(guān)的.從而證明了網(wǎng)絡(luò)搜索的路徑長(zhǎng)度與log2N是同樣級(jí)別的.

當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)比較多時(shí),小世界網(wǎng)絡(luò)及隨機(jī)網(wǎng)絡(luò)的度分布是符合泊松分布的,但不符合前面的3類度分布規(guī)律.

2 度分布符合泊松分布的度序列特性

按照隨機(jī)圖模型的定義,當(dāng)節(jié)點(diǎn)數(shù)N比較大、節(jié)點(diǎn)之間連接的概率p比較小時(shí),隨機(jī)圖模型的度分布概率近似為

(5)

式中，c4、為常數(shù).小世界網(wǎng)絡(luò)中的SW模型[2]、NW模型[3]是基于規(guī)則網(wǎng)絡(luò)與隨機(jī)網(wǎng)絡(luò)之間,采用隨機(jī)重連或者加邊的方式生成,當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模較大時(shí),SW模型與NW模型網(wǎng)絡(luò)的度分布近似為泊松分布,即滿足式(5).下面從理論角度來(lái)分析度序列長(zhǎng)度l與節(jié)點(diǎn)數(shù)N的關(guān)系.

按照P(ki)的定義,由式(5)可得

(6)

令i=1,由等式(6)可推導(dǎo)出

(7)

由式(7)可得到常數(shù)c4的表達(dá)式,即

(8)

把式(8)中的常數(shù)c4代入式(6),可得

(9)

由式(9)可以推導(dǎo)出nki的表達(dá)式,即

(10)

同理,將式(10)的i用l替代,可推導(dǎo)出nkl的表達(dá)式為

(11)

斯特林公式給出了n!的表達(dá)式,即

(12)

(13)

由式(13)可推導(dǎo)出

(14)

由于nkl≤nk1,k1≤kl,nk1≥1,由式(14)可推導(dǎo)出

(15)

由式(15)可得

(16)

不等式(16)兩邊取以2為底的對(duì)數(shù),當(dāng)kl≥2e時(shí),可得

(17)

由不等式(17)可知,度序列長(zhǎng)度l同樣也是log2N級(jí)別的.這說(shuō)明了復(fù)雜網(wǎng)絡(luò)的度分布滿足泊松分布時(shí),文中的結(jié)論是成立的.

3 仿真驗(yàn)證

3.1 度分布符合泊松分布的復(fù)雜網(wǎng)絡(luò)模型

(18)

NW復(fù)雜網(wǎng)絡(luò)模型[3]是在規(guī)則網(wǎng)絡(luò)的基礎(chǔ)上采用“隨機(jī)化加邊”的機(jī)制,也具有小世界網(wǎng)絡(luò)特性,其度分布概率為

(19)

式中:K為節(jié)點(diǎn)左右相鄰的節(jié)點(diǎn)數(shù),為偶數(shù);p為重連概率.

在G(N,p)模型中p的取值依次取為0.015、0.015、0.012、0.010、0.010、0.008、0.008、0.005、0.005、0.003、0.003、0.003,M的取值為節(jié)點(diǎn)數(shù)的2倍,即平均度為4.在G(N,M)和G(N,p)模型中,由于網(wǎng)絡(luò)節(jié)點(diǎn)平均度的不同,度序列長(zhǎng)度l與log2N趨勢(shì)略有差別,但度序列長(zhǎng)度l還是與log2N同級(jí)別,即l≤(log2N)ε.從圖1(a)、1(b)中可以看出,1<ε<2.

WS與NW模型中K=4,p=0.03.從圖1(c)、1(d)中可知,l也是與log2N同級(jí)別,且ε<1.

3.2 度分布符合冪律分布的復(fù)雜網(wǎng)絡(luò)模型

BA模型是復(fù)雜網(wǎng)絡(luò)的主要理論模型之一,其構(gòu)建思想如下:網(wǎng)絡(luò)中有m0個(gè)節(jié)點(diǎn),每個(gè)步驟中新加入一個(gè)節(jié)點(diǎn),該節(jié)點(diǎn)與網(wǎng)絡(luò)中的m個(gè)節(jié)點(diǎn)連接,滿足m

圖1 幾種復(fù)雜網(wǎng)絡(luò)模型的度序列長(zhǎng)度與節(jié)點(diǎn)數(shù)的關(guān)系

(20)

BA模型的度分布滿足冪律分布.從圖1(e)中可知,度序列長(zhǎng)度l與log2N是同級(jí)別的,且1<ε<2.

從以上實(shí)驗(yàn)結(jié)果可以看出,小世界網(wǎng)絡(luò)模型(WS模型和NW模型)由于網(wǎng)絡(luò)的聚集系數(shù)相對(duì)比較高,度分布主要集中在一個(gè)范圍內(nèi),其度序列的長(zhǎng)度是小于log2N的,即ε<1.由于BA模型與隨機(jī)圖模型的節(jié)點(diǎn)度分布范圍比小世界網(wǎng)絡(luò)模型更廣泛,其度序列長(zhǎng)度也相對(duì)較大,因此1<ε<2.由此可知,度序列長(zhǎng)度也是衡量小世界網(wǎng)絡(luò)的一個(gè)特性,和度分布、網(wǎng)絡(luò)聚集系數(shù)一起可以更好地刻畫(huà)小世界網(wǎng)絡(luò)的特征.

4 實(shí)際數(shù)據(jù)驗(yàn)證

測(cè)試數(shù)據(jù)集包括有向網(wǎng)絡(luò)和無(wú)向網(wǎng)絡(luò).對(duì)于有向圖網(wǎng)絡(luò),首先將有向圖轉(zhuǎn)換為無(wú)向圖,并去掉圖中的自環(huán)及重邊,然后通過(guò)程序計(jì)算得到度序列長(zhǎng)度與log2N的關(guān)系數(shù)據(jù),如表1所示.從表中可以看出,現(xiàn)實(shí)網(wǎng)絡(luò)的ε值比理論推導(dǎo)稍大,主要是因?yàn)楝F(xiàn)實(shí)網(wǎng)絡(luò)不符合嚴(yán)格的理論網(wǎng)絡(luò)模型,其度分布也不符合嚴(yán)格的冪律或者指數(shù)或者泊松分布,而是多個(gè)分布函數(shù)的組合,無(wú)法將現(xiàn)實(shí)網(wǎng)絡(luò)歸結(jié)于某個(gè)理論網(wǎng)絡(luò)模型,但現(xiàn)實(shí)網(wǎng)絡(luò)往往具有小世界特性,因此其度序列長(zhǎng)度也不可能太大.從實(shí)驗(yàn)結(jié)果來(lái)分析,現(xiàn)實(shí)網(wǎng)絡(luò)的度序列長(zhǎng)度l也是與log2N同一級(jí)別,只是ε的值偏大.

5 結(jié)論

在針對(duì)度分布符合冪律分布、指數(shù)分布、擴(kuò)展冪律的度序列前期研究中,筆者得出了度序列長(zhǎng)度l與log2N是同級(jí)別的結(jié)論,文中將此結(jié)論擴(kuò)展到度分布符合泊松分布的復(fù)雜網(wǎng)絡(luò)模型的度序列長(zhǎng)度的特性,理論推導(dǎo)及實(shí)驗(yàn)仿真都證明了該結(jié)論的正確性.從現(xiàn)實(shí)的角度也可以得到該結(jié)論.盡管現(xiàn)實(shí)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)比較大,但現(xiàn)實(shí)網(wǎng)絡(luò)普遍呈現(xiàn)了平均路徑長(zhǎng)度短、聚集系數(shù)高的小世界特性.現(xiàn)實(shí)網(wǎng)絡(luò)的小世界特性導(dǎo)致網(wǎng)絡(luò)中大多數(shù)節(jié)點(diǎn)度不可能很大,而度序列長(zhǎng)度與網(wǎng)絡(luò)大小相比是小的,否則將與小世界特性相矛盾.

文中從離散數(shù)學(xué)理論嚴(yán)格證明了復(fù)雜網(wǎng)絡(luò)的度序列長(zhǎng)度l與log2N是同一級(jí)別的,該結(jié)論是否可以進(jìn)一步推廣到復(fù)雜系統(tǒng)與社會(huì)系統(tǒng)中,是值得進(jìn)一步研究的問(wèn)題.

表1 現(xiàn)實(shí)網(wǎng)絡(luò)數(shù)據(jù)1)

1)表中第1- 28行數(shù)據(jù)見(jiàn)http:∥snap.stanford.edu/data/index.html,第29-31行數(shù)據(jù)見(jiàn)www.tc.cornell.edu/myers/Data/SoftwareGraphs/index.html,第32-33行數(shù)據(jù)見(jiàn)www.cosin.org/extra/data.

[1] ERD?S P,RéNYI A.On the evolution of random graphs [J].Magyar Tud Akad Mat KutatóInt K?zl,1960,5:17- 61.[2] WATTS D J,STROGATZ S H.Collective dynamics of ‘small-world’ networks [J].Nature,1998,393(6684):440- 442.

[3] NEWMAN M E,WATTS D J.Renormalization group ana-lysis of the small-world network model [J].Physics Le-tters A,1999,263(4):341-346.

[5] LI X,CHEN G R.A local-world evolving network model [J].Physica A:Statistical Mechanics and Its Applications,2003,328(1):274- 286.

[6] 章忠志,周水庚,方錦清.復(fù)雜網(wǎng)絡(luò)確定性模型研究的最新進(jìn)展 [J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2008,5(4):29- 46.

ZHANG Zhong-zhi,ZHOU Shui-geng,FANG Jin-qing.Recent progress of deterministic models for complex networks [J].Complex Systems and Complexity Science,2008,5(4):29- 46.

[7] ZHANG Z Z,RONG L L,GUO C H.A deterministic small-world network created by edge iterations [J].Physica A:Statistical Mechanics and Its Applications,2006,363(2):567-572.

[8] XIAO W J,PARHAMI B.Cayley graphs as models of deterministic small-world networks [J].Information Proce-ssing Letters,2006,97(3):115-117.

[9] STROGATZ S H.Exploring complex networks [J].Nature,2001,410(6825):268- 276.

[10] ALBERT R,BARABSI A.Statistical mechanics of complex networks [J].Reviews of Modern Physics,2002,74(1):47.

[11] XIAO W J,LIU Y X,CHEN G R.Characterizing vertex-degree sequences in scale-free networks [J].Physica A:Statistical Mechanics and Its Applications,2014,404(24):291- 295.

[12] XIAO W J,LAI Z W,CHEN G R.Characterizing general scale-free networks by vertex-degree sequences [J].Chaos:An Interdisciplinary Journal of Nonlinear Science,2015,25(11):113111/1-3.

[13] XIAO W J,JIANG S Z,CHEN G R.A small-world model of scale-free networks:features and verifications [J].App-lied Mechanics and Materials,2011,50/51:166-170.

[14] XIAO W J,CHEN W D,PARHAMI B.On necessary conditions for scale-freedom in complex networks,with applications to computer communication systems [J].International Journal of Systems Science,2011,42(6):951-958.

[17] Jr ANDRADE 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/1- 4.

Analysis of Vertex-Degree Sequence Length of Complex Networks

XIONGYun-yan1,2XIAOWen-jun3MAOYi-jun4LAIZheng-wen1HANDong1LIMei-sheng1

(1. School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, Guangdong, China;2. Computer Engineering Department, Guangdong College of Industry and Commerce, Guangzhou 510510, Guangdong, China;3. School of Software Engineering, South China University of Technology, Guangzhou 510006, Guangdong, China;4. College of Mathematics and Informatics, South China University of Agriculture, Guangzhou 510642, Guangdong, China)

In this paper, a conclusion that the length of vertex-degree sequences is of the order log2N(Nis the number of network nodes) in the complex networks exhibiting a Poisson vertex-degree distribution, is theoretically proved. Then, by the simulation experiments on the length of the vertex-degree sequences in random networks, small world networks and scale-free networks, the conclusion is also proved to be correct. Finally, this conclusion is also confirmed in real complex networks by computing the length of the vertex-degree sequences.

complex networks; vertex-degree sequences; Poisson distribution

1000-565X(2017)01- 0074- 06

2016- 01- 07

國(guó)家自然科學(xué)基金資助項(xiàng)目(61170313)

Foundation item： Supported by the National Natural Science Foundation of China(61170313)

熊云艷(1976-)，女，在職博士生，副教授，主要從事復(fù)雜網(wǎng)絡(luò)、數(shù)據(jù)中心網(wǎng)絡(luò)研究.E-mail:yunyanx@163.com

? 通信作者： 毛宜軍(1979-)，男，博士生，主要從事大數(shù)據(jù)、圖計(jì)算研究.E-mail:yijunmao@163.com

TP 393

10.3969/j.issn.1000-565X.2017.01.011