復(fù)雜網(wǎng)絡(luò)的度分布及其算法

王桂山 任學(xué)藻 西南科技大學(xué) 許凡 河南理工大學(xué)

自然界中存在的大量復(fù)雜系統(tǒng)都可以通過(guò)形形色色的網(wǎng)絡(luò)加以描述一個(gè)典型的網(wǎng)絡(luò)是由許多節(jié)點(diǎn)與連接兩個(gè)節(jié)點(diǎn)之間的一些邊組成的，其中節(jié)點(diǎn)用來(lái)代表真實(shí)系統(tǒng)中不同的個(gè)體，而邊則用來(lái)表示個(gè)體之間的關(guān)系，通常是當(dāng)兩個(gè)節(jié)點(diǎn)之間具有某種特定的關(guān)系時(shí)連一條邊，反之則不連邊有邊相連的兩個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中被看作是相鄰的。

一網(wǎng)絡(luò)的發(fā)展大致經(jīng)歷了規(guī)則網(wǎng)絡(luò)、隨機(jī)網(wǎng)絡(luò)和復(fù)雜網(wǎng)絡(luò)三個(gè)階段。

第一階段規(guī)則網(wǎng)絡(luò)的理論：圖論的發(fā)展始于18世紀(jì)偉大的數(shù)學(xué)家Euler對(duì)著名的柯尼斯堡（konigsberg）七橋問(wèn)題的研究。開創(chuàng)了數(shù)學(xué)分支圖論的研究，研究表明規(guī)則網(wǎng)絡(luò)具有較大的聚類系數(shù)和較大的平均最短路徑長(zhǎng)度，其所有的節(jié)點(diǎn)都有相同的度，節(jié)點(diǎn)度分布為

第二階段隨機(jī)網(wǎng)絡(luò)階段理論：如果節(jié)點(diǎn)之間不按確定的規(guī)則連接，而是以一定的概率隨機(jī)連接，所得到的網(wǎng)絡(luò)就是隨機(jī)網(wǎng)絡(luò)。20世紀(jì)60年代，兩個(gè)著名的匈牙利數(shù)學(xué)家Erdo和Renyi提出的ER隨機(jī)網(wǎng)絡(luò)模型，開創(chuàng)了隨機(jī)網(wǎng)絡(luò)的研究的新局面。隨機(jī)網(wǎng)絡(luò)具有較小的聚類系數(shù)和較小的平均最短路徑長(zhǎng)度，節(jié)點(diǎn)度分布為泊松分布。

第三階段復(fù)雜網(wǎng)絡(luò)理論：在世紀(jì)之交，隨著計(jì)算機(jī)技術(shù)的高度發(fā)展、計(jì)算機(jī)運(yùn)算能力的不斷提高，人們擁有了各種的數(shù)據(jù)庫(kù)，因此對(duì)大規(guī)模的網(wǎng)絡(luò)進(jìn)行實(shí)證研究有了可能，復(fù)雜網(wǎng)絡(luò)科學(xué)取得了突破性的進(jìn)展。問(wèn)題的起因可追溯到20世紀(jì)60年代，美國(guó)心理學(xué)家曾做過(guò)一個(gè)所謂‘六度分割’（six degree of separation）實(shí)驗(yàn)。已有的規(guī)則網(wǎng)絡(luò)和ER隨機(jī)網(wǎng)絡(luò)都無(wú)法解釋這種“小世界現(xiàn)象”。

1998年Watts和Strogata提出了小世界網(wǎng)絡(luò)模型，說(shuō)明了少量的隨機(jī)捷徑（Random shortcuts）會(huì)改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，從而涌現(xiàn)出“小世界效應(yīng)”，小世界網(wǎng)絡(luò)模型介于規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)之間，具有較大的聚類系數(shù)和短平均路徑長(zhǎng)度，節(jié)點(diǎn)度分布為泊松分布，比規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)更能模擬真實(shí)網(wǎng)絡(luò)的特性。

