動(dòng)態(tài)空間約束網(wǎng)絡(luò)模型及其雙段冪律特征

徐 靜,錢江海

(上海電力大學(xué)數(shù)理學(xué)院，上海 200090)

0 引言

空間網(wǎng)絡(luò)是指節(jié)點(diǎn)和邊嵌入幾何空間，并與某些實(shí)際的物理或幾何效應(yīng)(比如連邊長(zhǎng)度、構(gòu)建代價(jià)、延時(shí)和能量耗散等)相聯(lián)系著的一類復(fù)雜網(wǎng)絡(luò)。這類網(wǎng)絡(luò)包括航空網(wǎng)絡(luò)[1-4]、道路網(wǎng)絡(luò)[5-7]、Internet[8-9]、電力網(wǎng)絡(luò)[10-12]和社會(huì)網(wǎng)絡(luò)等等[13-16]。與那些只具有拓?fù)湫再|(zhì)的系統(tǒng)不同[17-21]，空間網(wǎng)絡(luò)的結(jié)構(gòu)、演化和動(dòng)力學(xué)行為極大地受幾何效應(yīng)的制約[1-16]。這種制約帶來(lái)的對(duì)拓?fù)浣Y(jié)構(gòu)的一個(gè)重要影響體現(xiàn)在網(wǎng)絡(luò)度分布的標(biāo)度律上。大量實(shí)證研究表明，隨著網(wǎng)絡(luò)空間效應(yīng)的增強(qiáng)，其度分布會(huì)偏離冪律形態(tài)，而向較窄的指數(shù)型或高斯型分布過(guò)渡[1-7,22]。這一過(guò)渡在定性的層面是可以直觀理解的。由于空間網(wǎng)絡(luò)的連邊和構(gòu)建成本、時(shí)延以及能量耗散密切關(guān)聯(lián)，為了降低這些代價(jià)，一個(gè)節(jié)點(diǎn)的連接目標(biāo)自然局限于其附近的節(jié)點(diǎn)。這使得節(jié)點(diǎn)可連目標(biāo)的數(shù)量大大減少，從而抑制了大度值節(jié)點(diǎn)的產(chǎn)生。

為了從理論上定量地解釋這種空間效應(yīng)對(duì)度分布的影響，科學(xué)家提出了各種空間網(wǎng)絡(luò)模型。這些模型引入空間約束的方法大致可分為兩種。一種方法是賦予每個(gè)節(jié)點(diǎn)一個(gè)有限邊界的約束范圍，只有當(dāng)一方落在另一方的約束范圍內(nèi)時(shí)才可形成連邊。這種約束模式及其相關(guān)的各類變種組成空間網(wǎng)絡(luò)模型的一大類，即幾何圖模型[23-25]。另一種方法是引入距離衰減因子來(lái)修正連邊的概率，這類模型包含Waxman模型[26]、空間小世界模型[27-28]、空間無(wú)標(biāo)度模型和引力模型等等[4,29-30]。當(dāng)節(jié)點(diǎn)在網(wǎng)絡(luò)演化中互相競(jìng)爭(zhēng)著獲取連邊時(shí)，距離衰減函數(shù)將導(dǎo)致每個(gè)節(jié)點(diǎn)在其自身周圍產(chǎn)生一個(gè)有效影響范圍。當(dāng)目標(biāo)落入該范圍內(nèi)時(shí)，節(jié)點(diǎn)與之連邊的概率高于其他節(jié)點(diǎn)。因此，距離衰減函數(shù)本質(zhì)上具有與有限邊界相類似的約束范圍的思想和內(nèi)涵。事實(shí)上，有些基于距離衰減函數(shù)的空間網(wǎng)絡(luò)模型正是通過(guò)引入有限邊界的概念來(lái)幫助實(shí)現(xiàn)模型解析的[31]。但不管用哪種約束方式，通過(guò)調(diào)節(jié)約束強(qiáng)度，基本都能實(shí)現(xiàn)網(wǎng)絡(luò)度分布從冪律到指數(shù)再到高斯型分布的轉(zhuǎn)變。然而對(duì)于所有這些模型，有一種分布始終無(wú)法通過(guò)調(diào)節(jié)約束強(qiáng)度的方式產(chǎn)生，它就是在各類航空網(wǎng)絡(luò)中出現(xiàn)的雙段冪律度分布[1-3,32-34]。

