楊 珉,張家玥,張達敏

(貴州大學大數(shù)據(jù)與信息工程學院,貴州貴陽550025)

復雜網(wǎng)絡(luò)拓撲結(jié)構(gòu)的網(wǎng)絡(luò)模型研究綜述*

楊 珉,張家玥,張達敏

(貴州大學大數(shù)據(jù)與信息工程學院,貴州貴陽550025)

基于復雜網(wǎng)絡(luò)拓撲結(jié)構(gòu)建模能夠有效地分析其結(jié)構(gòu)特征和傳播機理。文中從網(wǎng)絡(luò)拓撲結(jié)構(gòu)方面總結(jié)了現(xiàn)有的網(wǎng)絡(luò)拓撲基本模型,以及目前的研究狀況,具體介紹局域世界演化網(wǎng)絡(luò)、自相似性網(wǎng)絡(luò)、模塊性網(wǎng)絡(luò)、含權(quán)網(wǎng)絡(luò)等典型模型的建立過程以及研究者們在其基礎(chǔ)上的拓展研究。最后,在討論目前復雜網(wǎng)絡(luò)拓撲基本模型存在問題的同時,也提出復雜網(wǎng)絡(luò)拓撲結(jié)構(gòu)上的網(wǎng)絡(luò)模型發(fā)展的新挑戰(zhàn)。

復雜網(wǎng)絡(luò) 演化 拓撲結(jié)構(gòu) 動力學行為

0 引 言

復雜網(wǎng)絡(luò)的相關(guān)研究進入中國已經(jīng)有超過十年的時間了,其中的很多方向、分支都受到各個學科甚至很多交叉學科的廣泛關(guān)注和研究,諸如Internet、WWW、社會關(guān)系網(wǎng)絡(luò)、經(jīng)濟網(wǎng)絡(luò)、全球交通網(wǎng)絡(luò)、大型電力網(wǎng)絡(luò)、科學家合作網(wǎng)絡(luò)等[1],可以說研究這些網(wǎng)絡(luò)的工具就是復雜網(wǎng)絡(luò)。

復雜網(wǎng)絡(luò)的研究一般認為是從瑞士著名的數(shù)學家Eular開創(chuàng)圖論學科開始的,之后在相當長的一段時期沒有得到發(fā)展,直到20世紀50年代末,兩位著名的數(shù)學家Erdǒs和Rényi引出隨機圖理論,從此該發(fā)現(xiàn)在數(shù)學領(lǐng)域被公認為是開辟了復雜網(wǎng)絡(luò)的系統(tǒng)性研究。1998年小世界網(wǎng)絡(luò)[2]和1999年無標度網(wǎng)絡(luò)[3]這兩篇論文開創(chuàng)性地把現(xiàn)實世界中的網(wǎng)絡(luò)數(shù)據(jù)抽象統(tǒng)計分析,研究更加符合實際網(wǎng)絡(luò)特性的網(wǎng)絡(luò)結(jié)構(gòu)對傳播過程產(chǎn)生了重要影響,復雜網(wǎng)絡(luò)的

研究也發(fā)生了巨大的轉(zhuǎn)變[4-6]。

錢學森先生曾給出復雜網(wǎng)絡(luò)的一個定義:具有自組織、自相似、吸引子、小世界、無標度中部分或全部性質(zhì)的網(wǎng)絡(luò)稱為復雜網(wǎng)絡(luò)。當前對復雜網(wǎng)絡(luò)的研究主要集中在三方面:①各類實際網(wǎng)絡(luò)的拓撲結(jié)構(gòu)實證研究,通過分析這些網(wǎng)絡(luò)的拓撲性質(zhì),研究網(wǎng)絡(luò)演化的特征與規(guī)律;②網(wǎng)絡(luò)生成機制及演化模型的研究,確立網(wǎng)絡(luò)演化模型,模仿真實網(wǎng)絡(luò)行為;③復雜網(wǎng)絡(luò)上的動力學行為研究。研究之間并不是孤立進行的,通常是復雜網(wǎng)絡(luò)的結(jié)構(gòu)決定了動力學過程,而動力學過程反過來影響網(wǎng)絡(luò)結(jié)構(gòu)的演化。

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

