一類變冪率的無標度網絡模型構建和分析

那 日 薩， 張 書 超， 穆 青

（大連理工大學 管理學院，遼寧 大連 116024）

0 引 言

現實世界中許多系統都可以用復雜網絡來描述，20世紀末，Albert等在對互聯網的研究中發現了無標度網絡（scale－free network），即節點度分布服從冪律分布，從而開辟了人類對于復雜網絡系統認識的新天地.

BA模型［1］是第一個無標度網絡演化模型，它捕捉到了無標度網絡形成的增長和擇優連接這兩個必不可少的機制，說明了大規模復雜網絡自組織成為無標度狀態的原因.BA模型雖然比較準確地把握了現實世界中網絡最基本的特點，較好地解釋了無標度網絡的形成機制，但其與現實網絡相比，仍有一定的差距，如多數現實網絡具有很大的集聚系數，它們的度分布指數γ一般介于（2，3）［2～4］，相反BA 網絡的集聚系數隨著網絡規模增大趨于0且其度分布指數γ＝3.

為了對現實的復雜網絡進行更深入的分析和研究，還需要對BA模型進行擴充，使它更加符合實際.劉慧等［5］兼顧局域演化、增長，以及局域與局域外存在較弱連接等3方面因素的加權網絡，發現它服從冪律指數為（2，3）的冪律分布.Krapivsky等［6］研究了非線性的擇優連接機制，并證明線性擇優連接時的冪率分布指數γ∈（2，∞）.Dorogovtsev等［7］考慮了老節點之間的連接或者斷開的情況，用節點連通的平均度的變化率來建立模型，并計算出該模型的網絡冪指數γ＝2＋1/（1＋2c），其中c∈R.Albert等［8］建立的模型則加入了一個老節點之間連接和已有邊的重新連接這兩種情況.但如何用連續域的解析方法建立和論證具有一般意義的復雜網絡演化模型仍是需要解決的問題，這對于細致地分析復雜網絡的演化過程具有重要意義.本文基于BA模型（新增節點的度為m），引入老節點之間的線性擇優連接機制（每次新增p條邊），建立一類變冪率的無標度網絡模型，用連續域的方法［9］給出這類復雜網絡演化的解析結果，并給出該網絡的集聚系數；同時通過一些實際網絡數據的分析，說明該網絡模型的有效性和合理性.

1 模型的演化規則

BA模型只考慮了新加入節點與系統已存在節點的連接情況，忽略了系統已存的老節點間的連接情況，為此基于BA模型，本文引入老節點之間的連接機制，構建一類新的網絡演化模型，其演化規則描述如下：

（1）在初始時刻t＝0，假定系統中已有少量（m0個）節點.

（2）t＝1時刻，新增一個度為m（m≤m0）的節點（與系統中原有的m0個初始節點進行連接，并且m0個孤立點之間產生p條邊（p≤m0（m0－1）/2））.

（3）在以后每一個時間間隔內，向系統增加一個度為m的新節點，其m條邊擇優連接到網絡中已經存在的不同節點上，并且現有系統老節點間擇優產生p條邊，直至網絡達到所需要的大小為止.這樣在經過t個時間間隔后，便形成一個具有N＝m0＋t個節點、（m＋p）t條邊的網絡.

具體的演化示意圖見圖1，初始時刻m0＝5，若m＝3，p＝2.t＝1時，新增節點5與節點0、1、4相連，老節點2與3、3與4之間產生p＝2條邊.t＝2時，新增節點6與節點3、4、5相連，已有節點0與2、3與5產生p＝2條邊.

圖1 網絡演化示意圖Fig.1 Sketch diagram of network evolution

下面給出該網絡演化的解析方程.

2 網絡模型的解析解及計算分析

在t時刻系統中有m0＋t個節點，設模型中i節點的連通度為ki（t）.根據前述演化規則，一方面考慮依據BA規則新增節點及其連接，一方面考慮老節點間的連接.

根據BA模型演化的擇優連接規則，i節點與新增節點連接的概率為P i（t），其中Pi（t）取決于該節點的連通度，

假設ki（t）連續，由于新增節點與老節點間的連接，以及老節點之間的連接均服從擇優連接規則，對已有節點i，有

其中Δk（t）表示t時刻網絡系統連通度的增量.在一個時間間隔網絡系統連通度的變化Δk（t）由兩部分構成，一是由新增節點增加的m條邊導致的新增連通度m，二是由老節點產生p條邊導致的新增連通度2p.因此有Δk（t）＝m＋2p，又考慮到則有

