徐玉章

最近鄰演化網(wǎng)絡(luò)模型

徐玉章

江蘇省自然科學(xué)基金項目：BK20141071

徐玉章 朱 磊

中國人民解放軍理工大學(xué)通信工程學(xué)院

我們生活在一個充滿復(fù)雜系統(tǒng)的社會中，其中很多系統(tǒng)的結(jié)構(gòu)都可以用復(fù)雜網(wǎng)絡(luò)來刻畫。20世紀(jì)末，科學(xué)家們建立了兩個重要的復(fù)雜網(wǎng)絡(luò)模型。其中一個模型是WS小世界網(wǎng)絡(luò)模型，該模型融合了規(guī)則網(wǎng)絡(luò)的大聚類特性和隨機(jī)圖網(wǎng)絡(luò)平均路徑長度較小的特性，可以說，WS小世界網(wǎng)絡(luò)模型是一種介于規(guī)則網(wǎng)絡(luò)和完全隨機(jī)網(wǎng)絡(luò)之間的網(wǎng)絡(luò)模型。但隨著復(fù)雜網(wǎng)絡(luò)研究的深入，人們發(fā)現(xiàn)越來越多的真實(shí)生活中的網(wǎng)絡(luò)呈現(xiàn)出無標(biāo)度（節(jié)點(diǎn)的度即與節(jié)點(diǎn)相連的邊的數(shù)量）的特點(diǎn)，即網(wǎng)絡(luò)中節(jié)點(diǎn)的度服從冪律分布，在雙對數(shù)坐標(biāo)下是一條斜線，而不是單峰曲線，另一種重要的復(fù)雜網(wǎng)絡(luò)模型應(yīng)運(yùn)而生。1999年，Barabási和Albert成功地提出了BA無標(biāo)度網(wǎng)絡(luò)模型，他們在該模型中解釋了復(fù)雜網(wǎng)絡(luò)無標(biāo)度性質(zhì)的一種可能形成機(jī)制：增長和隨機(jī)連接。BA無標(biāo)度網(wǎng)絡(luò)模型被認(rèn)為是最著名的復(fù)雜網(wǎng)絡(luò)模型之一。

在以往的復(fù)雜網(wǎng)絡(luò)模型的研究中很少考慮區(qū)域和距離的因素。然而，很多真實(shí)的網(wǎng)絡(luò)受限于節(jié)點(diǎn)的位置和節(jié)點(diǎn)間的距離，例如，現(xiàn)代物流網(wǎng)絡(luò)和大型集會中的臨時通信網(wǎng)絡(luò)，人際關(guān)系網(wǎng)絡(luò)中也有區(qū)域的限制。假設(shè)存在若干區(qū)域，每塊區(qū)域中有一個“骨干節(jié)點(diǎn)”。每個骨干節(jié)點(diǎn)和其鄰近的骨干節(jié)點(diǎn)相連，新加入的節(jié)點(diǎn)選擇其附近的節(jié)點(diǎn)進(jìn)行連接。節(jié)點(diǎn)代表了通信節(jié)點(diǎn)、物流中心等實(shí)際場景，邊代表了節(jié)點(diǎn)之間的聯(lián)系。在這種情況下，節(jié)點(diǎn)和邊的連接遵循就近原則，即節(jié)點(diǎn)更傾向于與最近的鄰居相連。上述情況在我們的生活中幾乎時時刻刻都在發(fā)生，我們該如何構(gòu)建與之相符的模型來描述這種情況呢？如何得出模型的關(guān)鍵指標(biāo)？新模型將具有哪些特性？為此，本文提出了“最近鄰演化網(wǎng)絡(luò)模型”。

1 最近鄰演化網(wǎng)絡(luò)模型的構(gòu)建

本文在BA無標(biāo)度網(wǎng)絡(luò)的構(gòu)建算法的基礎(chǔ)上引入?yún)^(qū)域和距離的限制，鄰近的節(jié)點(diǎn)將會位于同一簇中。最近鄰演化網(wǎng)絡(luò)模型的構(gòu)建算法如下。