對于拓撲特性分析,研究者們根據(jù)建立的模型利用圖論、動力學特性以及相關(guān)交叉學科的方法進行計算分析和仿真?；诂F(xiàn)實網(wǎng)絡(luò)存在的缺陷,更多符合實際需求的網(wǎng)絡(luò)擴展模型被相應(yīng)提出。例如,方錦清等提出隨機性擇優(yōu)和確定性擇優(yōu)相結(jié)合模型[7],史定華等提出優(yōu)勝劣汰模型[8]和對數(shù)增長模型[9],Saramaki等提出隨機游走模型[10],Krapivsky等提出非線性擇優(yōu)模型[11],Dorogovtsev等提出冪律增長模型[12],鄭蕾等提出的基于微博網(wǎng)絡(luò)的信息傳播模型[13]。

復雜網(wǎng)絡(luò)的特征一般通過度分布、平均路徑長度、簇系數(shù)、中心性、模體、社團分類、有效性、魯棒性等屬性進行度量。其中,基本特征有節(jié)點的度分布、聚類系數(shù)和平均路徑長度。本文重點闡述典型的更加符合實際的網(wǎng)絡(luò)拓撲結(jié)構(gòu)模型,進一步探索真實網(wǎng)絡(luò)的傳播機制和拓撲結(jié)構(gòu),分析和總結(jié)基本模型及其性質(zhì),提出現(xiàn)有研究中存在的問題以及展望。

1.1 局域世界演化網(wǎng)絡(luò)模型

李翔和陳關(guān)榮于2003年提出了局域世界演化網(wǎng)絡(luò)模型[14]在BA無標度模型基礎(chǔ)上做出了改進。局域世界網(wǎng)絡(luò)模型不僅保持了無標度網(wǎng)絡(luò)具有的魯棒性,而且還改進了無標度網(wǎng)絡(luò)面對惡意攻擊所存在的脆弱性。局域世界網(wǎng)絡(luò)模型中保留BA模型中的增長機制,也就是在每一個單位時間步長t內(nèi),加入一個新節(jié)點和m條邊;而前者的全局優(yōu)先連接機制被局部優(yōu)先連接機制所替代,即新加入的節(jié)點從局域世界(LW)中按照擇優(yōu)連接概率選擇M個 (M≥m)節(jié)點進行連接,而不是從整個網(wǎng)絡(luò)中選擇節(jié)點[15]。新加入的節(jié)點根據(jù)擇優(yōu)連接概率:

式中,m0為初始網(wǎng)絡(luò)的節(jié)點數(shù),M在局域世界中的個數(shù)要滿足m≤M≤m0+t,即當M/m的值1≤M/m≤范圍內(nèi)增加時,網(wǎng)絡(luò)中節(jié)點度的分布顯示出由指數(shù)分布向冪律分布的過渡過程。局域世界網(wǎng)絡(luò)中的節(jié)點往往比無標度網(wǎng)路中節(jié)點數(shù)目少,即局域世界網(wǎng)絡(luò)中的度分布相較于隨機網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)、無標度網(wǎng)絡(luò)中要更均勻[16]。

很多研究者在基于BA無標度網(wǎng)絡(luò)的局域世界網(wǎng)絡(luò)演化模型的基礎(chǔ)上又進行改進。Xuan等首先通過節(jié)點之間度的相關(guān)性大小來判斷局域世界范圍的大小后,然后選取其中相關(guān)性最大的節(jié)點作為新的節(jié)點,并且通過建立局域世界網(wǎng)絡(luò)模型和數(shù)值仿真模擬,得出度分布呈冪率分布等規(guī)律[17]。Gu等在局域世界中通過改變連接概率值和局域范圍的大小構(gòu)造出LWD網(wǎng)絡(luò)模型,同時還研究得出模型度分布、聚類系數(shù)、平均路徑長度等參數(shù)的變化[18]。還有田立新等構(gòu)造出一個基于二分網(wǎng)絡(luò)的類局域世界網(wǎng)絡(luò)模型,

式中,ki(max)(t)為在t時刻節(jié)點i的飽和度,〈k(t)〉指的是在t時刻ki(max)節(jié)點平均度值,ki(t)指的是在t時刻節(jié)點i的度值。該網(wǎng)絡(luò)模型根據(jù)節(jié)點的度和飽和度兩項指標為標準決定該節(jié)點是否添加新節(jié)點,即是由舊節(jié)點本身的承載能力判斷之后被動生成的,故稱類局域世界模型[19]。