1999年的Barabasi和Albert在研究萬(wàn)維網(wǎng)時(shí)發(fā)現(xiàn)，萬(wàn)維網(wǎng)的度分布不像隨機(jī)網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)那種具有對(duì)稱的泊松分布，而是偏倚的冪律分布，在該網(wǎng)絡(luò)中，大多數(shù)節(jié)點(diǎn)僅有少量的連線，而少數(shù)節(jié)點(diǎn)擁有大量的連線。為此提出了無(wú)標(biāo)度（Scale-free）網(wǎng)絡(luò)模型，揭示了增長(zhǎng)和擇優(yōu)機(jī)制在復(fù)雜網(wǎng)絡(luò)自組織演化過(guò)程中的普遍性和冪律的重要性。無(wú)標(biāo)度網(wǎng)絡(luò)中的節(jié)點(diǎn)具有很強(qiáng)的異質(zhì)性，不同度的節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性不同。例如：在城市交通網(wǎng)絡(luò)中，度分布表示城市之間的航線的多少和重要程度，度越大的城市，其重要性也越大；在社會(huì)網(wǎng)絡(luò)中，度可以表示個(gè)體的作用力和影響度，一個(gè)節(jié)點(diǎn)的度越大，一般表示在整個(gè)網(wǎng)絡(luò)中的作用和影響越大，反之亦然。

復(fù)雜網(wǎng)絡(luò)可以描述自然界和人類社會(huì)中大量的復(fù)雜系統(tǒng)，一個(gè)典型的網(wǎng)絡(luò)是有許多節(jié)點(diǎn)和一些連接節(jié)點(diǎn)間的邊組成，其中節(jié)點(diǎn)代表真實(shí)系統(tǒng)中不同的個(gè)體，二邊則表示個(gè)體之間的關(guān)系。例如上面提到的交通網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)代表一個(gè)城市，每條邊表示兩個(gè)城市間有一條航線。目前復(fù)雜網(wǎng)絡(luò)的研究主要為：社會(huì)網(wǎng)絡(luò)、信息網(wǎng)絡(luò)、技術(shù)網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等。

復(fù)雜網(wǎng)絡(luò)在社會(huì)網(wǎng)絡(luò)中的應(yīng)用十分廣泛，社會(huì)網(wǎng)絡(luò)是指社會(huì)個(gè)體成員之間因?yàn)榛?dòng)而形成的相對(duì)穩(wěn)定的關(guān)系體系，社會(huì)網(wǎng)絡(luò)關(guān)注的是人們之間的互動(dòng)和聯(lián)系，社會(huì)互動(dòng)影響到人們的社會(huì)行為。社會(huì)網(wǎng)絡(luò)研究如個(gè)人間的朋友關(guān)系，公司商業(yè)伙伴關(guān)系，電影演員合作網(wǎng)絡(luò)，性接觸網(wǎng)絡(luò)，科學(xué)家合作網(wǎng)絡(luò)等。目前，復(fù)雜網(wǎng)絡(luò)研究主題主要包括：復(fù)雜網(wǎng)絡(luò)的拓?fù)湫再|(zhì)，復(fù)雜網(wǎng)絡(luò)的生成機(jī)制，復(fù)雜網(wǎng)絡(luò)的演化的統(tǒng)計(jì)規(guī)律，復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)穩(wěn)定性，復(fù)雜網(wǎng)絡(luò)上的傳播機(jī)理與動(dòng)力學(xué)特性，復(fù)雜網(wǎng)絡(luò)中的搜索，復(fù)雜網(wǎng)絡(luò)中的同步與控制以及把網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與具體系統(tǒng)結(jié)合起來(lái)。

分析復(fù)雜網(wǎng)路在隨機(jī)和惡意攻擊下的魯棒性。對(duì)于隨機(jī)網(wǎng)絡(luò)而言網(wǎng)絡(luò)中的節(jié)點(diǎn)是同質(zhì)的，即網(wǎng)絡(luò)中所有的節(jié)點(diǎn)幾乎具有相同的度數(shù)。而無(wú)標(biāo)度網(wǎng)絡(luò)具有很強(qiáng)的異質(zhì)性，網(wǎng)絡(luò)中大部分節(jié)點(diǎn)具有較小的度只有少量的節(jié)點(diǎn)具有較大的度，當(dāng)隨機(jī)刪除一小部分節(jié)點(diǎn)時(shí)，隨機(jī)網(wǎng)絡(luò)的直徑隨著刪除節(jié)點(diǎn)的多少單調(diào)增加，而無(wú)標(biāo)度網(wǎng)絡(luò)的直徑幾乎不變。

