指數增長方式對無標度網絡冪律分布的影響

摘 要：隨機網絡中的增長和擇優連接特性是其頂點度服從冪律分布的重要原因。然而，在現實網絡中存在多種不同的增長方式。基于擇優連接和指數式增長，給出了無標度網絡頂點度服從冪律分布的解析結果：p（k）～k-r（r=2β+1且0.5<β≤1）。同時我們發現擇優連接過程發生在一個動態的局域世界上，并且局域世界的規模與整個網絡的規模成正比例。給出了隨機網絡上非擇優連接和指數式增長的解析結果。最后，給出了模型的計算機模擬結果來說明所給出的解析結論。

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

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

引言

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

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

復雜系統中一些事件的發生是隨機的且是獨立的，比如WWW中新網頁的出現等。由于增長型網絡中兩個接連添加的節點（即發生的事件）的間隔時間是不相同的，且指數分布具有無記憶性的優點，所以兩個節點（事件）出現的時間間隔服從參數為β的指數分布是描述這種現象的恰當方法，這里稱β為網絡的演化速率。可以看出，不同類型的增長網絡具有不同的演化速率。

Li Chen在2003年提出了無標度網絡的局域世界演化模型[6]。在事先給定局域世界的規模M后，隨機地從網絡中選出M個節點作為局域世界，新增節點擇優連接到局域世界中的m個節點上。可以說，BA模型的局域世界就是整個網絡。

在本文中，我們應用平均場理論給出網絡演化速率β對冪律分布指數的影響。同時，從網絡的指數式增長中得到了動態變化的局域世界，其規模與整個網絡的規模成比例。

一、指數式增長與擇優連接

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

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

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

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

π（ki）=■ （1）

由于每個節點出現的間隔時間t服從指數分布f（x）=βe-βx，β>0，x>0，則區間[0，t]上的計數過程N（t）服從泊松分布P（N（t）=

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

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

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

β≤1 （2）

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

假設是k連續的，對于節點i有

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

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

■=■ （4）

等式（4）的初始條件是節點i在時刻ti被添加到網絡，連通度為ki（ti），則等式（4）的解為

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

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

所以參數β滿足

β>0.5 （6）

根據等式（2）和（6），可得到隨機網絡的演化速率β滿足

0.5<β≤1 （7）

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

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

由于網絡增長的假設，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）

根據泰勒級數展開式，得到

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

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

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

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

二、指數式增長與非擇優連接

BA分別研究了兩個對照模型：均勻增長且非擇優連接的模型A和擇優連接且非增長的模型B。為檢測和驗證指數式增長對于網絡的影響，我們同樣也給出具有指數式增長且非擇優連接的模型的解析結果。

具有指數式增長且非擇優連接的模型的假設如下：

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

（2）均勻連接：假設新增節點等概率地與網絡中已存在的節點相連接。在時刻t，平均向網絡添加了βt個節點，則π（ki）=■與ki無關。

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

■Aπ（ki）=■ （13）

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

等式（13）的初始條件為節點i在時刻ti被添加到網絡中，ki（ti）=m，則等式（13）的解為

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

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

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

根據網絡增長方式的假設，ti的概率密度為

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

從而得到

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

對上式求導，可以得到概率密度P（k）為

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

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

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

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

結論

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

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

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

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

參考文獻：

[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] 李備友，劉思峰，路英，等.基于二分網絡演化的市場波動與羊群行為[J].系統工程，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] 李備友.基于交易者網絡的證券市場傳聞擴散博弈分析[J].經濟管理，2011，（9）：160-166.

[責任編輯 吳高君]

收稿日期：2013-08-02

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

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