基于BA無標度的復雜有向網絡演化模型

馬秀娟

（青海師范大學 計算機科學學院，青海 西寧 810008）

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

近年來，隨著對有向網絡研究的逐步深入，研究者發現對有向網絡的研究將有助于人類對與有向網絡相關的許多領域有更深入的理解。對在信息通信、網絡搜索、信號傳輸、傳染病控制，網絡的安全性和可靠性等方面都具有重要而深遠的意義[16-20]。

1999年 Barabási和 Albert提出 Scale-free （無標度）網絡模型[21]。與古典模型相比，這種模型較好地解釋了一些實際網絡（如因特網和演員合作網等）的特性。研究人員對大量的實際網絡進行了實證分析[22，23]，發現許多網絡都具有無標度的特性。

上述網絡模型是基于無向網絡建立的，文中根據BA無標度網絡模型提出了一種具有無標度特性的有向網絡演化模型，并設計程序進行了仿真實驗，對有向網絡的度分布進行了分析，結果表明，利用文中提出的有向網絡演化模型生成的復雜有向網絡的度分布符合冪律分布，能有效的模擬現實世界的具有無標度特性的復雜有向網絡，可以在此模型上展開對復雜有向網絡的其他相關拓撲性質的分析及研究。

1 有向網絡及其相關概念

1.1 有向網絡

一個具體的網絡可以抽象為一個由點集V邊集E組成的圖G=（V，E）。 節點數記為N=|V|，邊數記為M=|E|，E中每條邊都有V中一對頂點與之相對應，如果任意點對（i，j）與（j，i）對應同一條邊，則該網絡成為無向網絡（undirected network），否則稱為有向網絡（directed network）[24]。圖1給出了兩種不同類型的網絡。

圖1 不同類型網絡結構圖Fig.1 Different types of network structure

1.2 有向網絡的度、出度、入度和鄰接矩陣

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

設G是含有P個節點 （或頂點），q條有向邊的有向網絡。令

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

2 BA無標度復雜有向網絡演化模型

1999年Barabási和Albert[21]提出了一個以增長和擇優連接機理演化的無標度網絡模型，它揭示了各類現實網絡最普遍的現象，但該模型只是一個無向的網絡模型，它無法體現有向網絡的一些主要特性，為了研究有向網絡的相關性質，需要建立有向網絡的動態演化模型以模擬現實世界中的復雜有向網絡。文中在前人提出的BA無標度網絡模型的基礎之上提出了具有無標度特性的復雜有向網絡演化模型。具體演化過程如下：

1）初始網絡：初始給定m0個節點，m0條有向邊，首尾連接，保證網絡的連通性；固定網絡的規模為N。

2）增長機制：每一時刻將N-m0中的一個節點s作為新節點加入到有向網絡中。為了保證有向網絡的連通性，結點s連入網絡時，增加以結點s為弧尾的min條入邊和以結點s為弧頭的mout條出邊；網絡中不允許重連邊，也不允許自身連邊；新節點連接到網絡后，N減1；

3）擇優機制：新節點s連入網絡時，將與網絡中的已有結點進行連接，由于網絡是一個連通的復雜有向網絡，因此連接時考慮如下兩個方面：

4）輸出數據：輸出最終得到的N個節點的鄰接矩陣，該矩陣表示了利用上述演化模型生成的規模為N的復雜有向網絡，同時輸出該有向網絡結點的度分布圖，有向網絡中結點的度為 deg ree（i）=deg+（i）+deg-（i），（其中 deg+（i）表示結點i的入度，deg-（i）為結點 i的出度）。

圖 2 顯示了當 N=5，m0=4，min=3，mout=1 時的 BA 無標度有向網絡的演化過程。

圖 2 BA 無標度有向網絡演化示意圖（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 仿真結果及分析

文中通過計算機利用matlab程序設計語言，編寫程序對上述演化模型進行了仿真實驗。模擬了10 000個節點的BA無標度復雜有向網絡模型，并得到了該復雜有向網絡的鄰接矩陣及網絡中結點度分布圖如圖3所示。實驗中的相關數據為網絡的規模N=104，初始網絡中的結點數m0=4，新節點連入網絡時以該節點為弧頭的入邊min=3，以新節點為弧尾的出邊mout=1。圖中星號表示實驗得到的數據（30次實驗的平均值），直線是對于雙對數圖的擬合直線，可以看出通過上述BA無標度復雜有向網絡演化模型得到的復雜有向網絡的度分布滿足冪指數為-3的冪律分布，具有明顯的無標度特性。

圖3 BA無標度復雜有向網絡的度分布Fig.3 Degree distribution of BA scale-free comple direction network

4 結 論

現實世界中有很多網絡都是有向網絡，例如神經網絡、電子郵件網絡等，文中提出的有向網絡演化模型，對于研究復雜有向網絡的相關特性具有重要的意義。通過仿真實驗，本模型得到的復雜有向網絡具有明顯的無標度特性，能有效的模擬現實世界的具有無標度特性的復雜有向網絡，可以在此模型上展開對復雜有向網絡的其他相關拓撲性質及其動力學行為的分析及研究，依據本模型得到的仿真數據對于我們更進一步了解復雜有向網絡具有重要的參考價值。

[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，Faloutsos M，Faloutsos P， et al.Power-laws and the AS-level Internet topology [J].IEEE/ACM Trans.on Networking，2003（11）：514-524.

[20]郭進利.供應鏈型網絡中雙冪律分布模型[J].物理學報，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]汪小帆，李翔，陳關榮.復雜網絡理論及其應用[M].北京：清華大學出版社，2006.

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

[26]楊韜，劉崇新，許喆，等.基于神經網絡與混沌理論的電力系統短期負荷預測[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.