基于BA無標(biāo)度的復(fù)雜有向網(wǎng)絡(luò)演化模型

馬秀娟

（青海師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，青海 西寧 810008）

當(dāng)前，各國研究人員在無向網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征，建立無向網(wǎng)絡(luò)模型以幫助人們理解真實(shí)系統(tǒng)中各種宏觀性質(zhì)的微觀生成機(jī)制，研究具有不同結(jié)構(gòu)的無向網(wǎng)絡(luò)中發(fā)生的各種動(dòng)力學(xué)過程的特征，比如研究流行病的傳播行為在無標(biāo)度網(wǎng)絡(luò)和指數(shù)網(wǎng)絡(luò)中分別具有什么特征等方面已經(jīng)取得了很大的進(jìn)展，獲得了許多令人興奮的結(jié)果[1]。但以上研究大多是基于無向網(wǎng)絡(luò)的，然而現(xiàn)實(shí)世界中許多復(fù)雜系統(tǒng)更適合于利用有向網(wǎng)絡(luò)來表示和研究，這些復(fù)雜系統(tǒng)廣泛的存在于科技、信息、社會(huì)及生物領(lǐng)域中，于是對(duì)有向網(wǎng)絡(luò)基本理論及其應(yīng)用的研究具有重要的實(shí)際意義。近年來，研究者們對(duì)有向網(wǎng)絡(luò)進(jìn)行了相對(duì)廣泛的研究，他們通過實(shí)證萬維網(wǎng)、細(xì)胞網(wǎng)絡(luò)、電話網(wǎng)、引文網(wǎng)及食物網(wǎng)等有向網(wǎng)絡(luò)而發(fā)現(xiàn)了它們的一些特征，并在此基礎(chǔ)上提出了一些有向網(wǎng)絡(luò)模型，研究了這些模型的特點(diǎn)及其簡單應(yīng)用[2-15]。例如，B.Tadic[12]等人提出了一個(gè)表示W(wǎng)WW網(wǎng)的有向網(wǎng)絡(luò)模型；A.Ramezanpour[13]等人對(duì)發(fā)生在有向網(wǎng)絡(luò)中的傳播進(jìn)程進(jìn)行了研究；N.Schwartz[14]等人研究了有向無標(biāo)度網(wǎng)絡(luò)中的逾透問題；日本的TetsuroMurai[15]等人對(duì)有向網(wǎng)絡(luò)的譜的性質(zhì)進(jìn)行了初步的研究。

近年來，隨著對(duì)有向網(wǎng)絡(luò)研究的逐步深入，研究者發(fā)現(xiàn)對(duì)有向網(wǎng)絡(luò)的研究將有助于人類對(duì)與有向網(wǎng)絡(luò)相關(guān)的許多領(lǐng)域有更深入的理解。對(duì)在信息通信、網(wǎng)絡(luò)搜索、信號(hào)傳輸、傳染病控制，網(wǎng)絡(luò)的安全性和可靠性等方面都具有重要而深遠(yuǎn)的意義[16-20]。

1999年 Barabási和 Albert提出 Scale-free （無標(biāo)度）網(wǎng)絡(luò)模型[21]。與古典模型相比，這種模型較好地解釋了一些實(shí)際網(wǎng)絡(luò)（如因特網(wǎng)和演員合作網(wǎng)等）的特性。研究人員對(duì)大量的實(shí)際網(wǎng)絡(luò)進(jìn)行了實(shí)證分析[22，23]，發(fā)現(xiàn)許多網(wǎng)絡(luò)都具有無標(biāo)度的特性。

上述網(wǎng)絡(luò)模型是基于無向網(wǎng)絡(luò)建立的，文中根據(jù)BA無標(biāo)度網(wǎng)絡(luò)模型提出了一種具有無標(biāo)度特性的有向網(wǎng)絡(luò)演化模型，并設(shè)計(jì)程序進(jìn)行了仿真實(shí)驗(yàn)，對(duì)有向網(wǎng)絡(luò)的度分布進(jìn)行了分析，結(jié)果表明，利用文中提出的有向網(wǎng)絡(luò)演化模型生成的復(fù)雜有向網(wǎng)絡(luò)的度分布符合冪律分布，能有效的模擬現(xiàn)實(shí)世界的具有無標(biāo)度特性的復(fù)雜有向網(wǎng)絡(luò)，可以在此模型上展開對(duì)復(fù)雜有向網(wǎng)絡(luò)的其他相關(guān)拓?fù)湫再|(zhì)的分析及研究。

