指數(shù)增長(zhǎng)方式對(duì)無標(biāo)度網(wǎng)絡(luò)冪律分布的影響

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

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

中圖分類號(hào)：O24 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1673-291X（2013）28-0013-04

引言

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

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

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

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

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

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

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

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

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

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

π（ki）=■ （1）

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

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

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

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

β≤1 （2）

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

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

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

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

■=■ （4）

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

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

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

所以參數(shù)β滿足

β>0.5 （6）

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

0.5<β≤1 （7）

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

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

由于網(wǎng)絡(luò)增長(zhǎng)的假設(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ù)泰勒級(jí)數(shù)展開式，得到

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

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

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

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

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

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

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

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

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

利用平均場(chǎng)理論，可以得到

■Aπ（ki）=■ （13）

在時(shí)間間隔Δt上，Δk=m，則A=m。

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

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

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

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

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

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

從而得到

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

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

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

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

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

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

結(jié)論

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

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

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

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

參考文獻(xiàn)：

[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ò)演化的市場(chǎng)波動(dòng)與羊群行為[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ò)的證券市場(chǎng)傳聞擴(kuò)散博弈分析[J].經(jīng)濟(jì)管理，2011，（9）：160-166.

[責(zé)任編輯 吳高君]

收稿日期：2013-08-02

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

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