摘 要：隨機網(wǎng)絡(luò)中的增長和擇優(yōu)連接特性是其頂點度服從冪律分布的重要原因。然而，在現(xiàn)實網(wǎng)絡(luò)中存在多種不同的增長方式?；趽駜?yōu)連接和指數(shù)式增長，給出了無標度網(wǎng)絡(luò)頂點度服從冪律分布的解析結(jié)果：p（k）～k-r（r=2β+1且0.5<β≤1）。同時我們發(fā)現(xiàn)擇優(yōu)連接過程發(fā)生在一個動態(tài)的局域世界上，并且局域世界的規(guī)模與整個網(wǎng)絡(luò)的規(guī)模成正比例。給出了隨機網(wǎng)絡(luò)上非擇優(yōu)連接和指數(shù)式增長的解析結(jié)果。最后，給出了模型的計算機模擬結(jié)果來說明所給出的解析結(jié)論。

關(guān)鍵詞：局域世界；冪律分布；泊松過程；平均場理論

中圖分類號：O24 文獻標志碼：A 文章編號：1673-291X（2013）28-0013-04

引言

最近以來，隨機網(wǎng)絡(luò)的增長特性引起了人們很大的興趣，如萬維網(wǎng)WWW和社會網(wǎng)絡(luò)。隨機網(wǎng)絡(luò)的增長模型首先由Barabási and Albert（BA）提出。在BA模型中，網(wǎng)絡(luò)開始于少量的節(jié)點（m0），并且在每一個相同長度的時間步上向網(wǎng)絡(luò)添加一個帶有m條邊的新增節(jié)點，故其增長方式是均勻增長的。所有節(jié)點的度都以同樣的方式演化，k～t1/2，即按照演化時間t的冪函數(shù)形式增加它們的連通度。老節(jié)點擁有較長的生存時間來獲得網(wǎng)絡(luò)中的連接，因此它們具有很高的連通度，形成規(guī)模不等的“hub”節(jié)點。現(xiàn)實中大量的增長型網(wǎng)絡(luò)（如Internet、傳染病傳播網(wǎng)等）雖然具有不同的物理形式，同時頂點和邊也具有不同的含義，但是，它們卻表現(xiàn)出極大的拓撲相似性，即節(jié)點的連通度分布服從冪律分布，這也是許多復(fù)雜網(wǎng)絡(luò)的一個共同特征。BA應(yīng)用平均場理論證明了增長特性與擇優(yōu)連接特性的結(jié)合最終使網(wǎng)絡(luò)自組織演化到一個無標度狀態(tài)[1]：一個節(jié)點連接到其他k個節(jié)點的連接概率P（k）以冪律形式衰減，服從P（k）～k-r形式，其中冪指數(shù)滿足r=3。

然而，大量對實際網(wǎng)絡(luò)的研究表明在許多無標度網(wǎng)絡(luò)中節(jié)點度的冪律分布不僅僅是r=3的情況（見表1），而是冪律分布的指數(shù)通常滿足2

復(fù)雜系統(tǒng)中一些事件的發(fā)生是隨機的且是獨立的，比如WWW中新網(wǎng)頁的出現(xiàn)等。由于增長型網(wǎng)絡(luò)中兩個接連添加的節(jié)點（即發(fā)生的事件）的間隔時間是不相同的，且指數(shù)分布具有無記憶性的優(yōu)點，所以兩個節(jié)點（事件）出現(xiàn)的時間間隔服從參數(shù)為β的指數(shù)分布是描述這種現(xiàn)象的恰當方法，這里稱β為網(wǎng)絡(luò)的演化速率?？梢钥闯觯煌愋偷脑鲩L網(wǎng)絡(luò)具有不同的演化速率。

Li Chen在2003年提出了無標度網(wǎng)絡(luò)的局域世界演化模型[6]。在事先給定局域世界的規(guī)模M后，隨機地從網(wǎng)絡(luò)中選出M個節(jié)點作為局域世界，新增節(jié)點擇優(yōu)連接到局域世界中的m個節(jié)點上?？梢哉f，BA模型的局域世界就是整個網(wǎng)絡(luò)。

