《小世界復(fù)雜網(wǎng)絡(luò)模型研究》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、小世界復(fù)雜網(wǎng)絡(luò)模型研究摘要：復(fù)雜網(wǎng)絡(luò)在工程技術(shù)、社會、政治、醫(yī)藥、經(jīng)濟(jì)、管理領(lǐng)域都有著潛在、廣泛的應(yīng)用。通過高級計(jì)算機(jī)網(wǎng)絡(luò)課程學(xué)習(xí)，本文介紹了復(fù)雜網(wǎng)絡(luò)研究歷史應(yīng)用，理論描述方法及闡述對幾種網(wǎng)絡(luò)模型的理解。1復(fù)雜網(wǎng)絡(luò)的發(fā)展及研究意義1.1復(fù)雜網(wǎng)絡(luò)的發(fā)展歷程現(xiàn)實(shí)世界中的許多系統(tǒng)都可以用復(fù)雜網(wǎng)絡(luò)來描述，如社會網(wǎng)絡(luò)中的科研合作網(wǎng)、信息網(wǎng)絡(luò)中的萬維網(wǎng)、電力網(wǎng)、航空網(wǎng)，生物網(wǎng)絡(luò)中的代謝網(wǎng)與蛋白質(zhì)網(wǎng)絡(luò)。由于現(xiàn)實(shí)世界網(wǎng)絡(luò)的規(guī)模大，節(jié)點(diǎn)間相互作用復(fù)雜，其拓?fù)浣Y(jié)構(gòu)基本上未知或未曾探索。兩百多年來，人們對描述真實(shí)系統(tǒng)拓?fù)浣Y(jié)構(gòu)的研究經(jīng)歷了三個(gè)階段。在最初的一百多年里，科學(xué)家們認(rèn)為

2、真實(shí)系統(tǒng)要素之間的關(guān)系可以用一些規(guī)則的結(jié)構(gòu)表示，例如二維平面上的歐幾里德格網(wǎng)；從20世紀(jì)50年代末到90年代末，無明確設(shè)計(jì)原則的大規(guī)模網(wǎng)絡(luò)主要用簡單而易于被多數(shù)人接受的隨機(jī)網(wǎng)絡(luò)來描述，隨機(jī)圖的思想主宰復(fù)雜網(wǎng)絡(luò)研究達(dá)四十年之久；直到最近幾年，科學(xué)家們發(fā)現(xiàn)大量的真實(shí)網(wǎng)絡(luò)既不是規(guī)則網(wǎng)絡(luò)，也不是隨機(jī)網(wǎng)絡(luò)，而是具有與前兩者皆不同的統(tǒng)計(jì)特性的網(wǎng)絡(luò)，其中最有影響的是小世界網(wǎng)絡(luò)和無尺度網(wǎng)絡(luò)。這兩種網(wǎng)絡(luò)的發(fā)現(xiàn)，掀起了復(fù)雜網(wǎng)絡(luò)的研究熱潮。2復(fù)雜網(wǎng)絡(luò)的基本概念2.1網(wǎng)絡(luò)的定義自隨機(jī)圖理論提出至今，在復(fù)雜網(wǎng)絡(luò)領(lǐng)域提出了許多概念和術(shù)語。網(wǎng)絡(luò)（Network）在數(shù)學(xué)上以圖（Graph

3、）來表示，圖的研究最早起源于18世紀(jì)瑞士著名數(shù)學(xué)家Euler的哥尼斯堡七橋問題。復(fù)雜網(wǎng)絡(luò)可以用圖論的語言和符號精確簡潔地加以描述。圖論不僅為數(shù)學(xué)家和物理學(xué)家提供了描述網(wǎng)絡(luò)的語言和研究的平臺，而且其結(jié)論和技巧已經(jīng)被廣泛地移植到復(fù)雜網(wǎng)絡(luò)的研究中。網(wǎng)絡(luò)的節(jié)點(diǎn)和邊組成的集合。節(jié)點(diǎn)為系統(tǒng)元素，邊為元素間的互相作用（關(guān)系）。若用圖的方式表示網(wǎng)絡(luò)，則可以將一個(gè)具體網(wǎng)絡(luò)可抽象為一個(gè)由點(diǎn)集V和邊集E組成的圖G=（V,E）。節(jié)點(diǎn)數(shù)記為N=

4、V

5、，邊數(shù)記為M=

6、E

7、.E中每條邊都有V中一對點(diǎn)與之相對應(yīng)。如果任意點(diǎn)對（i,j）與（j,i）對應(yīng)同一條邊，則該網(wǎng)絡(luò)成為無向網(wǎng)絡(luò)（und

