邊界增長(zhǎng)網(wǎng)絡(luò)模型的演化性質(zhì)

劉 霞，姚東任，姚 兵

（1.西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 蘭州730070；2.西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，甘肅 蘭州730070）

1 預(yù)備知識(shí)

關(guān)于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)研究是當(dāng)今網(wǎng)絡(luò)研究中的關(guān)鍵課題.1959年，P.Erd?s和A.Rényi首先研究了在隨機(jī)網(wǎng)絡(luò)中最大和最小度的分布［1］，Bollobás（1981）隨后得到了所有度分布的形式.D.J.Watts和S.H.Strogatz在1998年結(jié)合規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)的特點(diǎn)給出了（WS）小世界網(wǎng)絡(luò)的生成機(jī)制模型［2］.小世界網(wǎng)絡(luò)是在規(guī)則網(wǎng)絡(luò)的基礎(chǔ)上加入隨機(jī)性產(chǎn)生的，即對(duì)規(guī)則網(wǎng)絡(luò)的每一個(gè)節(jié)點(diǎn)的所有邊（節(jié)點(diǎn)之間的連線），以概率p 斷開一個(gè)端節(jié)點(diǎn)，并重新連接，連接的新端節(jié)點(diǎn)從網(wǎng)絡(luò)中的其他節(jié)點(diǎn)里隨機(jī)選擇，如果選擇的節(jié)點(diǎn)已經(jīng)與此節(jié)點(diǎn)相連，則再隨機(jī)的選擇其他節(jié)點(diǎn)來(lái)重新連線.在復(fù)雜網(wǎng)絡(luò)的研究中，網(wǎng)絡(luò)如果同時(shí)具有大聚集程度和小最短路徑這兩個(gè)性質(zhì)，就說(shuō)它具有小世界效應(yīng).1999年，美國(guó)的物理學(xué)家A.L.Barabási和他的博士生R.Albert進(jìn)行萬(wàn)維網(wǎng)的研究時(shí)，發(fā)現(xiàn)通過(guò)超鏈接與網(wǎng)頁(yè)、文件所構(gòu)成的萬(wàn)維網(wǎng)網(wǎng)絡(luò)并不是如一般的隨機(jī)網(wǎng)絡(luò)一樣，有著均勻的度分布［3］.他們發(fā)現(xiàn)萬(wàn)維網(wǎng)是由少數(shù)高連接性的頁(yè)面串聯(lián)起來(lái)的.絕大多數(shù)（超過(guò)80%）的網(wǎng)頁(yè)只有不超過(guò)4個(gè)超鏈接，但極少數(shù)頁(yè)面（不到總頁(yè)面數(shù)的1／10 000）卻擁有超過(guò)1 000個(gè)的鏈接，個(gè)別文件甚至與超過(guò)200萬(wàn)個(gè)其他頁(yè)面相連.所謂的無(wú)標(biāo)度，是指雖然網(wǎng)絡(luò)中大部分節(jié)點(diǎn)的度不高，但極少數(shù)節(jié)點(diǎn)的度不受任何限制，可以變得十分巨大.冪率度分布使網(wǎng)絡(luò)在小世界特有的基礎(chǔ)上又具備了許多新的性質(zhì).網(wǎng)絡(luò)的大部分節(jié)點(diǎn)度值都很低，但存在著度值非常高的中樞節(jié)點(diǎn)，這種關(guān)鍵的節(jié)點(diǎn)的存在使得無(wú)尺度網(wǎng)絡(luò)對(duì)意外故障有強(qiáng)大的承受能力，但面對(duì)協(xié)同性攻擊時(shí)則顯得脆弱.現(xiàn)實(shí)中的許多網(wǎng)絡(luò)都帶有無(wú)標(biāo)度的特性.例如，社會(huì)人際網(wǎng)絡(luò)，信息交換網(wǎng)（萬(wàn)維網(wǎng)、國(guó)際互聯(lián)網(wǎng)、電話網(wǎng)），社會(huì)網(wǎng)絡(luò)（金融系統(tǒng)網(wǎng)絡(luò)、科研合作網(wǎng)、交通網(wǎng)），生物網(wǎng)絡(luò)（細(xì)胞網(wǎng)絡(luò)、生態(tài)網(wǎng)絡(luò)）等等.