雙段冪律分布在其分布的上下端分別具有兩種不同的標(biāo)度律特征，其互補(bǔ)累積分布表達(dá)為

(1)

式(1)中的γ1與γ2表示分布指數(shù)，kc表示分段點(diǎn)。除了航空網(wǎng)絡(luò)，這類分布還出現(xiàn)在語(yǔ)言網(wǎng)絡(luò)[35]、森林火災(zāi)的規(guī)模[36]、個(gè)人收入[37]、網(wǎng)站點(diǎn)擊次數(shù)[36]、龍卷風(fēng)的規(guī)模[36]、恐怖襲擊破壞程度以及人類行為等諸多復(fù)雜系統(tǒng)中[36,38]。實(shí)證得到的雙段冪律分布一般具有γ1<γ2，這里稱之為正雙段冪律。而γ1>γ2的情形，即反雙段冪律，似乎很少有見報(bào)道。關(guān)于雙段冪律分布的生成模型并不多，目前主要有Reed提出的基于幾何布朗運(yùn)動(dòng)的模型和Dorogovtsev、Mendes等人提出的語(yǔ)言網(wǎng)絡(luò)模型[35,39]。Reed發(fā)現(xiàn)若一隨機(jī)變量依據(jù)幾何布朗運(yùn)動(dòng)變化，且其演化時(shí)間本身還服從指數(shù)分布，則演化終態(tài)得到的變量服從雙段冪律分布[39]。該模型后來(lái)被Mitzenmacher詳述并進(jìn)一步衍生出其他變種[37,40-42]。但這些模型都不是網(wǎng)絡(luò)模型。此外Reed自己指出模型結(jié)果對(duì)指數(shù)分布的演化時(shí)間假設(shè)是敏感的。Dorogovtsev和Mendes在BA模型的基礎(chǔ)上引入了線性加速內(nèi)部連邊機(jī)制[35]。該模型可以產(chǎn)生雙段冪律度分布，此模型的機(jī)制與空間約束無(wú)關(guān)，且只針對(duì)語(yǔ)言網(wǎng)絡(luò)，其機(jī)制也未經(jīng)實(shí)證檢驗(yàn)。

既然空間約束可以導(dǎo)致度分布的過(guò)渡性轉(zhuǎn)變，那么是否也存在某種約束模式可以產(chǎn)生雙段冪律度分布？實(shí)際網(wǎng)絡(luò)的雙段冪律分布是否具有幾何學(xué)上的起源？解決這些問(wèn)題不僅有助于理解這類分布的形成原因，還能拓展對(duì)空間約束運(yùn)作機(jī)理的認(rèn)識(shí)。為此，本文提出了一種基于約束面積雙值跳變的空間網(wǎng)絡(luò)模型。它的核心機(jī)制可以簡(jiǎn)述為當(dāng)一個(gè)節(jié)點(diǎn)的度演化到預(yù)設(shè)的kc時(shí)，該節(jié)點(diǎn)的約束面積便會(huì)從初始S1跳變?yōu)镾2。換言之，模型要求約束強(qiáng)度本身具有動(dòng)力學(xué)演化的性質(zhì)。在現(xiàn)有的研究中，人們一般認(rèn)為約束強(qiáng)度只和網(wǎng)絡(luò)內(nèi)在空間屬性有關(guān)[43]，通常是不隨網(wǎng)絡(luò)演化而變化的。然而一些實(shí)證研究明確給出了空間約束具備演化行為的證據(jù)[25,44-45]。考慮到基于靜態(tài)空間約束的網(wǎng)絡(luò)模型都未能產(chǎn)生雙段冪律度分布，改用動(dòng)態(tài)約束似乎是一種必然的嘗試。事實(shí)上，我們認(rèn)為這可能就是解決雙段冪律問(wèn)題的關(guān)鍵。