1.2 網(wǎng)絡(luò)的自相似性

2005年Song等在分析各種實際網(wǎng)絡(luò)后發(fā)現(xiàn):很多實際網(wǎng)絡(luò)系統(tǒng),諸如社會網(wǎng)絡(luò)、萬維網(wǎng)、細胞網(wǎng)絡(luò)和蛋白質(zhì)交互網(wǎng)絡(luò)等,在所有長度標度下具有自相似性結(jié)構(gòu)[20]。所謂自相似性(self-similarity),即局部在某種意義上與整體相似,即就是是分形(fractal)的基本特征。復雜網(wǎng)絡(luò)的小世界特征表明L∝ln(N)(L為網(wǎng)絡(luò)平均路徑長度,N為網(wǎng)絡(luò)規(guī)模),其

等價表示N∝eL/L0(常數(shù)L0為特征長度),由此可發(fā)現(xiàn)網(wǎng)絡(luò)規(guī)模是網(wǎng)絡(luò)平均路徑長度的指數(shù)函數(shù),而自相似性則滿足某種冪律關(guān)系[21]。

分數(shù)維這一概念隨著自相似性原則的提出也引起了人們的注意。計算自相似分形維數(shù)的最常用方法之一就是盒記數(shù)法,采用該方法計算幾何圖形維數(shù)的思路:通過盒子(邊長為lB)覆蓋該圖形,同時統(tǒng)計最少的盒子數(shù)NB(lB)直到完全覆蓋該圖形。這里的盒子一維是線段表示,二維是正方形表示,三維是立方體表示,盒子的尺寸即為lB。計算圖形維數(shù)的近似公式:

等價地有

然而復雜網(wǎng)絡(luò)中節(jié)點間的距離表示的并非歐氏距離,而是節(jié)點間最短路徑包含的邊的數(shù)目。并且規(guī)定盒子尺寸lB:盒子中任意兩個節(jié)點之間的距離都小于lB,一組不重疊的盒子即可重新構(gòu)成一個完整的網(wǎng)絡(luò),即網(wǎng)絡(luò)中所有的節(jié)點都有且僅有一個盒子覆蓋。而大規(guī)模復雜網(wǎng)絡(luò)中擁有許多不盡相同的分割方式,其中的分數(shù)維計算式(3)或式(4)中要求NB(lB)是覆蓋網(wǎng)絡(luò)的最少的盒子數(shù),然而找到覆蓋網(wǎng)絡(luò)所需要的最少的盒子集合的問題與經(jīng)典的圖作色問題類似,相當于一個NP完全問題,也是復雜網(wǎng)絡(luò)運用盒記數(shù)法的主要難點。

目前復雜網(wǎng)絡(luò)分形大體上可分為兩種研究方法:幾何法和代數(shù)法。其中盒子覆蓋法即為基本的幾何法,比如:緊湊盒子燃燒算法、MEMB算法、貪心策略圖著色算法等;代數(shù)法主要是基于網(wǎng)絡(luò)結(jié)構(gòu)與網(wǎng)絡(luò)譜的特殊關(guān)系,研究不同網(wǎng)絡(luò)結(jié)構(gòu)導致的網(wǎng)絡(luò)譜特征。姚燦中等創(chuàng)新地將計算機算法中的welch powell法應(yīng)用到目前盒子覆蓋算法中,有效地解決了目前盒子覆蓋方法中的瓶頸問題,提高了算法效率改進了算法性能[22]。

1.3 模塊性網(wǎng)絡(luò)

一般而言,模塊(module)是指一組物理上或功能上連接在一起的、共同完成一個相對獨立功能的節(jié)點。模塊存在于實際系統(tǒng)中,比如“物以類聚,人以群分”,社團在實際系統(tǒng)中表現(xiàn)為節(jié)點之間關(guān)系較為緊密、節(jié)點的特性相同或較為相近,即社團內(nèi)部各節(jié)點之間表現(xiàn)關(guān)系相對緊密,而社團內(nèi)部節(jié)點和外部節(jié)點之間關(guān)系相對疏遠。網(wǎng)絡(luò)的高聚類性表明在局部可能包含由高度連接的節(jié)點組構(gòu)成的子圖,模塊度(modularity)的概念被Newman等首次引入,該函數(shù)是社團劃分優(yōu)劣程度的量化標準[23]。模塊度Q的定義:

式中,A是圖的鄰接矩陣,m是圖的邊數(shù)目,Pij代表在隨機圖中的點i與點j之間期望的邊數(shù)目,函數(shù)δ表示如果點i與點j在同一個社團中(Ci=Cj),那么函數(shù)值為1,否則為0。

基于模塊度的社團發(fā)現(xiàn)的算法一時間也隨著模塊度定義的提出涌現(xiàn)出來,社團發(fā)現(xiàn)與分割問題很相似,盡管是NP難題,但研究者們也提出了許多行之有效的解決辦法。其中最具代表性的算法是由Newman提出的凝聚算法,基本思想是:首先把所有節(jié)點都看作是單獨的社團,然后每次迭代的時候選擇兩個Q值最大的社團合并,直到整個網(wǎng)絡(luò)所有的節(jié)點都被凝聚至一個社團之內(nèi)。采用凝聚算法后能夠得到一個社團結(jié)構(gòu)分解的樹狀圖,最終社團結(jié)構(gòu)就是從所有的社團里再選擇一個局部最大的Q值社團[23]。隨后,Newman和Girvan還提出了與凝聚算法思路完全相反的分裂算法,基本思想是:首先自頂向下不斷地從網(wǎng)絡(luò)中刪除邊的信息中心度(edge centrality)最大的邊,直到又退化為每個節(jié)點單獨存在的社團,然后在上一步的過程中找出對應(yīng)Q值最大時的結(jié)果。通常邊的信息中心度的值取為邊的最短路徑數(shù)[24]。還有Duch等提出的基于直接尋優(yōu)算法思路的EO算法,基本思想是:首先引入一個新的局部變量,即每個節(jié)點所對應(yīng)的模塊度Q值貢獻大小,通過初始的隨機劃分后,采用貪婪策略局部變量得以調(diào)整從而全局目標函數(shù)Q值也得以提高[25]。另外,還有Kernighan-Lin算法、模擬退火算法、極值優(yōu)化算法的啟發(fā)式搜索算法等。

很多情況下,劃分網(wǎng)絡(luò)的社團中,許多節(jié)點不僅屬于一個社團而且是多個社團,該情形下的社團叫做重疊社團(Overlapping Community)。典型的重疊社區(qū)挖掘算法有:Palla等人提出的派系過濾算法(CPM,Clique Percolation Method)、Lancichinetti等人提出的基于局部擴展算法(LFM)、Lee等人提出的

貪婪團擴張算法(GCE,Greedy Clique Expansion)、劉大有等人在原始網(wǎng)絡(luò)與相應(yīng)的退火網(wǎng)絡(luò)的結(jié)合成的集成網(wǎng)絡(luò)上,提出重疊社區(qū)挖掘算法(UEOC,Unfold and ExtractOverlapping Communities)。

1.4 含權(quán)網(wǎng)絡(luò)

在實際復雜系統(tǒng)中絕大多數(shù)網(wǎng)絡(luò)的權(quán)值并不是0或1,節(jié)點權(quán)和連邊權(quán)兩個概念隨著含權(quán)網(wǎng)絡(luò)的提出也應(yīng)運而生,節(jié)點權(quán)用于描繪節(jié)點的重要程度,而連邊權(quán)用于描繪節(jié)點間的作用強度。邊權(quán)所描繪的節(jié)點間的耦合關(guān)系多種多樣,諸如,交通網(wǎng)絡(luò)中的道路流量、Internet網(wǎng)絡(luò)中兩個路由器或兩個域之間的帶寬流量、社會網(wǎng)絡(luò)中朋友的親疏之分、科研合作網(wǎng)絡(luò)中科學家合作的次數(shù)等,真實網(wǎng)絡(luò)特性包括拓撲結(jié)構(gòu)、動力學特征都能夠從含權(quán)網(wǎng)絡(luò)中反映出來。