1 有向網(wǎng)絡(luò)及其相關(guān)概念

1.1 有向網(wǎng)絡(luò)

一個(gè)具體的網(wǎng)絡(luò)可以抽象為一個(gè)由點(diǎn)集V邊集E組成的圖G=（V，E）。 節(jié)點(diǎn)數(shù)記為N=|V|，邊數(shù)記為M=|E|，E中每條邊都有V中一對(duì)頂點(diǎn)與之相對(duì)應(yīng)，如果任意點(diǎn)對(duì)（i，j）與（j，i）對(duì)應(yīng)同一條邊，則該網(wǎng)絡(luò)成為無向網(wǎng)絡(luò)（undirected network），否則稱為有向網(wǎng)絡(luò)（directed network）[24]。圖1給出了兩種不同類型的網(wǎng)絡(luò)。

圖1 不同類型網(wǎng)絡(luò)結(jié)構(gòu)圖Fig.1 Different types of network structure

1.2 有向網(wǎng)絡(luò)的度、出度、入度和鄰接矩陣

節(jié)點(diǎn)i的度deg ree（i）定義為與該節(jié)點(diǎn)連接的其他節(jié)點(diǎn)的數(shù)目[25]。有向網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)的度分為出度（out-degree）和入度（in-degree）。節(jié)點(diǎn)的出度是指以該節(jié)點(diǎn)為弧尾指向其他節(jié)點(diǎn)的邊的數(shù)目，記作deg-（i）-；節(jié)點(diǎn)的入度是指以該節(jié)點(diǎn)為弧頭由其他節(jié)點(diǎn)指向該節(jié)點(diǎn)的邊的數(shù)目，記作deg+（i）。特別地，在有向網(wǎng)絡(luò)中 deg ree（i）=deg+（i）+deg-（i）。 從直觀來看，一個(gè)節(jié)點(diǎn)的度越大就意味著這個(gè)節(jié)點(diǎn)在某種意義下相對(duì)重要。

設(shè)G是含有P個(gè)節(jié)點(diǎn) （或頂點(diǎn)），q條有向邊的有向網(wǎng)絡(luò)。令

則稱由元素 mij=（i=1，2，…p，j=1，2，…q）所構(gòu)成 p×p 的矩陣為有向網(wǎng)絡(luò)G的鄰接矩陣，記作D。

2 BA無標(biāo)度復(fù)雜有向網(wǎng)絡(luò)演化模型

1999年Barabási和Albert[21]提出了一個(gè)以增長和擇優(yōu)連接機(jī)理演化的無標(biāo)度網(wǎng)絡(luò)模型，它揭示了各類現(xiàn)實(shí)網(wǎng)絡(luò)最普遍的現(xiàn)象，但該模型只是一個(gè)無向的網(wǎng)絡(luò)模型，它無法體現(xiàn)有向網(wǎng)絡(luò)的一些主要特性，為了研究有向網(wǎng)絡(luò)的相關(guān)性質(zhì)，需要建立有向網(wǎng)絡(luò)的動(dòng)態(tài)演化模型以模擬現(xiàn)實(shí)世界中的復(fù)雜有向網(wǎng)絡(luò)。文中在前人提出的BA無標(biāo)度網(wǎng)絡(luò)模型的基礎(chǔ)之上提出了具有無標(biāo)度特性的復(fù)雜有向網(wǎng)絡(luò)演化模型。具體演化過程如下：

1）初始網(wǎng)絡(luò)：初始給定m0個(gè)節(jié)點(diǎn)，m0條有向邊，首尾連接，保證網(wǎng)絡(luò)的連通性；固定網(wǎng)絡(luò)的規(guī)模為N。

2）增長機(jī)制：每一時(shí)刻將N-m0中的一個(gè)節(jié)點(diǎn)s作為新節(jié)點(diǎn)加入到有向網(wǎng)絡(luò)中。為了保證有向網(wǎng)絡(luò)的連通性，結(jié)點(diǎn)s連入網(wǎng)絡(luò)時(shí)，增加以結(jié)點(diǎn)s為弧尾的min條入邊和以結(jié)點(diǎn)s為弧頭的mout條出邊；網(wǎng)絡(luò)中不允許重連邊，也不允許自身連邊；新節(jié)點(diǎn)連接到網(wǎng)絡(luò)后，N減1；

