阻滯增長(zhǎng)演化網(wǎng)絡(luò)的拓?fù)湫再|(zhì)

彭 莎，覃 森

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

0 引 言

當(dāng)前，眾多現(xiàn)實(shí)社會(huì)系統(tǒng)，如社會(huì)網(wǎng)絡(luò)中的謠言傳播、電路交通網(wǎng)絡(luò)等均可抽象為復(fù)雜網(wǎng)絡(luò)，即將具體的對(duì)象和對(duì)象之間的關(guān)系抽象為網(wǎng)絡(luò)中的節(jié)點(diǎn)與邊[1-2]。復(fù)雜網(wǎng)絡(luò)復(fù)雜性的重要體現(xiàn)之一是網(wǎng)絡(luò)演化規(guī)則的復(fù)雜性。1999年，Barabàsi和Albert[3]提出了無(wú)標(biāo)度網(wǎng)絡(luò)(Scale-free Network, SF)，利用節(jié)點(diǎn)增長(zhǎng)性和新邊擇優(yōu)連接性來(lái)解釋現(xiàn)實(shí)社會(huì)中普通存在的“富者更富”現(xiàn)象，引起許多領(lǐng)域科學(xué)家的廣泛關(guān)注。后續(xù)的研究表明：SF網(wǎng)絡(luò)中增長(zhǎng)模式與某些現(xiàn)實(shí)社會(huì)的節(jié)點(diǎn)與邊增長(zhǎng)方式并不吻合，如社交網(wǎng)絡(luò)中同一時(shí)間會(huì)有多個(gè)新用戶加入網(wǎng)絡(luò)[4]、網(wǎng)絡(luò)每次增加邊數(shù)可能存在非線性增長(zhǎng)或加速增長(zhǎng)的特性[5]。此外，網(wǎng)絡(luò)增長(zhǎng)中存在節(jié)點(diǎn)的加入與衰退現(xiàn)象，例如：生態(tài)網(wǎng)絡(luò)中，當(dāng)生命結(jié)束時(shí)節(jié)點(diǎn)也會(huì)隨之消失[6]，而且每個(gè)節(jié)點(diǎn)對(duì)于環(huán)境的適應(yīng)能力也不同[7]。另一方面，網(wǎng)絡(luò)的新邊連接方式不僅有擇優(yōu)連接，還存在隨機(jī)連接和反擇優(yōu)連接等[8-9]。深入研究網(wǎng)絡(luò)的演化特點(diǎn)獲得特殊的演化規(guī)律，對(duì)于網(wǎng)絡(luò)拓?fù)涮匦苑治觥?dòng)力學(xué)行為探索和網(wǎng)絡(luò)控制均具有重要的理論意義和實(shí)用價(jià)值。在SF網(wǎng)絡(luò)的基礎(chǔ)上，本文提出Logistic阻滯增長(zhǎng)網(wǎng)絡(luò)模型，每一步添加到網(wǎng)絡(luò)中的邊數(shù)不是恒定的常數(shù)，而是符合Logistic增長(zhǎng)，得到單個(gè)節(jié)點(diǎn)的度演化規(guī)律。

1 Logistic阻滯增長(zhǎng)

人口預(yù)測(cè)問(wèn)題中的指數(shù)增長(zhǎng)模型是一類簡(jiǎn)單的生物增長(zhǎng)模型，其最大的不合理之處在于沒(méi)有考慮環(huán)境的制約。而Logistic阻滯增長(zhǎng)考慮自然資源和環(huán)境條件等因素，能有效預(yù)測(cè)人口增長(zhǎng)的規(guī)律，在生產(chǎn)預(yù)測(cè)等方面應(yīng)用廣泛[10]。SF網(wǎng)絡(luò)的演化規(guī)則中，每一步添加到網(wǎng)絡(luò)中的邊數(shù)是常數(shù)m，本文在網(wǎng)絡(luò)新增邊數(shù)的規(guī)則中引入Logistic阻滯增長(zhǎng)模式，即每一個(gè)演化時(shí)間步t，一個(gè)新節(jié)點(diǎn)附帶到網(wǎng)絡(luò)中的新邊數(shù)m(t)滿足如下規(guī)則：

(1)