已知很多動(dòng)態(tài)網(wǎng)絡(luò)（dynamic network）可以表示成N（t）＝（P（u，k，t），G（t），UG），t∈［a，b］.其中P（u，k，t）是一個(gè)節(jié)點(diǎn)u和k 個(gè)節(jié)點(diǎn)連接的概率，G（t）是N（t）的連通拓?fù)浣Y(jié)構(gòu)，UG 是N（t）在時(shí)間區(qū)間［a，b］上的底圖［4］.當(dāng)概率P（u，k，t）服從冪率分布k－α，2＜α＜3，則稱G（t）為無(wú)標(biāo)度圖，G（a）為初始化圖，N（t）為無(wú)標(biāo)度網(wǎng)絡(luò)（scale－free network）［5－9］.當(dāng)前，利用圖論的理論和技術(shù)來(lái)研究動(dòng)態(tài)網(wǎng)絡(luò)成為一個(gè)有效且有力的手段.為動(dòng)態(tài)網(wǎng)絡(luò)建立數(shù)學(xué)模型，或者建立數(shù)學(xué)模型來(lái)模擬實(shí)際網(wǎng)絡(luò)已經(jīng)成為不可缺少的技術(shù)環(huán)節(jié)［9－10］.受文獻(xiàn)［9］的研究技術(shù)啟發(fā)，本文構(gòu)造了一種新的邊界增長(zhǎng)網(wǎng)絡(luò)模型，并對(duì)這類網(wǎng)絡(luò)模型的主要特性進(jìn)行研究，進(jìn)而證明了這類網(wǎng)絡(luò)模型的無(wú)標(biāo)度性.為探索網(wǎng)絡(luò)無(wú)標(biāo)度性的必要條件，設(shè)計(jì)了新的統(tǒng)計(jì)指標(biāo)：邊累積分布，節(jié)點(diǎn)數(shù)目比和邊數(shù)目比，并將此在本文的邊界增長(zhǎng)網(wǎng)絡(luò)模型中加以應(yīng)用.

2 邊界增長(zhǎng)網(wǎng)絡(luò)模型

2.1 基本參數(shù)

對(duì)任意給定的至少有2個(gè)節(jié)點(diǎn)的連通網(wǎng)絡(luò)N（0），用記號(hào)nv（0）和ne（0）分別表示它的節(jié)點(diǎn)個(gè)數(shù)和邊數(shù)目，記號(hào)V（0）和E（0）分別表示網(wǎng)絡(luò)N（0）的節(jié)點(diǎn)集合和邊集合，使得n0（0）＝｜V（0）｜，ne（0）＝｜E（0）｜.對(duì)于網(wǎng)絡(luò)N（0）的每一條邊uv∈E（0），新增加m 個(gè)節(jié)點(diǎn)，并且將這m 個(gè)節(jié)點(diǎn)與節(jié)點(diǎn)u，v 分別相連，產(chǎn)生t＝1時(shí)刻的網(wǎng)絡(luò)N（1），并將最后一個(gè)新節(jié)點(diǎn)w 與節(jié)點(diǎn)u，v 分別相連所得的邊wu 和邊wv定義為網(wǎng)絡(luò)N（1）的邊界邊（bound edge）.記號(hào)X1代表N（0）新增加節(jié)點(diǎn)的集合，Y1代表新增加的邊集合，則有Y1＝｛wu，wv：uv∈E（0），w∈X1｝，以及V（1）＝V（0）∪X1，E（1）＝E（0）∪Y1，｜Y1｜＝2·｜X1｜＝2mne（0）.