本文的內(nèi)容安排如下：第1節(jié)給出約束面積雙值跳變的空間網(wǎng)絡(luò)模型的描述；第2節(jié)中對(duì)度分布進(jìn)行解析計(jì)算，并證明該模型產(chǎn)生的度分布會(huì)在演化初期呈現(xiàn)單段冪律，而當(dāng)有節(jié)點(diǎn)約束面積發(fā)生跳變后，網(wǎng)絡(luò)逐漸演化為雙段冪律；第3節(jié)對(duì)中國(guó)航空網(wǎng)絡(luò)進(jìn)行實(shí)證分析，驗(yàn)證模型機(jī)制對(duì)該真實(shí)網(wǎng)絡(luò)的適用性，并探討空間網(wǎng)絡(luò)中約束面積減小的可能原因；最后一節(jié)對(duì)本文的工作予以總結(jié)。

1 模型描述

本文的模型構(gòu)建在[0,10]×[0,10]的二維方形區(qū)域中，網(wǎng)絡(luò)通過(guò)不斷添加節(jié)點(diǎn)和邊而演化。我們遵循主流空間網(wǎng)絡(luò)模型的共同思想內(nèi)涵，賦予每個(gè)節(jié)點(diǎn)一個(gè)面積為S的約束范圍，其形狀規(guī)定為圓盤形。只有當(dāng)一個(gè)節(jié)點(diǎn)的約束范圍覆蓋了另一個(gè)節(jié)點(diǎn)u的位置時(shí)(即其影響能夠被u感知時(shí))，它才成為u連邊時(shí)的候選目標(biāo)。節(jié)點(diǎn)u僅在其候選目標(biāo)集合內(nèi)擇優(yōu)連一條邊。每個(gè)節(jié)點(diǎn)的初始約束范圍為S1，當(dāng)其度增長(zhǎng)到預(yù)設(shè)的kc時(shí)，其約束面積立刻跳變?yōu)镾2。模型具體演化規(guī)則描述如下：

1)在每時(shí)間步u，一個(gè)具有初始約束范圍S1的新節(jié)點(diǎn)(用u來(lái)標(biāo)記)加入網(wǎng)絡(luò)，它被隨機(jī)分配一個(gè)位置(x,y)。

3)檢查在此時(shí)間步中被u連接到的點(diǎn)，若連接后該節(jié)點(diǎn)的度達(dá)到預(yù)設(shè)的kc，令其約束面積等于S2。然后回到1)重復(fù)整個(gè)過(guò)程。

2 模型度分布的雙段冪律特征

令模型所在空間區(qū)域的總面積為A，節(jié)點(diǎn)i被新加入節(jié)點(diǎn)u選中連接的概率為

(2)

(3)

在模型演化的第一階段，所有節(jié)點(diǎn)度均未超過(guò)kc，此時(shí)網(wǎng)絡(luò)中只存在唯一的約束面積S1。將其代入式(2)，則模型直接退化為經(jīng)典的BA模型[46]，其互補(bǔ)累積度分布為P(k)=k-2。因此在這一階段，度分布僅表現(xiàn)為單段冪律。

當(dāng)有任意一個(gè)節(jié)點(diǎn)度值達(dá)到kc時(shí)，該節(jié)點(diǎn)的約束面積跳變到S2，網(wǎng)絡(luò)從此時(shí)起就存在兩種約束強(qiáng)度。式(3)因而對(duì)于不同度值范圍內(nèi)的節(jié)點(diǎn)具有兩種不同的表達(dá)

(4)

(5)

將式(5)代入f(t)的定義式中并用積分運(yùn)算替代求和，即

(6)

式(5)若為方程的真實(shí)解，式(6)關(guān)于f(t)的計(jì)算必須滿足解的假設(shè)條件f(t)=Ct。從而可得到自洽方程

(7)

由式(7)可以確定C，從而完成對(duì)ki(t)的求解。然后采用文獻(xiàn)[47]的方法可導(dǎo)出網(wǎng)絡(luò)在第二階段的互補(bǔ)累積度分布

(8)

為了驗(yàn)證以上理論分析，我們對(duì)模型進(jìn)行了蒙特卡羅模擬。圖1a～圖1b是取kc=15、S1=30和S2=10的網(wǎng)絡(luò)分別在演化初期(N=2 000)以及演化穩(wěn)定后(N=15 000)的累積度分布圖?？梢钥闯龆确植荚趦蓚€(gè)階段具有不同標(biāo)度律表現(xiàn)，早期網(wǎng)絡(luò)為單段冪律，而最終其演化為正雙段冪律。當(dāng)逐步增大S2時(shí)，模擬得到的穩(wěn)態(tài)累積度分布如圖1b～圖1d所示。在S2