式中，a是演化網(wǎng)絡(luò)中第一步的新增邊數(shù)，r是每一步連接網(wǎng)絡(luò)中新邊的增長(zhǎng)速率，L是網(wǎng)絡(luò)最大容納量，即每一步添加到網(wǎng)絡(luò)中的最大邊數(shù)。眾多社會(huì)系統(tǒng)可抽象為復(fù)雜網(wǎng)絡(luò)，網(wǎng)絡(luò)演化過(guò)程中，每添加一個(gè)新節(jié)點(diǎn)，新節(jié)點(diǎn)與網(wǎng)絡(luò)中已有的m(t)個(gè)節(jié)點(diǎn)進(jìn)行連接。在初始階段的網(wǎng)絡(luò)中，節(jié)點(diǎn)數(shù)量少，添加到網(wǎng)絡(luò)中邊數(shù)少，但增長(zhǎng)速率快；增長(zhǎng)一段時(shí)間后，網(wǎng)絡(luò)中節(jié)點(diǎn)和邊數(shù)增多，此時(shí)增長(zhǎng)速率減緩但是仍然處于增長(zhǎng)階段；由于不能無(wú)限增長(zhǎng)，最后達(dá)到網(wǎng)絡(luò)最大容納量，此時(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)多，基數(shù)大，以最大值保持不變。因此，每一步添加到網(wǎng)絡(luò)中的邊數(shù)呈現(xiàn)Logistic阻滯增長(zhǎng)。L和r分別為L(zhǎng)ogistic增長(zhǎng)每一步添加到網(wǎng)絡(luò)中的最大邊數(shù)和增長(zhǎng)速率，a為第一步添加到網(wǎng)絡(luò)中的邊數(shù)，本文的研究針對(duì)L和r，研究其對(duì)網(wǎng)絡(luò)拓?fù)湫再|(zhì)的影響，不考慮a對(duì)Logistic網(wǎng)絡(luò)的影響，故a取一個(gè)較小常數(shù)4。

每一步添加到網(wǎng)絡(luò)中的邊數(shù)m(t)隨著時(shí)間增長(zhǎng)的變化情況如圖1所示。圖1(a)中，當(dāng)r=0.002時(shí)，L的取值分別為5，10，15和20?？梢钥闯?，L取定一個(gè)數(shù)值，隨著t增大，每一步的網(wǎng)絡(luò)新增邊數(shù)m(t)增加并將穩(wěn)定于網(wǎng)絡(luò)的最大容納量L。例如L=20，m(t)會(huì)增加到20，則后續(xù)每一步的網(wǎng)絡(luò)新增邊數(shù)m(t)恒為20。圖1(b)中，當(dāng)L=20時(shí)，r的取值分別為0.001，0.002，0.005和0.010，可以看出，增長(zhǎng)速率r越大時(shí)，新增邊數(shù)m(t)越快地達(dá)到最大值。

圖1 網(wǎng)絡(luò)新增邊數(shù)m(t)隨時(shí)間t變化曲線

2 具有Logistic阻滯增長(zhǎng)特性的演化網(wǎng)絡(luò)

2.1 網(wǎng)絡(luò)模型構(gòu)建

SF網(wǎng)絡(luò)中，每一個(gè)時(shí)間步增加一個(gè)節(jié)點(diǎn)且?guī)в衜條新邊，以擇優(yōu)連接方式進(jìn)行連邊。本文構(gòu)建具有Logistic阻滯增長(zhǎng)特性的演化網(wǎng)絡(luò)，即每一步新節(jié)點(diǎn)附帶著的邊數(shù)滿足Logistic阻滯增長(zhǎng)曲線。具體演化步驟如下。

(1)Logistic增長(zhǎng)。初始網(wǎng)絡(luò)為由m0個(gè)節(jié)點(diǎn)組成的連通網(wǎng)絡(luò)，每一步增加一個(gè)新節(jié)點(diǎn)，該節(jié)點(diǎn)與網(wǎng)絡(luò)中的m(t)個(gè)節(jié)點(diǎn)連接，m(t)滿足式(1)，且m(t)≤t+m0。

ki(t)表示在t時(shí)刻第i個(gè)節(jié)點(diǎn)的度。隨著時(shí)間t的增加，網(wǎng)絡(luò)規(guī)模不斷增長(zhǎng)，在時(shí)刻t網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)為m0+t。當(dāng)t足夠大時(shí)，網(wǎng)絡(luò)中的初始節(jié)點(diǎn)數(shù)可以忽略不計(jì)，即m0+t≈t。本文將時(shí)間t等價(jià)為網(wǎng)絡(luò)規(guī)模的大小n。

2.2 節(jié)點(diǎn)度的性質(zhì)分析

