邊界增長網絡模型的演化性質

劉 霞，姚東任，姚 兵

（1.西北師范大學數學與統計學院，甘肅 蘭州730070；2.西北師范大學計算機科學與工程學院，甘肅 蘭州730070）

1 預備知識

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

已知很多動態網絡（dynamic network）可以表示成N（t）＝（P（u，k，t），G（t），UG），t∈［a，b］.其中P（u，k，t）是一個節點u和k 個節點連接的概率，G（t）是N（t）的連通拓撲結構，UG 是N（t）在時間區間［a，b］上的底圖［4］.當概率P（u，k，t）服從冪率分布k－α，2＜α＜3，則稱G（t）為無標度圖，G（a）為初始化圖，N（t）為無標度網絡（scale－free network）［5－9］.當前，利用圖論的理論和技術來研究動態網絡成為一個有效且有力的手段.為動態網絡建立數學模型，或者建立數學模型來模擬實際網絡已經成為不可缺少的技術環節［9－10］.受文獻［9］的研究技術啟發，本文構造了一種新的邊界增長網絡模型，并對這類網絡模型的主要特性進行研究，進而證明了這類網絡模型的無標度性.為探索網絡無標度性的必要條件，設計了新的統計指標：邊累積分布，節點數目比和邊數目比，并將此在本文的邊界增長網絡模型中加以應用.

2 邊界增長網絡模型

2.1 基本參數

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

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

其中：Xt表示t時刻新增節點的集合，Yt表示時間步驟t時新增邊的集合.因為

不難得到N（t）的節點數目和邊數目分別如下：

邊界增長網絡N（k）的新增加節點數目

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

平均度〈k〉說明邊界增長網絡N（t）是一個稀疏網絡，也是樹型網絡.公式（3）表明N（t）具有優先鏈接性，即新進入N（t）的節點與初始網絡中的節點相連線.同時，N（t）的構造表明N（t）具有增長性.故N（t）屬于BA 無標度模型.

圖1 當m＝3時，N（0）＝K3 和N（1）網絡生成示意圖

圖2 當m＝3時，N（2）及N（3）網絡生成示意圖

2.2 度分布性質

下面將證明邊界增長網絡N（t）的無標度性與初始網絡N（0）的結構無關（計算方法參見文獻［9］）.

設d1，d2，…，da為初始網絡N（0）的全體不相同的度，ndj（0）為具有度數dj的節點的個數.不妨設d1＞d2＞…＞da.則初始網絡N（0）的度數為dj的節點在邊界增長網絡N（k）（k≥1）中的度數為2k－1m·dj，且記號k（i，N（t））表示t時刻節點i 的度數，P（k）表示隨機選擇恰好連接k條邊的節點的概率，tc，i表示節點i被新增進網絡的時刻.由于k（i，N（t＋1））＝k（i，N（t））＋2m，且k（i，N（tc，i））＝2.所以

注意到tc，i∈｛1，2，…，t｝，邊界增長網絡N（t）中度數d＝2，2＋2m，2＋4m，…，2＋2（t－1）m，2＋2tm，2t－1m·da，2t－1m·da－1，…，2t－1m·d1的 節 點 的 個 數通常，稱上述邊界增長網絡N（t）的度數和節點個數的關系為N（t）的度譜（degree spectrum）.

邊界增長網絡N（t）的連接概率P（k）（connection probability）.

注意到N（t）的度譜屬于離散型，下面計算邊界增長網絡N（t）的隨機選擇恰好有k 條邊的節點的概率P（k）.根據（4）式，

故邊界增長網絡N（t）服從指數分布，即是無標度網絡.

2.3 聚類系數

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

可以估計

以及

那么，唯一的可能性是〈c〉→1（m→∞，t→∞），即邊界增長網絡N（t）具有高聚類性質.

3 其他統計指標

基于實際問題研究的需要，我們提出以下統計指標，期望能更好地研究增長型網絡.

3.1 邊累積分布

當τ＜t時，τ時刻N（τ）的節點i的度K（i，N（τ））之和記為∑K（i，N（τ））；時間步驟t時，N（t）的節點j的度K（j，N（t））之和記為∑K（j，N（t））.定義邊界增長網絡N（t）的邊累積分布（edge－cumulative distribution）為

根據（3）式，當t較大時，

且

進而有

（10）式表明，邊界增長網絡N（t）的邊累積分布Pe－cum（k）服從無標度分布.

3.2 （αk，βk）－增長網絡模型

首先，計算邊界增長網絡N（t）中度數不大于k的節點總數

取k＝2（t－r）m，節點數目比（node－number proportion）為

則當t很大時，有

其次，計算邊界增長網絡N（t）中度數不大于k的節點的度數總和

令

得

解得 取k＝2（t－r）m，計算邊數目比（edge－number proportion）

同理得

所以，邊界增長網絡N（t）可稱為（αk，βk）－增長網絡模型.

4 結論與問題

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

［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.