類似地，對(duì)于網(wǎng)絡(luò)N（1）的每條邊界邊xy∈E（1），新增加m 個(gè)新節(jié)點(diǎn)，并且將這m 個(gè)節(jié)點(diǎn)分別與節(jié)點(diǎn)x 和節(jié)點(diǎn)y 相連，從而得到t＝2時(shí)刻的網(wǎng)絡(luò)N（2），并將最后一個(gè)新節(jié)點(diǎn)z與節(jié)點(diǎn)x，y 分別相連所得的邊zx 和zy 定義為網(wǎng)絡(luò)N（2）的邊界邊，顯然有V（2）＝V（1）∪X2，E（2）＝E（1）∪Y2.依此類推，從網(wǎng)絡(luò)N（t－1）可得到網(wǎng)絡(luò)N（t）.以下稱N（t）為邊界增長(zhǎng)網(wǎng)絡(luò)模型（bound growing network model），簡(jiǎn)稱為邊界增長(zhǎng)網(wǎng)絡(luò)；稱N（0）為初始網(wǎng)絡(luò)（initial network）.見圖1—2.下面給出邊界增長(zhǎng)網(wǎng)絡(luò)N（t）的一些基本參數(shù).對(duì)t≥1，邊界增長(zhǎng)網(wǎng)絡(luò)N（t）的節(jié)點(diǎn)集合V（t）與邊集合E（t）分別為：

其中：Xt表示t時(shí)刻新增節(jié)點(diǎn)的集合，Yt表示時(shí)間步驟t時(shí)新增邊的集合.因?yàn)?/p>

不難得到N（t）的節(jié)點(diǎn)數(shù)目和邊數(shù)目分別如下：

邊界增長(zhǎng)網(wǎng)絡(luò)N（k）的新增加節(jié)點(diǎn)數(shù)目

且有2kne（0）條邊界邊，最大度Δ（N（t））＝（tm＋1）·Δ（N（0）），最小度δ（N（t））＝2.此外，N（t）的平均度

平均度〈k〉說(shuō)明邊界增長(zhǎng)網(wǎng)絡(luò)N（t）是一個(gè)稀疏網(wǎng)絡(luò)，也是樹型網(wǎng)絡(luò).公式（3）表明N（t）具有優(yōu)先鏈接性，即新進(jìn)入N（t）的節(jié)點(diǎn)與初始網(wǎng)絡(luò)中的節(jié)點(diǎn)相連線.同時(shí)，N（t）的構(gòu)造表明N（t）具有增長(zhǎng)性.故N（t）屬于BA 無(wú)標(biāo)度模型.

圖1 當(dāng)m＝3時(shí)，N（0）＝K3 和N（1）網(wǎng)絡(luò)生成示意圖

圖2 當(dāng)m＝3時(shí)，N（2）及N（3）網(wǎng)絡(luò)生成示意圖

2.2 度分布性質(zhì)

下面將證明邊界增長(zhǎng)網(wǎng)絡(luò)N（t）的無(wú)標(biāo)度性與初始網(wǎng)絡(luò)N（0）的結(jié)構(gòu)無(wú)關(guān)（計(jì)算方法參見文獻(xiàn)［9］）.

設(shè)d1，d2，…，da為初始網(wǎng)絡(luò)N（0）的全體不相同的度，ndj（0）為具有度數(shù)dj的節(jié)點(diǎn)的個(gè)數(shù).不妨設(shè)d1＞d2＞…＞da.則初始網(wǎng)絡(luò)N（0）的度數(shù)為dj的節(jié)點(diǎn)在邊界增長(zhǎng)網(wǎng)絡(luò)N（k）（k≥1）中的度數(shù)為2k－1m·dj，且記號(hào)k（i，N（t））表示t時(shí)刻節(jié)點(diǎn)i 的度數(shù)，P（k）表示隨機(jī)選擇恰好連接k條邊的節(jié)點(diǎn)的概率，tc，i表示節(jié)點(diǎn)i被新增進(jìn)網(wǎng)絡(luò)的時(shí)刻.由于k（i，N（t＋1））＝k（i，N（t））＋2m，且k（i，N（tc，i））＝2.所以

注意到tc，i∈｛1，2，…，t｝，邊界增長(zhǎng)網(wǎng)絡(luò)N（t）中度數(shù)d＝2，2＋2m，2＋4m，…，2＋2（t－1）m，2＋2tm，2t－1m·da，2t－1m·da－1，…，2t－1m·d1的 節(jié) 點(diǎn) 的 個(gè) 數(shù)通常，稱上述邊界增長(zhǎng)網(wǎng)絡(luò)N（t）的度數(shù)和節(jié)點(diǎn)個(gè)數(shù)的關(guān)系為N（t）的度譜（degree spectrum）.