由于初始網(wǎng)絡(luò)中有m0個(gè)節(jié)點(diǎn)，每一步增加一個(gè)節(jié)點(diǎn)且連接m(t)條新邊。當(dāng)時(shí)間t充分大且忽略初始網(wǎng)絡(luò)邊數(shù)時(shí)，網(wǎng)絡(luò)中邊的總數(shù)為：

新節(jié)點(diǎn)加入到網(wǎng)絡(luò)中并與網(wǎng)絡(luò)中已存在的第i個(gè)節(jié)點(diǎn)連接的概率為：

根據(jù)平均場(chǎng)理論，單個(gè)節(jié)點(diǎn)的演化方程如下：

假設(shè)節(jié)點(diǎn)i是ti時(shí)刻加入到網(wǎng)絡(luò)中，則上述微分方程的初始條件為：

從而，解此微分方程得到網(wǎng)絡(luò)中任意節(jié)點(diǎn)i的演化方程：

令r趨于0，可以得到：

(2)

圖2 網(wǎng)絡(luò)中，3個(gè)不同節(jié)點(diǎn)的度隨時(shí)間t的演化規(guī)律

2.3 拓?fù)涮匦苑治?/h3>

2.3.1 度分布

由于Logistic阻滯增長(zhǎng)模型的節(jié)點(diǎn)度演化方程為非線性的，其度分布難以獲得解析結(jié)果，本文采用數(shù)值模擬的方法進(jìn)行分析。從節(jié)點(diǎn)度的演化方程可知，SF網(wǎng)絡(luò)是Logistic阻滯增長(zhǎng)模型的一個(gè)特例。因此，這兩類網(wǎng)絡(luò)模型的度分布也呈現(xiàn)出相關(guān)性。不同的L和r情況下，Logistic阻滯增長(zhǎng)網(wǎng)絡(luò)的度分布情況如圖3所示。

SF網(wǎng)絡(luò)的度分布服從冪律分布P(k)～k-γ，在雙對(duì)數(shù)坐標(biāo)系中是斜率為-γ的直線[3]。探索L和r對(duì)Logistic阻滯增長(zhǎng)模型度分布的影響，在數(shù)值模擬實(shí)驗(yàn)中，取n=20 000。從圖3可以看出，Logistic阻滯增長(zhǎng)模型的度分布在雙對(duì)數(shù)坐標(biāo)系中由兩段斜率不同的直線組成，呈現(xiàn)出雙冪律分布。在圖3(a)中，前半部分線性擬合，直線斜率均接近于-3。這表明當(dāng)網(wǎng)絡(luò)增長(zhǎng)邊數(shù)L達(dá)到最大值，后續(xù)每一步添加到網(wǎng)絡(luò)中的邊數(shù)恒為最大值，網(wǎng)絡(luò)演化退化為SF網(wǎng)絡(luò)。后半部分度分布的線性擬合發(fā)現(xiàn)：斜率數(shù)值相差較大，且L越大，后半部分度分布下降越快，此時(shí)受Logistic阻滯增長(zhǎng)的影響明顯，從而與SF網(wǎng)絡(luò)的度分布差別變大。

如圖3(b)所示，在不同的r下，前半部分的度分布仍然符合SF網(wǎng)絡(luò)，后半部分的度分布通過(guò)線性擬合得到直線斜率接近，并且r越小，雙冪律分布轉(zhuǎn)折點(diǎn)出現(xiàn)的越早。所以Logistic阻滯增長(zhǎng)模型中的參數(shù)L和r分別決定了其雙冪律分布后半部分的度分布指數(shù)與臨界點(diǎn)的位置。

圖3 網(wǎng)絡(luò)在不同的L與r條件下的度分布圖

2.3.2 平均路徑長(zhǎng)度

當(dāng)復(fù)雜網(wǎng)絡(luò)具有較小的平均路徑長(zhǎng)度和較大的聚類系數(shù)時(shí)，稱它具有小世界特性。圖4顯示網(wǎng)絡(luò)平均路徑長(zhǎng)度d在不同的L和r條件下隨網(wǎng)絡(luò)規(guī)模增長(zhǎng)的變化情況。當(dāng)網(wǎng)絡(luò)規(guī)模固定時(shí)，L或r越大，網(wǎng)絡(luò)的平均路徑長(zhǎng)度越小，這表明每步添加到網(wǎng)絡(luò)中的邊數(shù)越多可縮短節(jié)點(diǎn)之間的路徑長(zhǎng)度。如圖4(b)，固定L，隨著網(wǎng)絡(luò)規(guī)模增加，不同的r所對(duì)應(yīng)的平均路徑長(zhǎng)度差距縮小，比如當(dāng)n=7 000時(shí)，平均路徑長(zhǎng)度最大差距約為0.1。