Yook等提出的網(wǎng)絡(luò)模型演化規(guī)則遵循BA無標度模型,另外在演化規(guī)則的基礎(chǔ)上給每條新加入的邊賦權(quán),稱為考慮權(quán)重的無標度網(wǎng)絡(luò)演化模型(YJBT模型)[26]。Barrat等提出邊點權(quán)值動態(tài)演化模型(BBV,Barrat-Barthelemy-Vespignani),該模型綜合考慮點強度與邊權(quán)值加強機制,BBV模型的動態(tài)演化利用權(quán)驅(qū)動方式得以實現(xiàn),從而得出結(jié)論:節(jié)點強度、邊權(quán)值和度都實現(xiàn)了冪率分布[27],其演化算法如下:網(wǎng)絡(luò)初始節(jié)點m0,初始邊隨機連接,每一個時間步長內(nèi)帶有m條邊的新節(jié)點j(按照節(jié)點強度擇優(yōu)方式)連接到初始網(wǎng)絡(luò)中,且新邊的權(quán)值為w0。新邊lij的加入會造成邊權(quán)(按照邊權(quán)值擇優(yōu)方式)重新分配,權(quán)值變化如下:

式中,Δwij=,式中si是節(jié)點強度,定義為:

式中,Ni是節(jié)點i的鄰點集合。

我們可以把含權(quán)網(wǎng)絡(luò)演化模型看作是網(wǎng)絡(luò)拓撲結(jié)構(gòu)與其承載的業(yè)務(wù)有著共生演化的耦合關(guān)系。不僅是BBV模型,還有TDE模型[28]把網(wǎng)絡(luò)業(yè)務(wù)耦合進網(wǎng)絡(luò)拓撲演化過程,得到網(wǎng)絡(luò)的度、強度、權(quán)重的冪律分布以及非相稱混合性和高聚集性等特征,描繪出更加符合真實工程網(wǎng)絡(luò)的特征。

2 當前復雜網(wǎng)絡(luò)模型存在的問題及展望

1)復雜網(wǎng)絡(luò)的建模?；诟叨葎討B(tài)的、過程的方法會逐漸取代基于固定結(jié)構(gòu)的、靜態(tài)的、線性的復雜網(wǎng)絡(luò)研究。動態(tài)的演化過程盡管具體構(gòu)造機理互不相同,但是它們基本上都遵循擇優(yōu)連接的機制。然而,已經(jīng)有學者證實真實網(wǎng)絡(luò)在演化過程中并不是完全遵守嚴格的擇優(yōu)機制,而是隨機和擇優(yōu)兩種機制共同作用的結(jié)果[29]。還有許多實際網(wǎng)絡(luò)是由多個個體或子系統(tǒng)由于相互作用而融合為網(wǎng)絡(luò),這時就需要新的度量指標和特定的新型工具來描述和模擬網(wǎng)絡(luò)間的相互作用和影響。復雜網(wǎng)絡(luò)的理論模型以及網(wǎng)絡(luò)的拓撲構(gòu)造方法、網(wǎng)絡(luò)特征參數(shù)度量還需要更加深入研究。

2)含權(quán)網(wǎng)絡(luò)的權(quán)重與拓撲結(jié)構(gòu)。節(jié)點與節(jié)點間的最短路徑可由權(quán)重隨機化直接影響,從而影響到點、邊介數(shù),因此網(wǎng)絡(luò)的全局拓撲結(jié)構(gòu)特征僅僅利用權(quán)重隨機化就可以改變。方錦清等在對實際網(wǎng)絡(luò)(包括恒河猴網(wǎng)絡(luò)、經(jīng)濟物理科學家合作網(wǎng)絡(luò)等)進行了多次劃分,發(fā)現(xiàn)加權(quán)網(wǎng)絡(luò)、無權(quán)網(wǎng)絡(luò)和反權(quán)網(wǎng)絡(luò)之間社團結(jié)構(gòu)具有顯著差別,認為權(quán)重與邊的匹配方式對于社團結(jié)構(gòu)劃分具有重要的影響。然而現(xiàn)實網(wǎng)絡(luò)中(比如交通流量)在網(wǎng)絡(luò)負載足夠的情況下,網(wǎng)絡(luò)拓撲結(jié)構(gòu)不一定會隨著網(wǎng)絡(luò)權(quán)重的變化而變化,因此關(guān)于含權(quán)網(wǎng)絡(luò)權(quán)重與拓撲結(jié)構(gòu)的研究還有很多實際問題值得探討[30]。