3）擇優(yōu)機(jī)制：新節(jié)點(diǎn)s連入網(wǎng)絡(luò)時(shí)，將與網(wǎng)絡(luò)中的已有結(jié)點(diǎn)進(jìn)行連接，由于網(wǎng)絡(luò)是一個(gè)連通的復(fù)雜有向網(wǎng)絡(luò)，因此連接時(shí)考慮如下兩個(gè)方面：

4）輸出數(shù)據(jù)：輸出最終得到的N個(gè)節(jié)點(diǎn)的鄰接矩陣，該矩陣表示了利用上述演化模型生成的規(guī)模為N的復(fù)雜有向網(wǎng)絡(luò)，同時(shí)輸出該有向網(wǎng)絡(luò)結(jié)點(diǎn)的度分布圖，有向網(wǎng)絡(luò)中結(jié)點(diǎn)的度為 deg ree（i）=deg+（i）+deg-（i），（其中 deg+（i）表示結(jié)點(diǎn)i的入度，deg-（i）為結(jié)點(diǎn) i的出度）。

圖 2 顯示了當(dāng) N=5，m0=4，min=3，mout=1 時(shí)的 BA 無標(biāo)度有向網(wǎng)絡(luò)的演化過程。

圖 2 BA 無標(biāo)度有向網(wǎng)絡(luò)演化示意圖（N=5，m0=4，min=3，mout=1）Fig.2 BA scale-free directed network diagram evolution（N=5，m0=4，min=3，mout=1）

3 仿真結(jié)果及分析

文中通過計(jì)算機(jī)利用matlab程序設(shè)計(jì)語言，編寫程序?qū)ι鲜鲅莼Ｐ瓦M(jìn)行了仿真實(shí)驗(yàn)。模擬了10 000個(gè)節(jié)點(diǎn)的BA無標(biāo)度復(fù)雜有向網(wǎng)絡(luò)模型，并得到了該復(fù)雜有向網(wǎng)絡(luò)的鄰接矩陣及網(wǎng)絡(luò)中結(jié)點(diǎn)度分布圖如圖3所示。實(shí)驗(yàn)中的相關(guān)數(shù)據(jù)為網(wǎng)絡(luò)的規(guī)模N=104，初始網(wǎng)絡(luò)中的結(jié)點(diǎn)數(shù)m0=4，新節(jié)點(diǎn)連入網(wǎng)絡(luò)時(shí)以該節(jié)點(diǎn)為弧頭的入邊min=3，以新節(jié)點(diǎn)為弧尾的出邊mout=1。圖中星號(hào)表示實(shí)驗(yàn)得到的數(shù)據(jù)（30次實(shí)驗(yàn)的平均值），直線是對(duì)于雙對(duì)數(shù)圖的擬合直線，可以看出通過上述BA無標(biāo)度復(fù)雜有向網(wǎng)絡(luò)演化模型得到的復(fù)雜有向網(wǎng)絡(luò)的度分布滿足冪指數(shù)為-3的冪律分布，具有明顯的無標(biāo)度特性。

圖3 BA無標(biāo)度復(fù)雜有向網(wǎng)絡(luò)的度分布Fig.3 Degree distribution of BA scale-free comple direction network

4 結(jié) 論

現(xiàn)實(shí)世界中有很多網(wǎng)絡(luò)都是有向網(wǎng)絡(luò)，例如神經(jīng)網(wǎng)絡(luò)、電子郵件網(wǎng)絡(luò)等，文中提出的有向網(wǎng)絡(luò)演化模型，對(duì)于研究復(fù)雜有向網(wǎng)絡(luò)的相關(guān)特性具有重要的意義。通過仿真實(shí)驗(yàn)，本模型得到的復(fù)雜有向網(wǎng)絡(luò)具有明顯的無標(biāo)度特性，能有效的模擬現(xiàn)實(shí)世界的具有無標(biāo)度特性的復(fù)雜有向網(wǎng)絡(luò)，可以在此模型上展開對(duì)復(fù)雜有向網(wǎng)絡(luò)的其他相關(guān)拓?fù)湫再|(zhì)及其動(dòng)力學(xué)行為的分析及研究，依據(jù)本模型得到的仿真數(shù)據(jù)對(duì)于我們更進(jìn)一步了解復(fù)雜有向網(wǎng)絡(luò)具有重要的參考價(jià)值。