在本文中，我們應(yīng)用平均場理論給出網(wǎng)絡(luò)演化速率β對冪律分布指數(shù)的影響。同時，從網(wǎng)絡(luò)的指數(shù)式增長中得到了動態(tài)變化的局域世界，其規(guī)模與整個網(wǎng)絡(luò)的規(guī)模成比例。

一、指數(shù)式增長與擇優(yōu)連接

BA模型表明了增長和擇優(yōu)連接對于冪律分布的影響。其增長和擇優(yōu)連接分別為：在相同的時間間隔上向網(wǎng)絡(luò)添加一個新節(jié)點，并且新節(jié)點與節(jié)點i相連接的概率依賴于節(jié)點i的連通度ki。

這里，我們把節(jié)點增加的時間間隔從不變改為服從指數(shù)分布，同時保留擇優(yōu)連接特性，則新模型定義如下：

（1）指數(shù)式增長：網(wǎng)絡(luò)開始于較少數(shù)量的節(jié)點（n0）。在間隔時間t上，向網(wǎng)絡(luò)添加一個帶有m （m≤n0）邊的新節(jié)點，這m條邊將與網(wǎng)絡(luò)中已存在的m個節(jié)點相連。間隔時間t服從參數(shù)為β的指數(shù)分布。

（2）擇優(yōu)連接：當選擇與新節(jié)點相連接的節(jié)點時，假定新節(jié)點與節(jié)點i相連接的概率π（ki）依賴于該節(jié)點的連通度ki，即

π（ki）=■ （1）

由于每個節(jié)點出現(xiàn)的間隔時間t服從指數(shù)分布f（x）=βe-βx，β>0，x>0，則區(qū)間[0，t]上的計數(shù)過程N（t）服從泊松分布P（N（t）=

k）=■e-βt，從而在每個時間單元上出現(xiàn)的節(jié)點數(shù)目n服從泊松分布P（n=k）=■e-β。

在時刻t，平均有βt個節(jié)點被添加到網(wǎng)絡(luò)中，則模型變?yōu)橐粋€具有n0+βt個節(jié)點和mβt條邊的隨機網(wǎng)絡(luò)，整個網(wǎng)絡(luò)的度之和為■kj=2mβt。將網(wǎng)絡(luò)中的節(jié)點i按照其連通度ki的大小重復(fù)ki次排成一個列表。例如，一個網(wǎng)絡(luò)有4個節(jié)點，分別標記為a、b、c、d，且其度數(shù)分別為2.1.2.3，網(wǎng)絡(luò)共有4條邊，則節(jié)點排成列表的形式為（a，a，b，c，c，d，d，d）。處理的結(jié)果使得擇優(yōu)連接轉(zhuǎn)化為等概率的均勻連接，所以新節(jié)點的每條邊與老節(jié)點連接的概率為p=■。當t→∞，p→0，能夠滿足二項分布逼近泊松分布的條件：較大的N，較小的p，從而得到β=Np。對于適當?shù)膖，存在2mβt≥n0+βt，所以有N=β·2mβt≥β（n0+βt）。

根據(jù)二項分布逼近泊松分布得到β=NCmNpm（1-p）N-m，也即是說，從N個節(jié)點中選出m個節(jié)點與新增節(jié)點相連的事件對應(yīng)于m重貝努里試驗。這里，N是從所有n0+βt個節(jié)點中選出的局域世界的節(jié)點數(shù)，則N≤n0+βt。又由于N≥β（n0+βt），得到

β≤1 （2）

下面我們用平均場理論解析計算概率p（k），以便精確確定標度指數(shù)r。

假設(shè)是k連續(xù)的，對于節(jié)點i有

■=Aπ（ki）=A■ （3）

由于■kj=2mβt，且在只有一個節(jié)點被添加到網(wǎng)絡(luò)的時間間隔Δt上連通度的變化率為Δk=m，可知A=m，所以由等式（3）得到