圖1 kc=15時(shí)，不同模型參數(shù)下的累積度分布Fig.1 The cumulative degree distributions for different model parameters under kc=15

表1 雙段冪律度分布指數(shù)Tab.1 Exponents of double power law degree distribution

3 中國(guó)航空網(wǎng)實(shí)證

為評(píng)估模型的有效性，驗(yàn)證空間網(wǎng)絡(luò)中的雙段冪律度分布確有可能起源于空間約束面積的變化，本節(jié)將針對(duì)中國(guó)航空網(wǎng)絡(luò)(CAN)進(jìn)行實(shí)證分析。需要指出，由于本模型只提供了一個(gè)概念性的框架，并不涉及任何實(shí)際系統(tǒng)的細(xì)節(jié)，因此尋求模型與真實(shí)觀測(cè)量之間定量的匹配顯然超出模型的能力。然而，如果雙冪律度分布確實(shí)是由動(dòng)態(tài)空間約束引起的，那么我們理應(yīng)觀測(cè)到這種動(dòng)態(tài)約束造成的效應(yīng)，即連邊長(zhǎng)度在不同時(shí)間段的變化趨勢(shì)，而相應(yīng)的度分布標(biāo)度律演化特征原則上也應(yīng)該能觀測(cè)到。

3.1 航空網(wǎng)絡(luò)數(shù)據(jù)說(shuō)明

文中所用到的航線數(shù)據(jù)全部來(lái)自《中國(guó)交通年鑒》(1988-2014)，主要參照年鑒中統(tǒng)計(jì)表格《民航國(guó)內(nèi)主要航線運(yùn)輸完成情況》中的航線。本文收集了跨度接近30年的CAN數(shù)據(jù)，可供我們建立每一年的網(wǎng)絡(luò)拓?fù)洳⑦M(jìn)行長(zhǎng)時(shí)間的動(dòng)態(tài)分析。

網(wǎng)絡(luò)數(shù)據(jù)處理方法：

1)以通航的城市作為網(wǎng)絡(luò)的節(jié)點(diǎn)。如果城市對(duì)之間實(shí)現(xiàn)了通航，那么兩節(jié)點(diǎn)間就存在連邊。最終某一城市的連邊數(shù)目也即通航城市數(shù)，就是它在CAN中的度。

2)經(jīng)停航線納入統(tǒng)計(jì)。以經(jīng)停2個(gè)城市的A-B-C-D航線為例，其中字母代表城市，該航線可分解為A-B、B-C、C-D 3個(gè)航段，每段按直飛航線處理，不區(qū)分航路方向。需要說(shuō)明的是，我們主要采集了大陸區(qū)域的航線數(shù)據(jù)，不包括港澳臺(tái)地區(qū)。

航線距離采集方法：任意一對(duì)空港城市間的航線距離都可以從Great Circle Mapper網(wǎng)站獲得(http://www.gcmap.com/)。在該網(wǎng)站中，只要輸入航線中機(jī)場(chǎng)對(duì)的三字碼(IATA碼)或四字碼(ICAO碼)，就能采集到兩地之間的飛行距離。

3.2 中國(guó)航空網(wǎng)中非平穩(wěn)的度分布演化特征

到目前為止，已有不少針對(duì)CAN的拓?fù)浣Y(jié)構(gòu)、流量動(dòng)態(tài)、結(jié)構(gòu)魯棒性和服務(wù)質(zhì)量的研究[2-4,48]。這些研究都證實(shí)了CAN具有典型的雙段冪律度分布。但幾乎所有這些研究的數(shù)據(jù)都采集于2002年以后，那時(shí)雙段冪律度分布已經(jīng)形成，從而無(wú)法辨識(shí)其可能存在的標(biāo)度律演化特征。本研究追溯至CAN演化的早期，將觀測(cè)時(shí)間提前至1988年，這比以前的研究都要早得多。