度分布是復(fù)雜網(wǎng)絡(luò)研究的一個(gè)重要的統(tǒng)計(jì)量，節(jié)點(diǎn)度數(shù)反映了節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性，度數(shù)越大的節(jié)點(diǎn)在網(wǎng)絡(luò)中有越多的鄰居節(jié)點(diǎn)，它的變化對(duì)網(wǎng)絡(luò)的影響越大，反之亦然。網(wǎng)絡(luò)度分布描述了網(wǎng)絡(luò)中節(jié)點(diǎn)度的分布情況，具有指數(shù)型度分布的網(wǎng)絡(luò)中節(jié)點(diǎn)是同質(zhì)的，這樣的網(wǎng)絡(luò)對(duì)惡意攻擊具有很強(qiáng)的魯棒性；具有冪律度分布的網(wǎng)路中節(jié)點(diǎn)是異質(zhì)的，網(wǎng)絡(luò)中大部分節(jié)點(diǎn)具有很小的度數(shù)，但也存在極少數(shù)量的節(jié)點(diǎn)度很大，這樣的網(wǎng)絡(luò)對(duì)于隨機(jī)攻擊具有強(qiáng)的韌魯棒性，但對(duì)于惡意攻擊卻很脆弱，下面系統(tǒng)分析網(wǎng)絡(luò)度分布的方法：

平均場(chǎng)方法：Barabasi等人分析BA模型的度分布提出了平均場(chǎng)方法（mean-fild approach）。具體計(jì)算步驟如下：令表示節(jié)點(diǎn)i(在第i時(shí)刻加入到網(wǎng)絡(luò)的節(jié)點(diǎn))在時(shí)刻 時(shí)的度數(shù)，對(duì)于BA模型，在t時(shí)刻網(wǎng)絡(luò)共增加了m條連線，每條連線連接網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)，此時(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)的度數(shù)之和.根據(jù)連續(xù)性理論，把看做連續(xù)動(dòng)力學(xué)函數(shù)，則滿足如下的動(dòng)力學(xué)方程

上述方程有如下的解：由于計(jì)算網(wǎng)絡(luò)的度分布需要隨機(jī)選擇一個(gè)節(jié)點(diǎn)，所以中的i必須看成隨機(jī)變量，由于節(jié)點(diǎn)是隨機(jī)選擇的，因此i在所有節(jié)點(diǎn)中服從均勻分布，又初始網(wǎng)絡(luò)中含有個(gè)節(jié)點(diǎn)，從而通過(guò)

可得：對(duì)k求導(dǎo)即可得到表示在時(shí)刻t度數(shù)為k的節(jié)點(diǎn)所占的比例：

當(dāng)時(shí)，網(wǎng)絡(luò)的穩(wěn)態(tài)度分布為：其中，為標(biāo)度指數(shù)。

率方程方法：

Krapivsky等人在分析網(wǎng)絡(luò)度分布的時(shí)候提出了率方程方法（rate-equation approach），求解過(guò)程：令表示在t時(shí)刻網(wǎng)絡(luò)中度數(shù)為k的節(jié)點(diǎn)總數(shù)，對(duì)于BA模型根據(jù)連續(xù)性理論，現(xiàn)在考慮節(jié)點(diǎn)數(shù)的變化率，對(duì)于原來(lái)度數(shù)為的節(jié)點(diǎn)由于與新節(jié)點(diǎn)相連度數(shù)變?yōu)閗，需要算入；對(duì)于原來(lái)度數(shù)為k的節(jié)點(diǎn)，由于增加了連線度數(shù)變?yōu)?，需要排除；?duì)于新節(jié)點(diǎn)，它的度數(shù)度數(shù)恰好為m，若k=m,則需要保留。節(jié)點(diǎn)i與新加入的節(jié)點(diǎn)相連的概率為可得到關(guān)于率方程由大數(shù)定律得結(jié)合上式可表示為：此方程式是一個(gè)關(guān)于一階差分方程，解此方程可以得到:通過(guò)率方程方法得到BA模型的度分布服從指數(shù)為3的冪律分布，這個(gè)結(jié)果和平均場(chǎng)方法所得結(jié)果一致。

主方程方法：

