一類變冪率的無(wú)標(biāo)度網(wǎng)絡(luò)模型構(gòu)建和分析

那 日 薩， 張 書 超， 穆 青

（大連理工大學(xué) 管理學(xué)院，遼寧 大連 116024）

0 引 言

現(xiàn)實(shí)世界中許多系統(tǒng)都可以用復(fù)雜網(wǎng)絡(luò)來(lái)描述，20世紀(jì)末，Albert等在對(duì)互聯(lián)網(wǎng)的研究中發(fā)現(xiàn)了無(wú)標(biāo)度網(wǎng)絡(luò)（scale－free network），即節(jié)點(diǎn)度分布服從冪律分布，從而開辟了人類對(duì)于復(fù)雜網(wǎng)絡(luò)系統(tǒng)認(rèn)識(shí)的新天地.

BA模型［1］是第一個(gè)無(wú)標(biāo)度網(wǎng)絡(luò)演化模型，它捕捉到了無(wú)標(biāo)度網(wǎng)絡(luò)形成的增長(zhǎng)和擇優(yōu)連接這兩個(gè)必不可少的機(jī)制，說(shuō)明了大規(guī)模復(fù)雜網(wǎng)絡(luò)自組織成為無(wú)標(biāo)度狀態(tài)的原因.BA模型雖然比較準(zhǔn)確地把握了現(xiàn)實(shí)世界中網(wǎng)絡(luò)最基本的特點(diǎn)，較好地解釋了無(wú)標(biāo)度網(wǎng)絡(luò)的形成機(jī)制，但其與現(xiàn)實(shí)網(wǎng)絡(luò)相比，仍有一定的差距，如多數(shù)現(xiàn)實(shí)網(wǎng)絡(luò)具有很大的集聚系數(shù)，它們的度分布指數(shù)γ一般介于（2，3）［2～4］，相反BA 網(wǎng)絡(luò)的集聚系數(shù)隨著網(wǎng)絡(luò)規(guī)模增大趨于0且其度分布指數(shù)γ＝3.

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

1 模型的演化規(guī)則

BA模型只考慮了新加入節(jié)點(diǎn)與系統(tǒng)已存在節(jié)點(diǎn)的連接情況，忽略了系統(tǒng)已存的老節(jié)點(diǎn)間的連接情況，為此基于BA模型，本文引入老節(jié)點(diǎn)之間的連接機(jī)制，構(gòu)建一類新的網(wǎng)絡(luò)演化模型，其演化規(guī)則描述如下：

（1）在初始時(shí)刻t＝0，假定系統(tǒng)中已有少量（m0個(gè)）節(jié)點(diǎn).

（2）t＝1時(shí)刻，新增一個(gè)度為m（m≤m0）的節(jié)點(diǎn)（與系統(tǒng)中原有的m0個(gè)初始節(jié)點(diǎn)進(jìn)行連接，并且m0個(gè)孤立點(diǎn)之間產(chǎn)生p條邊（p≤m0（m0－1）/2））.

（3）在以后每一個(gè)時(shí)間間隔內(nèi)，向系統(tǒng)增加一個(gè)度為m的新節(jié)點(diǎn)，其m條邊擇優(yōu)連接到網(wǎng)絡(luò)中已經(jīng)存在的不同節(jié)點(diǎn)上，并且現(xiàn)有系統(tǒng)老節(jié)點(diǎn)間擇優(yōu)產(chǎn)生p條邊，直至網(wǎng)絡(luò)達(dá)到所需要的大小為止.這樣在經(jīng)過(guò)t個(gè)時(shí)間間隔后，便形成一個(gè)具有N＝m0＋t個(gè)節(jié)點(diǎn)、（m＋p）t條邊的網(wǎng)絡(luò).

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

圖1 網(wǎng)絡(luò)演化示意圖Fig.1 Sketch diagram of network evolution

下面給出該網(wǎng)絡(luò)演化的解析方程.

2 網(wǎng)絡(luò)模型的解析解及計(jì)算分析

在t時(shí)刻系統(tǒng)中有m0＋t個(gè)節(jié)點(diǎn)，設(shè)模型中i節(jié)點(diǎn)的連通度為ki（t）.根據(jù)前述演化規(guī)則，一方面考慮依據(jù)BA規(guī)則新增節(jié)點(diǎn)及其連接，一方面考慮老節(jié)點(diǎn)間的連接.

根據(jù)BA模型演化的擇優(yōu)連接規(guī)則，i節(jié)點(diǎn)與新增節(jié)點(diǎn)連接的概率為P i（t），其中Pi（t）取決于該節(jié)點(diǎn)的連通度，

假設(shè)ki（t）連續(xù)，由于新增節(jié)點(diǎn)與老節(jié)點(diǎn)間的連接，以及老節(jié)點(diǎn)之間的連接均服從擇優(yōu)連接規(guī)則，對(duì)已有節(jié)點(diǎn)i，有

其中Δk（t）表示t時(shí)刻網(wǎng)絡(luò)系統(tǒng)連通度的增量.在一個(gè)時(shí)間間隔網(wǎng)絡(luò)系統(tǒng)連通度的變化Δk（t）由兩部分構(gòu)成，一是由新增節(jié)點(diǎn)增加的m條邊導(dǎo)致的新增連通度m，二是由老節(jié)點(diǎn)產(chǎn)生p條邊導(dǎo)致的新增連通度2p.因此有Δk（t）＝m＋2p，又考慮到則有

設(shè)節(jié)點(diǎn)i是t i時(shí)刻添加到系統(tǒng)的，則連通度ki（ti）＝m，此即為式（3）中微分方程的初始條件.通過(guò)計(jì)算，可得方程（3）的解