邊界增長(zhǎng)網(wǎng)絡(luò)N（t）的連接概率P（k）（connection probability）.

注意到N（t）的度譜屬于離散型，下面計(jì)算邊界增長(zhǎng)網(wǎng)絡(luò)N（t）的隨機(jī)選擇恰好有k 條邊的節(jié)點(diǎn)的概率P（k）.根據(jù)（4）式，

故邊界增長(zhǎng)網(wǎng)絡(luò)N（t）服從指數(shù)分布，即是無(wú)標(biāo)度網(wǎng)絡(luò).

2.3 聚類系數(shù)

對(duì)邊界增長(zhǎng)網(wǎng)絡(luò)N（t）的節(jié)點(diǎn)i，記號(hào)Ei表示與節(jié)點(diǎn)i相鄰的ki個(gè)節(jié)點(diǎn)間實(shí)際的邊數(shù)表示ki個(gè)節(jié)點(diǎn)間最大的邊數(shù)，那么節(jié)點(diǎn)i 的聚類系數(shù)是圖G 的 聚 類 系 數(shù)〈c〉＝當(dāng)新節(jié)點(diǎn)i加入邊界增長(zhǎng)網(wǎng)絡(luò)N（t）時(shí)，它的度ki和Ei分別為2和1.當(dāng)節(jié)點(diǎn)的度數(shù)每增加2m 時(shí)，Ei也增加2m，也就是說(shuō)節(jié)點(diǎn)i的度ki隨著時(shí)間增加時(shí)，它所對(duì)應(yīng)的Ei增加相同的數(shù)目，而最開始時(shí)E1＝k1－1，也就是Ei始終比ki多1，即Ei＝ki－1.對(duì)于任意度為k的節(jié)點(diǎn)，聚類系數(shù)C〈k〉＝即C〈k〉～k－1.令kr＝2＋2（t－r）m 表示N（t）中標(biāo)號(hào)為r的節(jié)點(diǎn)的度，可以算出度為kr的節(jié)點(diǎn)的聚類系數(shù)為再令Δnv（r）（0≤r≤t）表示度為kr的節(jié)點(diǎn)的數(shù)目（由上面的度譜可以得到），所謂求網(wǎng)絡(luò)的聚類系數(shù)，也就是求它的所有節(jié)點(diǎn)的聚類系數(shù)的平均值，將度相同的節(jié)點(diǎn)的聚類系數(shù)與節(jié)點(diǎn)的數(shù)目相乘再相加，然后除以網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù).所以，對(duì)任意t時(shí)刻，邊界增長(zhǎng)網(wǎng)絡(luò)N（t）的聚類系數(shù)

可以估計(jì)

以及

那么，唯一的可能性是〈c〉→1（m→∞，t→∞），即邊界增長(zhǎng)網(wǎng)絡(luò)N（t）具有高聚類性質(zhì).

3 其他統(tǒng)計(jì)指標(biāo)

基于實(shí)際問(wèn)題研究的需要，我們提出以下統(tǒng)計(jì)指標(biāo)，期望能更好地研究增長(zhǎng)型網(wǎng)絡(luò).

3.1 邊累積分布

當(dāng)τ＜t時(shí)，τ時(shí)刻N(yùn)（τ）的節(jié)點(diǎn)i的度K（i，N（τ））之和記為∑K（i，N（τ））；時(shí)間步驟t時(shí)，N（t）的節(jié)點(diǎn)j的度K（j，N（t））之和記為∑K（j，N（t））.定義邊界增長(zhǎng)網(wǎng)絡(luò)N（t）的邊累積分布（edge－cumulative distribution）為

根據(jù)（3）式，當(dāng)t較大時(shí)，

且

進(jìn)而有

（10）式表明，邊界增長(zhǎng)網(wǎng)絡(luò)N（t）的邊累積分布Pe－cum（k）服從無(wú)標(biāo)度分布.