（1）初始狀態(tài)：具有m0個節(jié)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)。每個節(jié)點(diǎn)和鄰近的左右兩側(cè)各K/2（K為偶數(shù)）個節(jié)點(diǎn)相連，稱這m0個初始節(jié)點(diǎn)為“骨干節(jié)點(diǎn)”。

（2）歸屬節(jié)點(diǎn)和節(jié)點(diǎn)簇：當(dāng)一個新節(jié)點(diǎn)加入網(wǎng)絡(luò)后，距該節(jié)點(diǎn)最近（距離以邊數(shù)衡量，最近即最短路徑上的邊數(shù)最少）的骨干節(jié)點(diǎn)稱為該節(jié)點(diǎn)的“歸屬節(jié)點(diǎn)”（如果幾個骨干節(jié)點(diǎn)與新節(jié)點(diǎn)的距離相同且均是最少，則從中隨機(jī)選取一個作為節(jié)點(diǎn)i的歸屬節(jié)點(diǎn)）。具有同一歸屬節(jié)點(diǎn)的節(jié)點(diǎn)構(gòu)成一個“節(jié)點(diǎn)簇”。

（3）增長：每次只允許一個節(jié)點(diǎn)加入網(wǎng)絡(luò)。新節(jié)點(diǎn)加入時，首先選擇2個相鄰的節(jié)點(diǎn)簇，再從這兩個節(jié)點(diǎn)簇中選擇m（m＞=2）個節(jié)點(diǎn)進(jìn)行連接。（在初始階段，節(jié)點(diǎn)簇中的節(jié)點(diǎn)數(shù)一般會小于m，所以規(guī)定新加入的節(jié)點(diǎn)只和其選擇的節(jié)點(diǎn)簇中2個節(jié)點(diǎn)連接）

（4）優(yōu)先連接：新節(jié)點(diǎn)在選擇節(jié)點(diǎn)進(jìn)行連接時，采用優(yōu)先連接的機(jī)制，即新節(jié)點(diǎn)和節(jié)點(diǎn)i相連的概率與節(jié)點(diǎn)i的度ki有關(guān)，度越大，連接概率越大，按如下公式計算：

其中，Pclusters表示選擇的節(jié)點(diǎn)簇中包含節(jié)點(diǎn)i的概率，

2 最近鄰演化網(wǎng)絡(luò)模型的基本指標(biāo)

復(fù)雜網(wǎng)絡(luò)研究中刻畫網(wǎng)絡(luò)特性的三個基本指標(biāo)為：度分布、聚類系數(shù)和平均路徑長度。度分布指網(wǎng)絡(luò)中節(jié)點(diǎn)度的分布，節(jié)點(diǎn)的度（如前述，即與該節(jié)點(diǎn)相連的邊的數(shù)目）可以衡量一個節(jié)點(diǎn)的重要程度，充分了解網(wǎng)絡(luò)的度分布，可以使我們對網(wǎng)絡(luò)拓?fù)溆幸粋€直觀的把握，并進(jìn)一步幫助人們更深入地了解復(fù)雜系統(tǒng)。聚類系數(shù)是衡量網(wǎng)絡(luò)中鄰近節(jié)點(diǎn)聯(lián)系緊密程度的指標(biāo)，網(wǎng)絡(luò)的聚類特性在某種程度上可以概括為社會關(guān)系網(wǎng)絡(luò)中“物以類聚，人以群分”的特性。平均路徑長度可用來衡量網(wǎng)絡(luò)中節(jié)點(diǎn)間距離的大小，如果網(wǎng)絡(luò)的平均路徑長度的增加速度至多與網(wǎng)絡(luò)規(guī)模的對數(shù)成正比，就說這個網(wǎng)絡(luò)具有小世界效應(yīng)。

度分布

將公式（2）帶入公式（1）得到

長時間后，每個節(jié)點(diǎn)簇中的節(jié)點(diǎn)數(shù)將遠(yuǎn)大于m，所以公式（3）中的約等于號成立。