3)復雜網(wǎng)絡(luò)演化的復雜性。某些真實網(wǎng)絡(luò)系統(tǒng)中出現(xiàn)的一些復雜現(xiàn)象,有的還沒得到很合理的解釋,其成因也缺乏研究,比如復雜網(wǎng)絡(luò)的自組織臨界性;網(wǎng)絡(luò)的拓撲結(jié)構(gòu)變化對網(wǎng)絡(luò)動力學行為的影響也少有研究,因此帶有反饋功能的自適應(yīng)網(wǎng)絡(luò)的動力學行為值得深入探索。許多研究成果單從物理學角度并沒有考慮網(wǎng)絡(luò)的實際功能和現(xiàn)實條件的限制,特別是針對網(wǎng)絡(luò)工程。許多關(guān)于應(yīng)用方面的文獻敘述的都是在某個方面對某個特殊領(lǐng)域的網(wǎng)絡(luò)化,并進行網(wǎng)絡(luò)的結(jié)構(gòu)分析與定性討論,還需要一些深入的應(yīng)用研究如何根據(jù)具體的應(yīng)用場景有針對性地選擇合適的方法。近年來眾多的研究成果還停留在從真實網(wǎng)絡(luò)到理論模型的建立和分析上,想要把科學研究的結(jié)果返回到網(wǎng)絡(luò)工程去檢驗和實現(xiàn),還有相當長的一段路要走。

4)復雜網(wǎng)絡(luò)的規(guī)模。由于大數(shù)據(jù)時代的到來,復雜網(wǎng)絡(luò)的規(guī)模也日益擴大,目前以單機資源為主的復雜網(wǎng)絡(luò)研究迎來了巨大的挑戰(zhàn)。不管是復雜網(wǎng)

絡(luò)的數(shù)據(jù)存儲還是大型運算,即使單機配置了更大容量的存儲設(shè)備和更高處理能力的處理器,其結(jié)果也收效甚微。一個有效的解決辦法就是采用由多臺單機組成的集群進行分布式存儲與處理;另一種解決辦法是利用云計算技術(shù),在云計算的環(huán)境下處理我們的任務(wù)既提升了研究的高度、提高了工作的效率,也增加了技術(shù)的靈活性。在云計算的環(huán)境下,例如Map Reduce、Erlang等編程框架也可以用于實現(xiàn)任務(wù)算法。

3 結(jié) 語

基于復雜網(wǎng)絡(luò)理論的拓撲演化能夠從網(wǎng)絡(luò)拓撲的角度揭示復雜網(wǎng)絡(luò)結(jié)構(gòu)特征對復雜網(wǎng)絡(luò)本身的影響。復雜網(wǎng)絡(luò)是物理學、數(shù)學、計算機科學、生物學、社會學等學科之間的橋梁。如,醫(yī)學家希望了解傳染病是如何在人群中傳播的并希望找到有效的預防和控制策略;社會學家關(guān)心謠言、輿論觀點等信息是如何在社會上傳播的;網(wǎng)絡(luò)安全專家關(guān)心各種計算機病毒是如何在Internet上傳播的。研究復雜網(wǎng)絡(luò)模型可以有效地分析傳播動力學行為及度量指標,從而提出相應(yīng)有效的防御和控制策略,進而達到降低網(wǎng)絡(luò)安全風險、提高網(wǎng)絡(luò)運行效率、優(yōu)化網(wǎng)絡(luò)設(shè)計結(jié)構(gòu)等現(xiàn)實目的。論文中錯漏和不妥之處在所難免,敬請專家批評指正。

[1] 周濤,張子柯,陳關(guān)榮,等.復雜網(wǎng)絡(luò)研究的機遇與挑戰(zhàn)[J].電子科技大學學報,2014,43(01):1-5.

ZHOU Tao,ZHANG Zi-Ke,CHEN Guan-rong,et al.The Opportunities and Challenges of Complex Network Research[J].Journal of University of Electronic Science and Technology of China,2014,43(1):1-5.

[2] Watts D J,Strogatz S H.Collective Dynamics of Small-World Networks[J].Nature,1998,393(6684):440-442.

[3] Barabási A L,Albert R.Emergence of Scaling in Random Networks[J].Science,1999(286):509-512.

[4] 方錦清,汪小帆,鄭志剛.非線性網(wǎng)絡(luò)的動力學復雜性研究[J].物理學進展,2009,29(01):1-74.