圖4 網(wǎng)絡(luò)在不同的L與r條件下的平均最短路徑長(zhǎng)度

2.3.3 聚類系數(shù)

當(dāng)網(wǎng)絡(luò)充分大時(shí)，SF網(wǎng)絡(luò)不具有明顯的聚類特征，其聚類系數(shù)C滿足C～(lnt)2/t[11]。圖5是Logistic阻滯增長(zhǎng)網(wǎng)絡(luò)的聚類系數(shù)C在不同的L和r隨著網(wǎng)絡(luò)規(guī)模的變化情況，Logistic阻滯增長(zhǎng)網(wǎng)絡(luò)的聚類系數(shù)較小，聚類特征不明顯。其中圖(a)和圖(b)的內(nèi)插圖顯示了在雙對(duì)數(shù)坐標(biāo)下，C在不同的L和r隨著網(wǎng)絡(luò)規(guī)模的變化情況。聚類系數(shù)隨著網(wǎng)絡(luò)的規(guī)模冪律遞減，并且在雙對(duì)數(shù)坐標(biāo)中下降速度大致相同，即每一條代表不同參數(shù)的直線斜率接近相等，說(shuō)明聚類系數(shù)隨網(wǎng)絡(luò)規(guī)模的變化速率與不同的L和r沒(méi)有明顯關(guān)系。

圖5 網(wǎng)絡(luò)在不同的L與r條件下的聚類系數(shù)

2.3.4 同配系數(shù)

同配系數(shù)s∈[-1,1]的大小反映了網(wǎng)絡(luò)同配或異配的強(qiáng)弱程度。當(dāng)s>0，網(wǎng)絡(luò)是同配的，意味著網(wǎng)絡(luò)中度大的節(jié)點(diǎn)傾向于與度大的節(jié)點(diǎn)連接；反之，稱網(wǎng)絡(luò)是異配的。圖6顯示了不同的L和r對(duì)網(wǎng)絡(luò)同配系數(shù)的影響。數(shù)值模擬結(jié)果得到網(wǎng)絡(luò)的聚類系數(shù)均是負(fù)數(shù)，表明網(wǎng)絡(luò)是異配網(wǎng)絡(luò)，這和添加到網(wǎng)絡(luò)中的節(jié)點(diǎn)滿足優(yōu)先連接的性質(zhì)相符合。圖6(a)中，L越大對(duì)應(yīng)的同配系數(shù)|s|越小，網(wǎng)絡(luò)的異配性變?nèi)?。圖6(b)中，網(wǎng)絡(luò)規(guī)模n>5 000時(shí)，不同的增長(zhǎng)速率r對(duì)應(yīng)的網(wǎng)絡(luò)同配系數(shù)接近相等。另外，隨著網(wǎng)絡(luò)規(guī)模增加，網(wǎng)絡(luò)的同配系數(shù)趨于穩(wěn)定。

圖6 網(wǎng)絡(luò)在不同的L與r條件下的同配系數(shù)

3 結(jié)束語(yǔ)

基于SF網(wǎng)絡(luò)的節(jié)點(diǎn)增長(zhǎng)性，本文構(gòu)建了Logistic阻滯增長(zhǎng)網(wǎng)絡(luò)模型，研究網(wǎng)絡(luò)最大容納量和增長(zhǎng)速率的拓?fù)湫再|(zhì)規(guī)律。數(shù)值模擬結(jié)果表明，網(wǎng)絡(luò)是具有雙冪律分布特性的異配網(wǎng)絡(luò)。隨著網(wǎng)絡(luò)規(guī)模的增加，增長(zhǎng)速率對(duì)網(wǎng)絡(luò)的平均路徑長(zhǎng)度和同配系數(shù)的影響減弱，然而對(duì)聚類系數(shù)的變化趨勢(shì)沒(méi)有明顯影響。網(wǎng)絡(luò)的拓?fù)湫再|(zhì)為進(jìn)一步探索網(wǎng)絡(luò)演化對(duì)網(wǎng)絡(luò)拓?fù)湫再|(zhì)的影響及其原因提供了方向，同時(shí)利用Logistic模型可有效地調(diào)節(jié)演化網(wǎng)絡(luò)的度分布、平均路徑長(zhǎng)度、聚類系數(shù)和同配系數(shù)等拓?fù)涮匦?，為研究Logistic阻滯增長(zhǎng)網(wǎng)絡(luò)的動(dòng)力學(xué)行為和控制方法提供理論依據(jù)。