1988-2014期間CAN度分布的部分結(jié)果如圖2所示。從圖2a～圖2b可看出在20世紀(jì)90年代早期至中期，度分布并不是雙段冪律而是呈現(xiàn)明顯的單段冪律特征。而在大約1999年左右，網(wǎng)絡(luò)從單段冪律轉(zhuǎn)換為雙段冪律，并一直維持這一特征至今。圖2c～圖2d顯示了2002年和2010年的CAN度分布，其為明顯的雙段冪律。經(jīng)測(cè)量分段點(diǎn)kc≈22，這與先前的實(shí)證研究結(jié)果吻合[3,41]。因此CAN的雙段冪律度分布并不是一開始就形成的，而是首先出現(xiàn)單一標(biāo)度律并逐漸演化成雙段冪律。這一結(jié)果完全吻合我們的模型對(duì)雙段冪律分布形成過(guò)程的預(yù)言，但卻無(wú)法由已有的其他相關(guān)模型解釋。Reed和Mitzenmacher等人的模型[39-40]沒有給出任何關(guān)于分布演化的動(dòng)力學(xué)信息，且就其推導(dǎo)來(lái)看，他們的模型不具有實(shí)證中看到的冪律段接連出現(xiàn)的過(guò)程。Dorogovtsev和Mendes提出的語(yǔ)言網(wǎng)絡(luò)模型[35]的度分布是含時(shí)的，但含時(shí)項(xiàng)并不處于指數(shù)項(xiàng)，即其標(biāo)度律特征依然是穩(wěn)定，這同樣無(wú)法吻合目前的觀測(cè)結(jié)果。此外Dorogovtsev和Mendes指出，在他們的模型中，度值大于分段點(diǎn)的節(jié)點(diǎn)集是恒定的。這與CAN情況不符合，因?yàn)槲覀兠黠@可以看到不斷有新節(jié)點(diǎn)城市加入到第二段冪律中去，比如深圳城市就是后續(xù)加入到第二段冪律段中的。

圖2 中國(guó)航空網(wǎng)在不同年份的度分布Fig.2 Degree distributions of Chinese aviation network for different years

3.3 航線距離的演化特征

依照模型，度分布為正雙段冪律的網(wǎng)絡(luò)，其節(jié)點(diǎn)在跨越分段點(diǎn)kc后，約束面積將變小。為驗(yàn)證這一機(jī)制是否存在，本研究分析了每個(gè)空港城市在通航數(shù)經(jīng)歷kc≈22前后的約束范圍的變化情況。我們將平均連邊距離作為對(duì)約束空間范圍的估計(jì)，如果分段點(diǎn)前后該距離在統(tǒng)計(jì)上有變小的趨勢(shì)，這種趨勢(shì)結(jié)合系統(tǒng)表現(xiàn)出的正雙段冪律分布就完全吻合我們模型的預(yù)言。

對(duì)于每個(gè)空港城市，選取其演化過(guò)程中度值未超過(guò)kc的最后一年(記作Y，該年對(duì)不同節(jié)點(diǎn)是不同的)，計(jì)算此時(shí)它所擁有的所有航線的距離平均值。然后選取該節(jié)點(diǎn)度值超過(guò)kc后的最后一年，即2014年，將該年里其航線中與Y共有的航線去除，計(jì)算剩下航線的平均距離。這樣就能分別獲得該節(jié)點(diǎn)在kc前后的約束空間范圍的估計(jì)。然后通過(guò)比較各節(jié)點(diǎn)在到達(dá)kc前后連邊平均距離的大小，便能看出約束空間范圍變化的趨勢(shì)。需要說(shuō)明的是，CAN度分布的特征決定了大部分節(jié)點(diǎn)從沒能演化到超過(guò)kc，因此這些節(jié)點(diǎn)無(wú)法納入我們的統(tǒng)計(jì)和比較中。剔除這些節(jié)點(diǎn)后，還剩下29個(gè)空港城市。相比于網(wǎng)絡(luò)的總節(jié)點(diǎn)數(shù)雖然少了很多，但若這些節(jié)點(diǎn)表現(xiàn)出統(tǒng)計(jì)上明顯的趨勢(shì)，則結(jié)果依然具有可信度。