FANG Jin-qing,WANG Xiao-fang,ZHENG Zhi-gang. Dynamical Complexity of Nonlinear Networks[J].Progress in Physics,2009,29(1):1-74.

[5] SHID H,LIU L,ZHU SX,et al.Degree distribution of evolving networks[J].Europhysics letter,2006,76 (04):10315-10316.

[6] SHID H,CHEN Q H,LIU L M.Markov chain-based Numerical Method for Degree Distribution of Growing Networks[J].Physical Review E,2005,(71):036140-036148.

[7] Saramaki J,Kaski K.Scale-free Networks Generated by Random Walkers[J].Physica A,2004,341(11):80-86.

[8] Krapivsky P L,Redner S,Leyvraz F.Connectivity of Growing Random Networks[J].Physics Review Letters, 2000,85(21):4629-4632.

[9] Dorogovtsev S N,Mendes J F F.Effect of the Accelerating Growth of Communication Networks on Their Structure[J]. Physical Review E,2001,63(06):025101-025104.

[10] 周濤,韓筱璞,閆小勇,等.人類行為時空特性的統(tǒng)計力學[J].電子科技大學學報,2013,42(07):481-540.

ZHOU Tao,HAN Xiao-pu,YAN Xiao-yong,et al.Statistical Mechanics of the Temporal Characteristics of Human Behavior[J].University of Electronic Science and Technology,2013,42(7):481-540.

[11] 陳關(guān)榮.復雜動態(tài)網(wǎng)絡(luò)環(huán)境下控制理論遇到的問題與挑戰(zhàn)[J].自動化學報,2013,39(04):312-321.

CHEN Guan-rong,Issues and Challenges of Control Theory based on a Complex Dynam ic Network Environment.Acta Automatica Sinica,2013,39(4):312-321.

[12] Nepusz T,Vicsek T.Controlling Edge Dynamics in Complex Networks[J].Nature Physics,2012,8(07):568-573.

[13] 鄭蕾,李生紅.基于微博網(wǎng)絡(luò)的信息傳播模型[J].通信技術(shù),2012,45(02):39-41.

ZHENG Lei,LISheng-hong.A Novel Information Diffusion Model based on Microblog Network[J].Communications Technology,2012,45(2):39-41.

[14] LIX,CHENG R.A Local-world Evolving Network Model [J].Physics Letters A,2003,328(02):287-296.

[15] 許丹,李翔,陳關(guān)榮.局域世界復雜網(wǎng)絡(luò)中的病毒傳播及免疫控制[J].控制與決策,2006,21(07):817-820.

Xu D,Li X,Chen G R.Local World Complex Network of Transmission of the Virus and Immune Control[J]. Control and Decision,2006,21(7):817-820.

[16] 汪小帆,李翔,陳關(guān)榮.復雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京:清華大學出版社,2006:4-5.

WANG Xiao-fang,LI Xiang,CHEN Guan-rong.Complex Network Theory and its Application[M].Beijing: Tsinghua University Press,2006:4-5.

[17] XUAN Q,LIY,WU T J.A Local-World Network Model based on Inter-node Correlation Degree[J].Physica A, 2007(378):561-572.

[18] GU Y Y,SUN JT.A Local-World node Deleting Evolving Network Model[J].Physics Letters A,2008,372 (25):4564-4568.

[19] 田立新,賀瑩環(huán),黃益.一種新型二分網(wǎng)絡(luò)類局域世界演化模型[J].物理學報,2012,61(22):228903.

TIAN Li-xin,JIA Ying-huan,HUANG Yi.A New Class of LocalWorld Bipartite Network Evolution Model[J]. Physics,2012,61(22):228903.

[20] SONG C,Jalvin S,Makse H A.Self-similarity of Complex Networks[J].Nature,2005(433):392-395.

[21] 王江濤,楊建梅.復雜網(wǎng)絡(luò)的分形研究方法研究[J].復雜系統(tǒng)與復雜性科學,2013,10(04):1-7.

WANG Jiang-tao,YANG Jian-mei.Fractal Study of Complex Networks Research Methods[J].Complex Systems and Complexity Science,2013,10(4):1-7.

[22] 姚燦中,楊建梅.復雜網(wǎng)絡(luò)分形的盒維數(shù)改進算法[J].計算機工程與應(yīng)用,2010,46(08):5-7.