■=■ （4）

等式（4）的初始條件是節(jié)點i在時刻ti被添加到網(wǎng)絡(luò)，連通度為ki（ti），則等式（4）的解為

ki（t）=m×■■ （5）

由于節(jié)點能夠隨時間演化增加其度數(shù)，則■>0；又由于ki（t）的增長不可能超過t，則■<1。所以，等式（5）中的指數(shù)■是有界的，即0<■<1。

所以參數(shù)β滿足

β>0.5 （6）

根據(jù)等式（2）和（6），可得到隨機網(wǎng)絡(luò)的演化速率β滿足

0.5<β≤1 （7）

節(jié)點連通度ki（t）小于k的概率P（ki（t）

P（ki（t）■2β·t （8）

由于網(wǎng)絡(luò)增長的假設(shè)，ti的概率密度為

pi（ti）=βe-βti （9）

從而得到

Pti>■2β·t=1-Pti≤■2β·t=e-βt■2β （10）

概率密度p（k）通過微分可以得到

p（k）=■=e-βt■2β·2β2t（m）2β·■ （11）

根據(jù)泰勒級數(shù)展開式，得到

e-βt■2β=1-βt■2β+■β2t2■4β-……

由于k≥m，得到概率密度的近似表達式為

p（k）≈2β2t·m2β·■ （12）

這里冪律分布的指數(shù)為r=2β+1，其中參數(shù)β滿足0.5<β≤1，所以冪律分布指數(shù)r滿足2

二、指數(shù)式增長與非擇優(yōu)連接

BA分別研究了兩個對照模型：均勻增長且非擇優(yōu)連接的模型A和擇優(yōu)連接且非增長的模型B。為檢測和驗證指數(shù)式增長對于網(wǎng)絡(luò)的影響，我們同樣也給出具有指數(shù)式增長且非擇優(yōu)連接的模型的解析結(jié)果。

具有指數(shù)式增長且非擇優(yōu)連接的模型的假設(shè)如下：

（1）指數(shù)式增長：網(wǎng)絡(luò)開始于較少數(shù)量的節(jié)點（n0）。在間隔時間t上，向網(wǎng)絡(luò)添加帶有m （m≤n0）個邊的新節(jié)點。這m條邊將與網(wǎng)絡(luò)中已存在的m個節(jié)點相連。間隔時間t服從參數(shù)為β的指數(shù)分布。

（2）均勻連接：假設(shè)新增節(jié)點等概率地與網(wǎng)絡(luò)中已存在的節(jié)點相連接。在時刻t，平均向網(wǎng)絡(luò)添加了βt個節(jié)點，則π（ki）=■與ki無關(guān)。

利用平均場理論，可以得到

■Aπ（ki）=■ （13）

在時間間隔Δt上，Δk=m，則A=m。

等式（13）的初始條件為節(jié)點i在時刻ti被添加到網(wǎng)絡(luò)中，ki（ti）=m，則等式（13）的解為

ki（t）=mln■+1 （14）

節(jié)點i連通度ki（t）小于k的概率p（ki（t）

p（ki（t）■（m0+βt-1）e1-■-m0+1 （15）

根據(jù)網(wǎng)絡(luò)增長方式的假設(shè)，ti的概率密度為

pi（ti）=βe-βti （16）

從而得到

Pti>■（m0+βt-1）e1-■-m0+1=e- [ （m0+βt-1）e1-■-m0+1] （17）

對上式求導(dǎo)，可以得到概率密度P（k）為

p（k）=■·e- [ （m0+βt-1）e1-■-m0 ]·e-■ （18）

根據(jù)ex的泰勒級數(shù)展開式和k≤m，得到概率密度為

p（k）≈■·e-■ （19）

這個結(jié)論與BA模型的結(jié)論相同[1]，但是系數(shù)卻豐富化了。同樣地，模型的特征連通度為k*=m。這個模型說明如果缺少了擇優(yōu)連接就消除了BA模型的無標度特性。

結(jié)論