Dorogovtsev等人提出了主方程方法（master-equation approach）.主方程方法求解度分布的步驟如下：對(duì)于固定的t,第i時(shí)刻加入到網(wǎng)絡(luò)中的節(jié)點(diǎn)i的度數(shù)是一個(gè)隨機(jī)變量，現(xiàn)在令對(duì)于BA模型，新節(jié)點(diǎn)加入到網(wǎng)絡(luò)時(shí)選擇舊節(jié)點(diǎn)i并與之相連的概率時(shí)得到下面的主方程：

這個(gè)方程的邊界條件:對(duì)于BA模型，結(jié)合上式可以化簡(jiǎn)為：這是一個(gè)一階差分方程，解此差分方程：

通過(guò)主方程方法可得BA模型是度分布服從指數(shù)為3的冪律分布的無(wú)標(biāo)度網(wǎng)絡(luò)。

鞅方法：

Bollobas等人用鞅方法嚴(yán)格證明了LCD模型度分布的存在性并求出了度分布的表達(dá)式，對(duì)于LCD模型，首先證明了當(dāng)然后定義一個(gè)鞅

根據(jù)Azuma-Hoeffding不等式，對(duì)于每個(gè)d有:

當(dāng)時(shí),有

BA模型的度分布另外一個(gè)求解方法，具體思路如下：首先令然后證明定義得

在BA模型中，對(duì)于每一個(gè)固定的t為一個(gè)隨機(jī)變量，對(duì)于變動(dòng)的t為一非齊次馬氏鏈，馬氏鏈的狀態(tài)轉(zhuǎn)移概率為

應(yīng)用馬氏鏈理論的首達(dá)概率及其方法和技巧，對(duì)節(jié)點(diǎn)度分布得出如下

最后給出網(wǎng)絡(luò)度分布的精確、解析表達(dá)式如下：

本文章馬氏鏈方法在求解復(fù)雜網(wǎng)絡(luò)度分布中，具有很好的普適性，對(duì)增長(zhǎng)網(wǎng)絡(luò)和演化網(wǎng)絡(luò)的度分布進(jìn)行了系統(tǒng)的分析，在對(duì)增長(zhǎng)網(wǎng)絡(luò)和演化網(wǎng)絡(luò)的度分布問(wèn)題給出了較為統(tǒng)一的答案。

[1]李彥.復(fù)雜網(wǎng)絡(luò)研究概述[J].科學(xué)與財(cái)富,2012(10):35-35.

[2]葉笛.基于復(fù)雜網(wǎng)絡(luò)視角的供應(yīng)鏈網(wǎng)絡(luò)研究[J].現(xiàn)代管理科學(xué),2011(8):111-113.

[3]趙京勝,孫宇航.基于復(fù)雜網(wǎng)絡(luò)理論的校友網(wǎng)絡(luò)研究[J].信息技術(shù)與信息化,2014(2):121-126.

[4]莊天舒.基于復(fù)雜網(wǎng)絡(luò)理論的Internet拓?fù)涔?jié)點(diǎn)特征分析[J].長(zhǎng)春大學(xué)學(xué)報(bào),2010, 20(10):30-32.

[5]趙山春.基于復(fù)雜網(wǎng)絡(luò)理論的城市公交網(wǎng)絡(luò)可靠性研究[J].中國(guó)安全科學(xué)學(xué)報(bào),2013, 23(4):108-112.

[6]胡海波.復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究[D]. 西安理工大學(xué), 2006.

[7]姚紅光,朱麗萍.基于仿真分析的中國(guó)航空網(wǎng)絡(luò)魯棒性研究[J]. 武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版), 2012, 36(1):42-46.

[8]蔣國(guó)平,宋玉蓉,鞏永旺.基于復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特征的病毒傳播研究綜述[J]. 南京郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012, 32(5):1-6.

[9]黃瑋強(qiáng),姚爽, 莊新田.基于復(fù)雜社會(huì)網(wǎng)絡(luò)的創(chuàng)新擴(kuò)散多智能體仿真研究[J].科學(xué)學(xué)研究,2013, 31(2):310-320.

[10]王甲生,吳曉平,陳永強(qiáng)，加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)級(jí)聯(lián)抗毀性研究[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2013,10(2):13-19.