復(fù)雜網(wǎng)絡(luò)模型比較研究

阿布力米提·艾西丁

摘要：復(fù)雜網(wǎng)絡(luò)屬于大型網(wǎng)絡(luò)系統(tǒng)，擁有相對復(fù)雜的拓?fù)浣Y(jié)構(gòu)，由諸多節(jié)點通過相互連接構(gòu)成，其動力行為具備動態(tài)性和多樣性，比如神經(jīng)網(wǎng)絡(luò)、食物鏈接網(wǎng)絡(luò)、社會網(wǎng)絡(luò)等自然形成的復(fù)雜網(wǎng)絡(luò)；與此同時，人類還不斷地建造了互聯(lián)網(wǎng)、電力網(wǎng)、萬維網(wǎng)、交通網(wǎng)絡(luò)等復(fù)雜網(wǎng)絡(luò)。該文論述復(fù)雜網(wǎng)絡(luò)基本概念與復(fù)雜網(wǎng)絡(luò)模型，同時對復(fù)雜網(wǎng)絡(luò)模型進行比較。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；網(wǎng)絡(luò)模型；網(wǎng)絡(luò)特性

中圖分類號：TP393 文獻標(biāo)識碼：A 文章編號：1009-3044（2017）03-0023-02

1 基本概念

所謂“網(wǎng)絡(luò)”（networks），實際上就是節(jié)點（node）和連邊（edge）的集合。若節(jié)點相對（i，j）和（j，i）的邊是相同的，則它就是無向網(wǎng)絡(luò)；如果不是相同的邊，那么就是有向型的。當(dāng)將權(quán)值賦給各邊時，就得到了加權(quán)網(wǎng)絡(luò)，若不賦值，就是無權(quán)型的，具體如下圖：

如果根據(jù)特定規(guī)律將各節(jié)點連邊到一起，那么就能獲得圖2所示規(guī)則網(wǎng)絡(luò)。若根據(jù)任意形式將節(jié)點各邊連到一起，那么就能獲得隨機網(wǎng)絡(luò)。

通?？梢杂媒閿?shù)、度分布、平均路徑長度等參數(shù)來闡述復(fù)雜網(wǎng)絡(luò)的各種特性，下文將描述各參數(shù)。

1）平均路徑長度（Average path length）

將網(wǎng)絡(luò)內(nèi)的任意兩節(jié)點[i]與[j]的間距[lij]定義為假定兩節(jié)點分別為起點與終點，中間過程最小的連邊量。將網(wǎng)絡(luò)直徑定義成網(wǎng)絡(luò)內(nèi)部任何兩節(jié)點之間的最大值。則：

[D=maxi，jlij] （1-1）

平均路徑長度定義[L]為網(wǎng)絡(luò)中所有節(jié)點對之間距離的平均值，用公式表示為：

2）簇系數(shù)（Clustering efficient）

網(wǎng)絡(luò)中存在一節(jié)點[i]，它和另外的節(jié)點通過[ki]條邊連到一起，這i[ki]個節(jié)點稱為節(jié)點[i]的鄰居節(jié)點，最多會有[KiKi-12]條邊。[i]的簇系數(shù)用[ki]個鄰居節(jié)點中含有的邊數(shù)[2Ni]比上最大邊數(shù)[KiKi-12]的數(shù)值來計算，用[Ci]來表示。公式為：

[Ci=2NiKiKi-1i] （1-3）

3）度分布（Degree distribution）

若將節(jié)點[i]的度[ki]定義成和它連接的另外節(jié)點的個數(shù)，就可用[i]的鄰居數(shù)來稱呼它。一般每個節(jié)點會有單獨的度，網(wǎng)絡(luò)平均度就是全部節(jié)點度的均值，用[k]表示。公式為：

[K=1Ni=1NKi] （1-4）

通?？梢杂枚确植己瘮?shù)[Pk]來顯示節(jié)點的分布狀態(tài)。[Pk]含義為選擇任何的一個節(jié)點，它的度正好是[k]的概率。則：