將各個(gè)空港城市在達(dá)到kc前與后的平均連邊距離作比，所得結(jié)果如圖3所示。圖中橫坐標(biāo)為賦予節(jié)點(diǎn)的標(biāo)號(hào)，縱坐標(biāo)為計(jì)算得到的比值。若比值大于1，則表明該節(jié)點(diǎn)的空間約束范圍在到達(dá)kc后變小。圖3里29個(gè)數(shù)據(jù)點(diǎn)中有22個(gè)數(shù)據(jù)點(diǎn)比值大于1，僅7個(gè)點(diǎn)小于1。這個(gè)結(jié)果表明，節(jié)點(diǎn)的約束空間在分段點(diǎn)前后具有統(tǒng)計(jì)上明顯減小的趨勢(shì)。而在該趨勢(shì)下網(wǎng)絡(luò)形成了正雙段冪律度分布，這完全吻合了本模型的預(yù)言。

圖3 29個(gè)空港城市在kc前后的平均連邊距離的比值Fig.3 Ratios of average distance of edges of 29 airport cities before and after kc

3.4 關(guān)于約束面積變化的原因

如果空間約束是跳變減小的，那么是什么因素造成了這一結(jié)果？本文從預(yù)算和成本的角度出發(fā)，提出一種可能的解釋。

我們假設(shè)空間網(wǎng)絡(luò)中的連邊可以分為兩類，一類是與成本成正比的長(zhǎng)程連邊，另一類是地理上相鄰節(jié)點(diǎn)之間無(wú)需代價(jià)即可形成的局部連邊。這意味著連邊長(zhǎng)度有兩種不同的尺度，即與整個(gè)空間的線性尺度成比例的長(zhǎng)邊L以及無(wú)需代價(jià)但只能局部連接的短邊尺度l。事實(shí)上，一些推廣的Kerlinberg模型就是采用類似的假設(shè)[49-51]，而一些實(shí)證研究也證實(shí)了空間網(wǎng)絡(luò)中連邊長(zhǎng)度具有的兩種尺度的現(xiàn)象[52]。假定每個(gè)節(jié)點(diǎn)用來(lái)構(gòu)造連邊的預(yù)算B～kcL，在初始階段，充足的預(yù)算允許它原則上將任何其他節(jié)點(diǎn)作為潛在的連接目標(biāo)，因而這一時(shí)期獲取的連邊平均長(zhǎng)度的規(guī)模約為L(zhǎng)。隨著邊數(shù)的增多，該節(jié)點(diǎn)剩余的預(yù)算不斷減少且每次平均減少大約L，該過(guò)程一直持續(xù)到預(yù)算降為B～L，然后只再需一個(gè)長(zhǎng)程連邊便可耗盡預(yù)算。而在隨后的演化中，只有尺度為l的局部連接可用了。這便導(dǎo)致了本模型所描述的當(dāng)節(jié)點(diǎn)達(dá)到某一臨界度時(shí)，空間約束面積陡然縮減的效果，而分段點(diǎn)kc則刻畫了節(jié)點(diǎn)構(gòu)建連邊的總預(yù)算。

4 結(jié)論

本文提出了一種基于約束面積雙值跳變的空間網(wǎng)絡(luò)模型，該模型在演化的初期產(chǎn)生了單段冪律度分布，而后逐漸轉(zhuǎn)變?yōu)殡p段冪律。通過(guò)改變跳變前后約束面積的相對(duì)大小，模型可以產(chǎn)生正反雙段兩種冪律度分布。這些結(jié)果通過(guò)解析方式得到，并經(jīng)模擬仿真定量驗(yàn)證。為檢驗(yàn)?zāi)Ｐ偷倪m用性，本文對(duì)中國(guó)航空網(wǎng)絡(luò)進(jìn)行了實(shí)證分析。分析結(jié)果不僅表明度分布的演變過(guò)程恰如模型所預(yù)言，還直接觀測(cè)到了模型所要求的約束面積減小的趨勢(shì)。最后我們從預(yù)算和成本的角度出發(fā)，探討了空間約束跳變減小的可能原因并指出分段點(diǎn)kc的物理意義。這些結(jié)果為雙段冪律分布的起源提供了一種新的解釋，同時(shí)拓展了對(duì)空間約束運(yùn)作機(jī)制的認(rèn)識(shí)。