利用主方程法，得到穩(wěn)態(tài)度分布為：

該公式表明最近鄰演化網(wǎng)絡(luò)模型和BA無標(biāo)度網(wǎng)絡(luò)模型具有相同的度分布。實(shí)驗結(jié)果和理論值吻合地較好。雙對數(shù)坐標(biāo)系下的斜線表明該網(wǎng)絡(luò)在具有眾多小度數(shù)節(jié)點(diǎn)的同時，仍在存在少量的大度節(jié)點(diǎn)，這也是網(wǎng)絡(luò)增長過程中擇優(yōu)連接的一個必然產(chǎn)物。

聚類系數(shù)

聚類系數(shù)指節(jié)點(diǎn)i的ki個鄰居節(jié)點(diǎn)之間實(shí)際存在的連邊數(shù)Ei與這ki節(jié)點(diǎn)所有可能的連邊數(shù)目之比，衡量了網(wǎng)絡(luò)中鄰近節(jié)點(diǎn)間的緊密程度，用Ci表示，即

這里“i”既是節(jié)點(diǎn)的代號，又是節(jié)點(diǎn)加入網(wǎng)絡(luò)的時間點(diǎn)。利用平均場理論，得到最近鄰演化網(wǎng)絡(luò)的聚類系數(shù)（隨時間變化）為：

當(dāng)ti遠(yuǎn)小于t（即節(jié)點(diǎn)i加入網(wǎng)絡(luò)后又過了較長時間）時，Ci（t）可作如下近似，

平均路徑長度

網(wǎng)絡(luò)中兩節(jié)點(diǎn)i和j之間的距離dij定義為連接這兩個節(jié)點(diǎn)的最短路徑的邊數(shù)。網(wǎng)絡(luò)的平均路徑長度L定義為任意兩個節(jié)點(diǎn)之間的距離的平均值，即

其中N為網(wǎng)絡(luò)節(jié)點(diǎn)個數(shù)，因為每一時刻網(wǎng)絡(luò)中有且只有一個節(jié)點(diǎn)加入，所以若不考慮網(wǎng)絡(luò)的初始規(guī)模，該處的N等價于t。

給出了無標(biāo)度網(wǎng)絡(luò)平均路徑長度的尺度，

如表1所示，通過仿真，本文得到了最近鄰演化網(wǎng)絡(luò)的平均路徑長度L，L的增長速度介于公式（9）和lnN之間。隨網(wǎng)絡(luò)規(guī)模的增加，平均路徑長度的增長十分緩慢，表明該網(wǎng)絡(luò)具有較明顯的“小世界效應(yīng)”。

表1 最近鄰演化網(wǎng)絡(luò)模型的平均路徑長度

3 總結(jié)與展望

現(xiàn)實(shí)生活中很多網(wǎng)絡(luò)與區(qū)域和距離因素息息相關(guān)，而以往的復(fù)雜網(wǎng)絡(luò)模型對區(qū)域和距離的因素考慮較少。本文將區(qū)域的概念引入無標(biāo)度網(wǎng)絡(luò)，建立了最近鄰演化網(wǎng)絡(luò)模型，并深入分析了該模型的度分布、聚類系數(shù)和平均路徑長度。結(jié)果表明，最近鄰演化網(wǎng)絡(luò)模型具有與BA無標(biāo)度網(wǎng)絡(luò)相同的度分布，此外，在保持較小的平均路徑長度的同時，該模型顯示出更好的聚類特性，即鄰近節(jié)點(diǎn)間的聯(lián)系更加緊密。下一步，我們將進(jìn)一步探究該模型的抗毀性。此外，在無標(biāo)度網(wǎng)絡(luò)的構(gòu)建中，人們專注于擇優(yōu)連接以求獲得無標(biāo)度特性，忽略了隨機(jī)連邊對網(wǎng)絡(luò)特性的影響，在復(fù)雜網(wǎng)絡(luò)模型研究中引入隨機(jī)連邊機(jī)制也將具有潛在重要意義。

10.3969/j.issn.1001-8972.2015.02.050