復雜網(wǎng)絡度序列長度分析*

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

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

復雜網(wǎng)絡度序列長度分析*

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

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

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

復雜網(wǎng)絡;節(jié)點度序列;泊松分布

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

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

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

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

1 相關工作

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

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

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

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

(1)

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

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

(2)

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

l-1≤log2N/log2q

(3)

從式(3)可知:當q=2時,式(3)與BA模型中度序列長度的結論是一致的;當q>2時,因為q為常數(shù),log2N/log2q≈(log2N)ε,所以式(3)可以表示為l≤(log2N)ε,可知l與log2N是同級別的.

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

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

(4)

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

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

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

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

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

(5)

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

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

(6)

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

(7)

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

(8)

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

(9)

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

(10)

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

(11)

斯特林公式給出了n!的表達式,即

(12)

(13)

由式(13)可推導出

(14)

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

(15)

由式(15)可得

(16)

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

(17)

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

3 仿真驗證

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

(18)

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

(19)

式中:K為節(jié)點左右相鄰的節(jié)點數(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é)點數(shù)的2倍,即平均度為4.在G(N,M)和G(N,p)模型中,由于網(wǎng)絡節(jié)點平均度的不同,度序列長度l與log2N趨勢略有差別,但度序列長度l還是與log2N同級別,即l≤(log2N)ε.從圖1(a)、1(b)中可以看出,1<ε<2.

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

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

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

圖1 幾種復雜網(wǎng)絡模型的度序列長度與節(jié)點數(shù)的關系

(20)

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

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

4 實際數(shù)據(jù)驗證

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

5 結論

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

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

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

1)表中第1- 28行數(shù)據(jù)見http:∥snap.stanford.edu/data/index.html,第29-31行數(shù)據(jù)見www.tc.cornell.edu/myers/Data/SoftwareGraphs/index.html,第32-33行數(shù)據(jù)見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] 章忠志,周水庚,方錦清.復雜網(wǎng)絡確定性模型研究的最新進展 [J].復雜系統(tǒng)與復雜性科學,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

國家自然科學基金資助項目(61170313)

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

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

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

TP 393

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