YAO Can-zhong,YANG Jian-mei.Box Fractal Dimension of Complex Networks Improved Algorithm[J].Computer Engineering and Applications,2010,46(8):5-7.

[23] Newman M E J.Fast Algorithm for Detecting Community Structure in Networks[J].Physical Review E,2004, 69(06):066133.

[24] Newman M E J,Girvan M.Finding and Evaluating Community Structure in Networks[J].Physical Review E, 2004,69(02):026113-026128.

[25] Duch J,Arenas A.Community Detection in Complex Networks Using External Optimization[J].Physical Review E,2005,72(07):027104.

[26] Yook SH,Jeong H,Barabási A L.Weighted Evolving Networks[J].Physical Review Letters,2001,86(25): 5835-5838.

[27] Barabási A L,Barthelemy M,Vespignani A.Weighted Evolving Networks:Coupling Topology and Weight Dynamics[J].Physical Review Letters,2004,92(22): 228701.

[28] 汪秉宏,王文旭,周濤.交通流驅(qū)動的含權(quán)網(wǎng)絡(luò)[J].物理,2006,35(04):304-310.

WANG Bing-hong,WANG Wen-xun,ZHOU Tao.A Weighted Complex Network Model Driven by Traffic Flow[J].Physics,2006,35(4):304-310.

[29] 蔣國平,宋玉蓉,鞏永旺.基于復雜網(wǎng)絡(luò)結(jié)構(gòu)特征的病毒傳播研究綜述[J].南京郵電大學學報:自然科學版,2012,32(05):1-5.

JIANG Guo-ping,SONG Yu-rong,GONG Yong-wang. Summary based on Complex Structural Characteristics of the Network Transmission of the Virus[J].Nanjing University of Posts and Telecommunications:Natural Science,2012,32(5):1-5.

[30] 呂琳媛,陸君安,張子柯,等.復雜網(wǎng)絡(luò)觀察[J].復雜系統(tǒng)與復雜性科學,2010,7(2-3):173-187.

LV Lin-yuan,LU Jun-an,ZHANG Zi-ke,et al.Looking into Complex Networks[J].Complex Systems and Complexity Science,2010,7(2-3):173-187.

楊 珉(1989—),女,碩士研究生,主要研究方向為復雜網(wǎng)絡(luò);

YANG Min(1989-),female,graduate student,majoring in complex networks.

張家玥(1988—),女,碩士研究生,主要研究方向為復雜網(wǎng)絡(luò);

ZHANG Jia-yue(1989-),female,graduate student,majoring in complex networks.

張達敏(1967—),男,教授,主要研究方向為計算機應(yīng)用技術(shù)、網(wǎng)絡(luò)擁塞控制、病毒傳播機制。

ZHANG Da-min(1967-),male,professor,majoring in computer application technology,network congestion control and virus propagationmechanisms.

Overview on Network Models of Complex Networks Topology Structure

YANGMin,ZHANG Jia-yue,ZHANG Da-min
(College of Big Data and Information Engineering,Guizhou University,Guiyang Guizhou 550025,China)

Modeling based on complex network topology structure could effectively analyze its structural characteristics and propagationmechanism.In terms of network topology structure,this paper summarizes the basic models of existing network topology and the research status.Then it introduces in detail the setup procedure and research extension of several typicalmodels,such as local-world evolving network,the self -similarity network,themodule network,the weighted network.Fianlly,the current issues of complex network topology basic model are discussed,and meanwhile,the new challenges in the development of network model on complex network topology structure are also pointed out in this paper.

complex network;evolution;topology;dynamic behavior

TP393

A

1002-0802(2014)12-1354-06

10.3969/j.issn.1002-0802.2014.12.002

2014-09-12;

2014-10-21 Received date：2014-09-12;Revised date：2014-10-21

貴州省省委組織部項目(No.TZJF-2011-37);貴州省合作計劃項目([2012]7002號);貴州大學研究生創(chuàng)新基金項目(研理工2014005)

FoundationItem:Guizhou Provincial Party Committee Organization Department of the Project(TZJF-2011-37),Cooperation Projects of Guizhou Province([2012]No.7002),Guizhou University Graduate Innovation Fund(Research of Technology 2014005)