設節點i是t i時刻添加到系統的，則連通度ki（ti）＝m，此即為式（3）中微分方程的初始條件.通過計算，可得方程（3）的解

考慮節點連通度ki（t）小于k的概率P（ki（t）＜k）可表示為

假設時間t服從均勻分布，即

則

即

那么節點連通度的分布函數P（k）為

從中可得節點度分布呈冪率分布，其冪指數為

式（9）可改寫為

如果令c＝p/m，則式（10）與文獻［7］的結果相同.由式（10），節點度分布的冪指數γ∈ （2，3］，這與目前實際網絡冪指數的值是符合的.p與m取值不同時γ的變化如下：

（1）當p＝0時，γ＝3，即轉化為BA模型；

（2）當pm時，即老節點連接的邊遠小于新節點連接的邊時，γ接近3；

（3）當pm時，即老節點之間的連接遠大于新加入節點產生的邊時，γ接近2.

這說明，本文模型能夠更好地描述實際網絡演化問題，并且，BA演化模型只是其一個特例.

圖2給出了選取不同的p、m下利用理論結果式（8）計算得到的節點連通度分布函數圖形.

圖2是初始有7個點按照本文所述的演化規則演化到10 000個點的網絡后節點的度分布情況.

通過圖2可以看出，在m＝3的情況下，隨著p的增大，曲線斜率的絕對值減小，即隨著p/m的增大，γ減小，結合式（10）可得γm＝3，p＝1＝2.6，γm＝3，p＝7＝2.18.圖3給出了一個隨機模擬節點連通度分布與理論分布函數比較的圖.

通過圖3可以看出，隨機模擬理論模型的節點連通度的分布結果一致，此時理論節點度分布的冪率指數γm＝3，p＝1＝2.6.

圖2 不同的p、m下節點連通度分布函數圖形Fig.2 The diagram of distribution function of node connectivity in different p，m

圖3 連通度分布與理論分布的比較（m0＝5，m＝3，p＝1）Fig.3 The comparison of connectivity distribution and theoretical distribution function（m0＝5，m＝3，p＝1）

3 網絡的集聚系數和平均路徑

根據定義，節點i的集聚系數Ci等于它的k i個直接鄰居之間實際存在的邊數E i占所有可能存在 的 邊 數k i（ki－1）/2 的 比 例，即Ci＝2Ei/［ki（ki－1）］.整個網絡的集聚系數指的是所有節點集聚系數的算術平均值.可見，Ci只與兩個變量E i和k i有關，只有當Ei和k i變化時，Ci才隨著改變.章忠志等［9］曾給出與BA網絡等價的一個網絡的集聚系數.由于在本模型中，只有新節點與老節點之間才建立連接，當新節點連接到節點i且與i的鄰居進行連接時，或者節點i的鄰居之間發生連接時，節點的ki和E i會發生改變，從而改變Ci的值.Ci滿足下面的動態方程：

其中ΔCin表示新節點連接到節點i和它的n個鄰居時集聚系數的變化值，Pin表示這一變化的概率.ΔCin滿足下式：

Pin由兩部分的乘積構成：第1部分是有一條新邊連接到節點i的概率，這一概率由式（3）給出；第2部分指的是其余（m＋p－1）條新邊連接到節點i的n個鄰居的概率，它等價于每次成功概率為n（i）/（2m＋2p）t的（m＋p－1）重貝努利試驗中，成功n次的概率.n（i）表示節點i的鄰居數目，其值可通過下面的積分獲得.

綜上可得Pin的關系式為

由式（14）知：n＞1時，Pin很小，可以忽略.將式（4）、（12）、（14）代入方程（11），忽略低階項，得

由式（15），可得到Ci隨時間的演化公式：

對式（16）進行積分計算，就可得到整個網絡的平均集聚系數

可見，根據該演化模型，可推定其平均集聚系數隨著網絡規模的增大而迅速下降.當p＝0時，

由式（18）知該演化模型的平均集聚系數與BA網絡完全相同，BA模型只是該演化模型的特例.

網絡的平均路徑長度是指網絡中所有節點對之間的平均最短距離，它描述了網絡節點之間的分離程度.這里節點間的距離指的是從一節點到另一節點所要經歷的邊的最小數目.平均路徑長度的計算公式為，其中d ij為節點i和j之間的最短距離，N為網絡的規模.關于隨機網絡平均路徑長度的解析計算，目前還沒有普適的一般性方法.BA模型平均路徑的較精確解直到最近才被Chen等［10］給出，可見復雜網絡平均路徑長度求解的困難.在今后的工作中，將對本文模型的平均路徑長度的解析計算進行深入研究.