[Pk=1Ni=1Nδk-ki] （1-5）

2復(fù)雜網(wǎng)絡(luò)模型

1）規(guī)則網(wǎng)絡(luò)（Regular network）

圖3顯示了普遍的網(wǎng)絡(luò)模型，分別是全局耦合、最近鄰耦合及星型模型。

上圖（a）顯示的全局模型中存在[N]個節(jié)點，邊數(shù)為[NN-12]條邊，它的[L=1]（最?。?，[C=1]（最大）。

2） ER隨機網(wǎng)絡(luò)（random network）

20世紀(jì)50年代匈牙利的兩位科學(xué)家設(shè)計出了此模型，如圖4所示：

（a）[p=0]時，存在10個孤立節(jié)點；（b）～（c）[p=0.1，0.15]時，得到的隨機效果圖

3）小世界網(wǎng)絡(luò)（small-world network）

1998年美國的Watts等人提出了一個小世界模型，它的特點是聚類參數(shù)大、路徑長度短，功能是使完全規(guī)則的網(wǎng)絡(luò)向完全隨機的形式轉(zhuǎn)變，通常稱作WS模型。如圖5所示：

4） NW小世界模型

因為網(wǎng)絡(luò)的連通性或許會被WS模型的隨機重連過程損壞，所以想要防止孤立子網(wǎng)產(chǎn)生，在1999年美國的Newman等人設(shè)計了一個新的小世界模型，它將隨機重連用隨機加邊代替，通常稱作NW模型。如圖6所示：

5）無標(biāo)度網(wǎng)絡(luò)（scale-free network）

1999年Albert等人設(shè)計了一種無標(biāo)度模型，來解釋此類網(wǎng)絡(luò)的冪律特性，通常被稱作BA模型，如圖7所示。

3 網(wǎng)絡(luò)模型比較

下面比較WS小世界網(wǎng)絡(luò)模型、BA無標(biāo)度網(wǎng)絡(luò)模型與真實網(wǎng)絡(luò)的主要性質(zhì)的異同。根據(jù)表1.5所示，現(xiàn)實網(wǎng)絡(luò)三大特性中的兩點能被BA與WS模型捕捉到。研究人員為了使現(xiàn)實網(wǎng)絡(luò)的全部特性都能被顯示，又設(shè)計了很多模型，然而BA與WS模型的結(jié)構(gòu)簡單，規(guī)則明確，且對復(fù)雜網(wǎng)絡(luò)的基本特性準(zhǔn)確把握，所以現(xiàn)階段應(yīng)用頻率最高的還是BA與WS模型。

[模型＼&節(jié)點度分布＼&平均路徑長度＼&聚類系數(shù)＼&真實網(wǎng)絡(luò)＼&冪率分布＼&?。?amp;大＼&小世界網(wǎng)絡(luò)＼&泊松分布＼&小＼&大＼&無標(biāo)度網(wǎng)絡(luò)＼&冪率分布＼&?。?amp;大＼&]

4 結(jié)束語

復(fù)雜網(wǎng)絡(luò)搜索過程的復(fù)雜性給搜索過程建模工作帶來一定程度的難度，在了解基本概念與復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的特性的基礎(chǔ)上，主要目的就是為了更好地描述復(fù)雜網(wǎng)絡(luò)動力學(xué)行為相關(guān)的問題（比如：網(wǎng)絡(luò)搜索、滲流、傳播、相變等）的在個體層和群體層之間的復(fù)雜性。本首先綜述了復(fù)雜網(wǎng)絡(luò)基本概念與復(fù)雜網(wǎng)絡(luò)模型，同時對復(fù)雜網(wǎng)絡(luò)模型進行比較。

參考文獻：

[1] 汪小帆， 李翔， 陳關(guān)榮. 復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M]. 北京： 清華大學(xué)出版社， 2006.

[2] 劉興堂， 劉力， 宋坤. 復(fù)雜系統(tǒng)建模與仿真的幾點重要思考[J]. 系統(tǒng)仿真學(xué)報， 2007， 19（13）.