8、irectednetwork），否則稱為無權(quán)網(wǎng)絡(luò)（unweightednetwork）。當(dāng)然，無權(quán)網(wǎng)絡(luò)也看作是每條邊的權(quán)值都為1的等權(quán)網(wǎng)絡(luò)。1.1復(fù)雜網(wǎng)絡(luò)的基本概念復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的有很多概念和方法，其中基本的概念是：平均路徑長度(averagepathlength)、集聚系數(shù)(clusteringcoefficient)和度分布(degreedistribution)。abdc圖1平均路徑長度：網(wǎng)絡(luò)中的任意兩點(diǎn)間有一條最短的路徑，它等于沿這條路徑從一點(diǎn)走到另一點(diǎn)所經(jīng)過的最少邊數(shù)，平均路徑長度表示網(wǎng)絡(luò)中所有的節(jié)點(diǎn)對之間的最短路徑的平均值。如圖1所示：?D(ab

9、)=1,D(ac)=1,D(ad)=2?D(bc)=1,D(bd)=2?D(cd)=1?L=(1+1+2+1+2+1)/6=8/6集聚系數(shù)：社會上形成了許多派系（Clique）或集團(tuán)，同一派系里的人兩兩相互認(rèn)識。為了描述網(wǎng)絡(luò)中與同一節(jié)點(diǎn)直接相連的節(jié)點(diǎn)之間的連接關(guān)系，人們引進(jìn)了集聚系數(shù)這一概念：假定某一節(jié)點(diǎn)i有Ki個(gè)最近鄰，那么在這些最近鄰的點(diǎn)之間最多可能存在Ki(Ki-1)/2條邊，用Ci表示這些可能存在的邊中實(shí)際上存在的百分比。對網(wǎng)絡(luò)中所的Ci取平均值，就得到集聚系數(shù)C，它描述了網(wǎng)絡(luò)中點(diǎn)與點(diǎn)集結(jié)成團(tuán)的趨勢。如圖1所示：?Ca=1(becausebandc

10、connected)?Cb=1(becauseaandbconnected)?Cc=1/3(a-b,notb-d,nota-d)?Cd=0?Averageclustering=(7/3)/4=7/12度分布：節(jié)點(diǎn)的度也稱為連通度，它指的是與該節(jié)點(diǎn)連接的邊數(shù)。度分布P(k)函數(shù)表示節(jié)點(diǎn)有k條邊連接（即有k個(gè)最近鄰居）的概率。如圖1所示：Ka=2,Kb=2,Kc=3,Kd=11.1復(fù)雜網(wǎng)絡(luò)的分類根據(jù)節(jié)點(diǎn)度的分布情況，可以將復(fù)雜網(wǎng)絡(luò)分為指數(shù)網(wǎng)絡(luò)和無尺度網(wǎng)絡(luò)兩大類。指數(shù)網(wǎng)絡(luò)中的節(jié)點(diǎn)是同質(zhì)的，它們的度大致相同，絕大部節(jié)點(diǎn)的度都位于網(wǎng)絡(luò)節(jié)點(diǎn)平均度附近，網(wǎng)絡(luò)節(jié)點(diǎn)度分布隨

11、度數(shù)的增加呈指數(shù)衰減，使得網(wǎng)絡(luò)中不存在度數(shù)特別大的節(jié)點(diǎn)，最經(jīng)典的兩種指數(shù)網(wǎng)絡(luò)是Erd?s與Rényi于1960年提出的Erd?s-Rényi（ER）隨機(jī)圖模型和Watt與Strogatz在1998年提出的Watt-Strogatz小世界網(wǎng)絡(luò)模型（WS模型）。隨機(jī)圖與小世界網(wǎng)絡(luò)的主要區(qū)別是：前者的簇系數(shù)小，而后者的簇系數(shù)大。目前，把具有較小平均路徑長度和較大簇系數(shù)的網(wǎng)絡(luò)統(tǒng)稱為小世界網(wǎng)絡(luò)，這一說法已得到學(xué)術(shù)界的公認(rèn)。無尺度網(wǎng)絡(luò)中的節(jié)點(diǎn)是異質(zhì)的，其節(jié)點(diǎn)度服從冪律分布。最著名的無尺度網(wǎng)絡(luò)模型是1999年Barabási和Albert建立的Barabási-Albe

12、rt無尺度網(wǎng)絡(luò)模型（BA模型或BA網(wǎng)絡(luò)）。在無尺度網(wǎng)絡(luò)中，大部分節(jié)