4 幾個實際網絡參數的估計

在現實生活中，實際的許多網絡如電影演員合作網等呈現出無標度現象，這些網絡相應規模下的冪率分布指數和節點平均連通度見表1.

表1 實際網絡的無標度現象Tab.1 The scale－free phenomenon in the real networks

這里假設實際的網絡是由BA模型演化而來，設網絡初始有m0個節點，經過w時間，則有〈k〉＝2mw/（m0＋w），當w→∞時，m則近似為實際網絡的平均度〈k〉的1/2，將m、γ代入式（10）可以計算出p.本文模型是同時考慮新增節點產生連接和老節點間的連接，則有〈k〉＝2（m＋p）w/（m0＋w），所以可近似地認為〈k〉＝ （m＋p）/2，這樣可以由算出的p和〈k〉推出m的值，結合式（10）可得本文模型的γ，具體結果見表2.

表2 實際網絡參數的估計Tab.2 The estimation of parameters on the real networks

表2中γBA表示BA模型推出的冪率分布指數，mBA表示假設實際網絡遵照BA模型演化時近似推得的BA模型中的m值，pwe表示由γ、mBA結合式（10）計算的p值，mwe是根據pwe和〈k〉近似得到的本模型中m值，γwe則是將pwe、mwe代入式（10）計算得到的本模型的冪率分布指數值.

通過表2可以看出本模型所得到的冪率分布指數比BA模型更接近于實際網絡，從而也證明了本模型的合理性和適用性.

5 結 語

用連續域的解析方法建立和論證具有一般意義的復雜網絡演化模型，對于分析大規模復雜網絡的演化規律、準確計算網絡各項綜合指標（如集聚系數）具有重要意義.本文提出了一類變冪率的無標度網絡模型，模型在BA模型的基礎上，加入系統已存節點之間的連接（其連接隱含擇優連接機制），并用連續域方法給出了該模型節點連通度分布函數的解析解和網絡的集聚系數.通過模擬計算分析，驗證了本文所提出的變冪率的網絡模型為無標度網絡，并且其冪率為2（m＋p）/（m＋2p）＋1，通過調節m和p的值，可以讓其冪率在（2，3）變化.當p＝0時，該模型與BA模型是一致的.通過一些實際網絡的數據，近似計算出本模型的冪率分布指數，驗證了該模型較之BA模型更具合理性和有效性.當然這里僅考慮了老節點之間產生新連接的問題，現實網絡涉及的其他問題并沒有加入到模型中，在今后的研究中，將進一步完善.

［1］BARABSI A L， ALBERT R， JEONG H.Mean－field theory for scale－free random networks［J］.Physica A，1999，272（68）：173－187

［2］ALBERT R，BARABSI A L.Statistical mechanics of complex networks［J］.Reviews of Modern Physics，2002，74（1）：47－97

［3］DOROGOVTSEV S N，MENDES J F F.Evolution of networks［J］.Advances in Physics，2002，51（4）：1079－1187

［4］NEWMAN M E J.The structure and function of complex networks［J］.SIAM Review，2003，45（2）：167－256

［5］劉 慧，李增揚，陸君安.局域演化的加權網絡模型［J］.復雜系統與復雜性科學，2006，3（1）：36－43

［6］KRAPIVSKY P L，REDNER S，LEYVRAZ F.Connectivity of growing random networks ［J］.Physical Review Letters，2000，85（21）：4629－4632

［7］DOROGOVTSEV S N，MENDES J F F.Scaling behaviour of developing and decaying networks［J］.Europhysics Letters，2000，52（33）：33－39

［8］ALBERT R，BARABASI A L.Topology of evolving networks：local events and universality ［J］.Physics Review Letters，2000，85（24）：5234－5237

［9］章忠志，榮莉莉.BA網絡的一個等價演化模型［J］.系統工程，2005，23（2）：1－5

［10］CHEN Fei，CHEN Zeng－qiang，WANG Xiu－feng，etal.The average path length of scale free networks［J］. Communications in Nonlinear Science and Numerical Simulation，2008，13（7）：1405－1410

［11］BARABSI A L， ALBERT R.Emergence of scaling in random networks ［J］.Science，1999，286（5439）：509－519

［12］NEWMAN M E J. Scientific collaboration networks.I.Network construction and fundamental results［J］.Physics Review E，2001，64（1）：016131

［13］CANCHO R F I，SOLE R V.The small－world of human language ［J］. Proceedings of the Royal Society B，2001，268（1482）：2261－2265