考慮節(jié)點(diǎn)連通度ki（t）小于k的概率P（ki（t）＜k）可表示為

假設(shè)時(shí)間t服從均勻分布，即

則

即

那么節(jié)點(diǎn)連通度的分布函數(shù)P（k）為

從中可得節(jié)點(diǎn)度分布呈冪率分布，其冪指數(shù)為

式（9）可改寫為

如果令c＝p/m，則式（10）與文獻(xiàn)［7］的結(jié)果相同.由式（10），節(jié)點(diǎn)度分布的冪指數(shù)γ∈ （2，3］，這與目前實(shí)際網(wǎng)絡(luò)冪指數(shù)的值是符合的.p與m取值不同時(shí)γ的變化如下：

（1）當(dāng)p＝0時(shí)，γ＝3，即轉(zhuǎn)化為BA模型；

（2）當(dāng)pm時(shí)，即老節(jié)點(diǎn)連接的邊遠(yuǎn)小于新節(jié)點(diǎn)連接的邊時(shí)，γ接近3；

（3）當(dāng)pm時(shí)，即老節(jié)點(diǎn)之間的連接遠(yuǎn)大于新加入節(jié)點(diǎn)產(chǎn)生的邊時(shí)，γ接近2.

這說(shuō)明，本文模型能夠更好地描述實(shí)際網(wǎng)絡(luò)演化問(wèn)題，并且，BA演化模型只是其一個(gè)特例.

圖2給出了選取不同的p、m下利用理論結(jié)果式（8）計(jì)算得到的節(jié)點(diǎn)連通度分布函數(shù)圖形.

圖2是初始有7個(gè)點(diǎn)按照本文所述的演化規(guī)則演化到10 000個(gè)點(diǎn)的網(wǎng)絡(luò)后節(jié)點(diǎn)的度分布情況.

通過(guò)圖2可以看出，在m＝3的情況下，隨著p的增大，曲線斜率的絕對(duì)值減小，即隨著p/m的增大，γ減小，結(jié)合式（10）可得γm＝3，p＝1＝2.6，γm＝3，p＝7＝2.18.圖3給出了一個(gè)隨機(jī)模擬節(jié)點(diǎn)連通度分布與理論分布函數(shù)比較的圖.

通過(guò)圖3可以看出，隨機(jī)模擬理論模型的節(jié)點(diǎn)連通度的分布結(jié)果一致，此時(shí)理論節(jié)點(diǎn)度分布的冪率指數(shù)γm＝3，p＝1＝2.6.

圖2 不同的p、m下節(jié)點(diǎn)連通度分布函數(shù)圖形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 網(wǎng)絡(luò)的集聚系數(shù)和平均路徑

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

其中ΔCin表示新節(jié)點(diǎn)連接到節(jié)點(diǎn)i和它的n個(gè)鄰居時(shí)集聚系數(shù)的變化值，Pin表示這一變化的概率.ΔCin滿足下式：

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

綜上可得Pin的關(guān)系式為

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

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

對(duì)式（16）進(jìn)行積分計(jì)算，就可得到整個(gè)網(wǎng)絡(luò)的平均集聚系數(shù)

可見(jiàn)，根據(jù)該演化模型，可推定其平均集聚系數(shù)隨著網(wǎng)絡(luò)規(guī)模的增大而迅速下降.當(dāng)p＝0時(shí)，

由式（18）知該演化模型的平均集聚系數(shù)與BA網(wǎng)絡(luò)完全相同，BA模型只是該演化模型的特例.

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

4 幾個(gè)實(shí)際網(wǎng)絡(luò)參數(shù)的估計(jì)

在現(xiàn)實(shí)生活中，實(shí)際的許多網(wǎng)絡(luò)如電影演員合作網(wǎng)等呈現(xiàn)出無(wú)標(biāo)度現(xiàn)象，這些網(wǎng)絡(luò)相應(yīng)規(guī)模下的冪率分布指數(shù)和節(jié)點(diǎn)平均連通度見(jiàn)表1.

表1 實(shí)際網(wǎng)絡(luò)的無(wú)標(biāo)度現(xiàn)象Tab.1 The scale－free phenomenon in the real networks

這里假設(shè)實(shí)際的網(wǎng)絡(luò)是由BA模型演化而來(lái)，設(shè)網(wǎng)絡(luò)初始有m0個(gè)節(jié)點(diǎn)，經(jīng)過(guò)w時(shí)間，則有〈k〉＝2mw/（m0＋w），當(dāng)w→∞時(shí)，m則近似為實(shí)際網(wǎng)絡(luò)的平均度〈k〉的1/2，將m、γ代入式（10）可以計(jì)算出p.本文模型是同時(shí)考慮新增節(jié)點(diǎn)產(chǎn)生連接和老節(jié)點(diǎn)間的連接，則有〈k〉＝2（m＋p）w/（m0＋w），所以可近似地認(rèn)為〈k〉＝ （m＋p）/2，這樣可以由算出的p和〈k〉推出m的值，結(jié)合式（10）可得本文模型的γ，具體結(jié)果見(jiàn)表2.

表2 實(shí)際網(wǎng)絡(luò)參數(shù)的估計(jì)Tab.2 The estimation of parameters on the real networks

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

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

5 結(jié) 語(yǔ)

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

［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］劉 慧，李增揚(yáng)，陸君安.局域演化的加權(quán)網(wǎng)絡(luò)模型［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，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網(wǎng)絡(luò)的一個(gè)等價(jià)演化模型［J］.系統(tǒng)工程，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