為檢測和驗證參數(shù)β對冪律指數(shù)r的影響，我們用計算機模擬隨機網(wǎng)絡(luò)的演化過程。模擬的結(jié)果由圖1給出。這里指數(shù)分布參數(shù)β取值為β=0.7，短劃線的斜率為冪律分布的指數(shù)r=2.308。同樣的圖形也可以在文獻[6]中找到。

從模擬的結(jié)果可以看出，網(wǎng)絡(luò)演化的速率β能夠影響冪律分布的指數(shù)r，基本滿足關(guān)系式r=2β+1。當然，由于泰勒級數(shù)的舍入使得結(jié)果不嚴格等同于關(guān)系式r=2β+1。

在圖1中，有少量的節(jié)點偏離了冪律分布，我們稱之為“super hub”節(jié)點。這些“super hub”擁有網(wǎng)絡(luò)中的大量的邊，隨著網(wǎng)絡(luò)演化的發(fā)展，“富者愈富”的現(xiàn)象能更早地顯現(xiàn)。而其他節(jié)點的度服從冪律分布，滿足r=2β+1形式。由于“super hub”的存在，網(wǎng)絡(luò)演化為一個或幾個相對較大的集群，這種現(xiàn)象能在生態(tài)系統(tǒng)中找到。

解析結(jié)論和模擬結(jié)果也同樣表明了新增節(jié)點所擇優(yōu)連接的局域世界的規(guī)模是動態(tài)變化的（N=β·2mβt）。局域世界的大小與整個網(wǎng)絡(luò)的大小是成正比例的。事實上，網(wǎng)絡(luò)不可能是按照事先規(guī)定了大小的局域世界進行演化的。

參考文獻：

[1] Barabási，A.-L.，Albert，R.，and Jeong，H.，Mean-field theory for scale-free random networks，Physica A 272，pp 173-187，1999.

[2] Barabási，A.-L.，Albert，R.，Emergence of scaling in random networks，Science 286，pp509-512，1999.

[3] 李備友，劉思峰，路英，等.基于二分網(wǎng)絡(luò)演化的市場波動與羊群行為[J].系統(tǒng)工程，2011，（9）：59-65.

[4] Albert，R.and Barabási，A.-L.，Statistical mechanics of complex networks，Rev.Mod.Phys.74，pp 47-97，2002.

[5] M.E.J.Newman，The structure and function of complex networks.SIAM Review 45，pp167-256，2003.

[6] Xiang Li，Guanrong Chen.A local-world evolving network model.Physica A 328，2003pp274-286.

[7] Dorogovtsev，S.N.，Goltsev，A.V.，and Mendes，J.F.F.，Pseudofractal scale-free web，Phys.Rev.E65，066122，2002.

[8] Szabó，G.，Alava，M.，and Kertész，J.，Structural transitions in scale-free networks，arXiv：cond-mat/0208551，2002

[9] Watts，D.J.and Strogatz，S.H.，Collective dynamics of ‘small-world’ networks，Nature 393，pp 440-442，1998.

[10] Ravasz，E.and Barabási，A.L.，Hierarchical organization in complex networks，Phys.Rev.E 67，026112，2003.

[11] Montoya，J.M.and Solé，R.V.，Small world patterns in food webs，J.Theor.Bio.214，pp 405-412，2002.

[12] Solé，R.V.，and Montoya，J.M.，Complexity and fragility in ecological networks，Proc.R.Soc.London B 268，pp2039-2045，2001.

[13] 李備友.基于交易者網(wǎng)絡(luò)的證券市場傳聞擴散博弈分析[J].經(jīng)濟管理，2011，（9）：160-166.

[責任編輯 吳高君]

收稿日期：2013-08-02

基金項目：國家社會科學基金項目（11BJL074）；教育部人文社會科學研究基金項目（10YJAZH042）；山東省社會科學規(guī)劃研究項目（12CJJJ18）；山東省高等學校人文社會科學研究計劃（J13WG05）

作者簡介：蔣冰冰（1979-），女，河南洛陽人，碩士研究生，從事證券市場研究。