3.2 （αk，βk）－增長(zhǎng)網(wǎng)絡(luò)模型

首先，計(jì)算邊界增長(zhǎng)網(wǎng)絡(luò)N（t）中度數(shù)不大于k的節(jié)點(diǎn)總數(shù)

取k＝2（t－r）m，節(jié)點(diǎn)數(shù)目比（node－number proportion）為

則當(dāng)t很大時(shí)，有

其次，計(jì)算邊界增長(zhǎng)網(wǎng)絡(luò)N（t）中度數(shù)不大于k的節(jié)點(diǎn)的度數(shù)總和

令

得

解得 取k＝2（t－r）m，計(jì)算邊數(shù)目比（edge－number proportion）

同理得

所以，邊界增長(zhǎng)網(wǎng)絡(luò)N（t）可稱為（αk，βk）－增長(zhǎng)網(wǎng)絡(luò)模型.

4 結(jié)論與問(wèn)題

我們推廣了文獻(xiàn)［9］的增長(zhǎng)型網(wǎng)絡(luò)模型，得到并計(jì)算了新網(wǎng)絡(luò)模型的冪律度分布、聚類系數(shù)等；提出了網(wǎng)絡(luò)研究的新統(tǒng)計(jì)指標(biāo)：邊累積分布、節(jié)點(diǎn)數(shù)目比率與邊數(shù)目和比率下的（αk，βk）－增長(zhǎng)網(wǎng)絡(luò)模型.顯然，還需要對(duì)新的隨機(jī)統(tǒng)計(jì)指標(biāo)在其他的網(wǎng)絡(luò)模型中進(jìn)行廣泛及深入地測(cè)試，修正其準(zhǔn)確度、提高其精度.必須注意到，邊界增長(zhǎng)型網(wǎng)絡(luò)N（t）在每一時(shí)刻t只有新進(jìn)入網(wǎng)絡(luò)的外部節(jié)點(diǎn)與N（t）內(nèi)的節(jié)點(diǎn)可以連線，N（t）內(nèi)的節(jié)點(diǎn)的度數(shù)和連線方式不再發(fā)生變化，即沒(méi)有N（t）內(nèi)的重新連線和添加新的連線.如果考慮邊界增長(zhǎng)型網(wǎng)絡(luò)N（t）內(nèi)的隨機(jī)重新連線或者隨機(jī)添加新的連線，所得到的模型對(duì)實(shí)際網(wǎng)絡(luò)進(jìn)行模擬則會(huì)更好些.

［1］ERD?S P，RéNYI A.On random graphs［J］.Publ Math Debrecen，1959（6）：290－297.

［2］WATTS D J，STROGATZ S H.Collective dynamics of‘small－world’networks［J］.Nature，1998，393：440－442.

［3］BARABáSI A L，ALBERT R.Emergence of scaling in random networks［J］.Science，1999，286：509－512.

［4］YAO BING，YANG CHAO，YAO MING，et al.Graphs as models of scale－free networks［J］.Applied Mechanics and Materials，2013，380／384：2034－2037.

［5］BONDY J A，MURTY U S R.Graph theory with applications［M］.London：Macmillan，1976：35－41.

［6］KIM D H，NOH J D，JEONG H.Scale－free trees：the skeletons of complex networks［J］.Physical Review E，2004，70，04612：1－5.

［7］LI L，ALDERSON D，TANAKA R，et al.Towards a theory of scale－free graphs：definition，properties，and implications［J］.Internet Mathematics，2005，2（4）：431－523.

［8］YAO BING，ZHANG ZHONG－FU，WANG JIAN－FANG.Some results on spanning trees［J］.Acta Mathematicae Applicatae Sinica：English Series，2010，26（4）：607－616.

［9］ZHANG ZHONG－ZHI，RONG LI－LI，GUO CHONG－HUI.A deterministic small－world network created by edge iterations［J］.Physica A，2006，363：567－572.

［10］SAGY B，MIRA G，AVISHAI W.An incremental super－linear preferential Internet topology model［J］.LNCS，2004，3015：53－62.