[1] Ralbert，Albarabasi. Statistical mechanics of complex networks[J].Rev.Mod.Phys，2002，74（1）：32-35.

[2]Newman M E J.The strueture and function of complex networks[J].SIAM Review，2003（45）：167-256.

[3]ErdosP，RenyiA.On random graphs[J].Publications Mathematicae，1959（6）：290-297.

[4]Erdos P，Renyi A.On the evolution of random graphs[J].Pub.Math.inst.hung.Acad， sci,1960（5）：17-61.

[5]Erdos P，Renyi A.On the strength of connectedness of a randomgraphs[J].ActaMath.Sci.Hungary，1961（12）：261-267.

[6]Barabási，A.-L，Albert R.Emergenee of scaling in random networks[J].Scienee，1999（286）：509-512.

[7]Barabási A L， Albert R， Jeong， H.Scale-free characteristics of random networks：The topology of the World Wide Web[J].Physica A，2000（281）：69-77.

[8]Barabási A L ，Bonabeau E.Scale-Free Networks[J].Scientific American，2003（288）：60-69.

[9]Newman M E J，Moore C，Watts D J.Mean-Field Solution of the small world network model[J].Physical Review Letters，2000，84（14）：3201-3204.

[10]Watts D J，Strogatz S H.Collective dynamics of“smallworld”networks[J].Nature，1998（393）：440-442.

[11]Barthelemy M L，AmaralA N.small-world networks：Evidence for a crossver picture[J].Phys.Rev， Lett，1999（82）：3180-3183.

[12]Tadie B.Dynamies of directed graphs：the world-wide web[J].Physical A，2001（293）：273-284.

[13]Ramezanpour A，Karimipour V.Simple models of smallworld networks with directed Links[J].Phys.Rev.E，2002（66）：036-128.

[14]Schwartz N，Cohen R，Ben-Avraham D A.et al.Havlin.Percolation in directed scale-free networks [J].Physical review E，2002（66）：151-442.

[15]Murai T.Master thesis：SpectralAnalysisofDirected Complex Networks[D].Japan：Tokyo，2002.

[16]De Angelis D L.Stability and connectance in food web models[J]， Ecology，1975（56）：238-243.

[17]J E C.Ratio of Prey to Predators in community food webs[J].Nature，1977（270）：165-167.

[18]Morelli L G.Simple model for directed networks[J].Physical Review，2003（67）：66-107.

[19]Siganos G，F(xiàn)aloutsos M，F(xiàn)aloutsos P， et al.Power-laws and the AS-level Internet topology [J].IEEE/ACM Trans.on Networking，2003（11）：514-524.

[20]郭進(jìn)利.供應(yīng)鏈型網(wǎng)絡(luò)中雙冪律分布模型[J].物理學(xué)報(bào)，2006，55（8）：3916-3921.

GUO Jin-li.The bilateral power-law distribution model of supply chain networks[J].Acta Phys.Sin.，2006，55 （8）：3916-3921.

[21]BarabásiA L， AlbertR.Emergence ofscaling in randomnetworks[J].Science，1999，286（5439）：5092512.

[22]Dorogovtsev S N，Mendes J F F.Evolutionof networks[J].Adv.Inphys.，2002（51）：1079-1187.

[23]Strogatz S H.Exploringcomplex networks[J].Nature，2001（410）：268-276.

[24]汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2006.

[25]王朝瑞.圖論[M].2版.北京：北京理工大學(xué)出版社，2000.

[26]楊韜，劉崇新，許喆，等.基于神經(jīng)網(wǎng)絡(luò)與混沌理論的電力系統(tǒng)短期負(fù)荷預(yù)測[J].陜西電力，2008（6）：6-9.

YANG Tao，LIU Chong-xin，XU Zhe，et al.Short-term load forecasting based on Chaos theory and neural network in power system[J].Shaanxi Electric Power，2008（6）：6-9.