小世界網(wǎng)絡(luò)簡介及及MATLAB建模

1、小世界網(wǎng)絡(luò)MATLAB建模1 .簡介小世界網(wǎng)絡(luò)存在于數(shù)學(xué)、物理學(xué)和社會學(xué)中，是一種數(shù)學(xué)圖的模型。在這種圖中大部份的結(jié)點不與彼此鄰接，但大部份結(jié)點可以通過任一其它節(jié)點經(jīng)少數(shù)幾步就可以產(chǎn)生聯(lián)系。若將一個小世界網(wǎng)絡(luò)中的點代表一個人，而聯(lián)機(jī)代表人與人之間是相互認(rèn)識的，則這小世界網(wǎng)絡(luò)可以反映陌生人通過彼此共同認(rèn)識的人而起來產(chǎn)生聯(lián)系關(guān)系的小世界現(xiàn)象。在日常生活中，有時你會發(fā)現(xiàn)，某些你覺得與你隔得很“遙遠(yuǎn)”的人，其實與你“很近”。小世界網(wǎng)絡(luò)就是對這種現(xiàn)象的數(shù)學(xué)描述。用數(shù)學(xué)中圖論的語言來說，小世界網(wǎng)絡(luò)就是一個由大量頂點構(gòu)成的圖，其中任意兩點之間的平均路徑長度比頂點數(shù)量小得多。除了社會人際網(wǎng)絡(luò)以外，小世界網(wǎng)絡(luò)的

2、例子在生物學(xué)、物理學(xué)、計算機(jī)科學(xué)等領(lǐng)域也有出現(xiàn)。許多經(jīng)驗中的圖可以用小世界網(wǎng)絡(luò)來作為模型。因特網(wǎng)、公路交通網(wǎng)、神經(jīng)網(wǎng)絡(luò)都呈現(xiàn)小世界網(wǎng)絡(luò)的特征。小世界網(wǎng)絡(luò)最早是由鄧肯瓦茨(DuncanWatts)和斯蒂文斯特羅加茨(StevenStrogatz)在1998年引進(jìn)的，將高聚合系數(shù)和低平均路徑長度作為特征，提出了一種新的網(wǎng)絡(luò)模型，一般就稱作瓦茨-斯特羅加茨模型(WS模型)，這也是最典型的小世界網(wǎng)絡(luò)的模型。由于WS小世界模型構(gòu)造算法中的隨機(jī)化過程有可能破壞網(wǎng)絡(luò)的連通性，紐曼(Newman)和瓦茨(Watts)提出了NW小世界網(wǎng)絡(luò)模型，該模型是通過用“隨機(jī)化加邊”模式來取代WS小世界網(wǎng)絡(luò)模型構(gòu)造中的“隨

3、機(jī)化重連”。在考慮網(wǎng)絡(luò)特征的時候，使用兩個特征來衡量網(wǎng)絡(luò)：特征路徑長度和聚合系數(shù)。特征路徑長度(characteristicpathlength)：在網(wǎng)絡(luò)中，任選兩個節(jié)點，連同這兩個節(jié)點的最少邊數(shù)，定義為這兩個節(jié)點的路徑長度，網(wǎng)絡(luò)中所有節(jié)點對的路徑長度的平均值，定義為網(wǎng)絡(luò)的特征路徑長度。這是網(wǎng)絡(luò)的全局特征。聚合系數(shù)(clusteringcoefficient):假設(shè)某個節(jié)點有k個邊，則這k條邊連接的節(jié)點之間最多可能存在的邊的個數(shù)為k(k-1)/2,用實際存在的邊數(shù)除以最多可能存在的邊數(shù)得到的分?jǐn)?shù)值，定義為這個節(jié)點的聚合系數(shù)。所有節(jié)點的聚合系數(shù)的均值定義為網(wǎng)絡(luò)的聚合系數(shù)。聚合系數(shù)是網(wǎng)絡(luò)的局部特征

4、，反映了相鄰兩個人之間朋友圈子的重合度，即該節(jié)點的朋友之間也是朋友的程度。我們可以發(fā)現(xiàn)規(guī)則網(wǎng)絡(luò)具有很高的聚合系數(shù)，大世界(largeworld,意思是特征路徑長度很大)，其特征路徑長度隨著n(網(wǎng)絡(luò)中節(jié)點的數(shù)量)線性增長，而隨機(jī)網(wǎng)絡(luò)聚合系數(shù)很小，小世界(smallworld,意思是特征路徑長度小)，其特征路徑長度隨著10g(n)增長中說明，在從規(guī)則網(wǎng)絡(luò)向隨機(jī)網(wǎng)絡(luò)轉(zhuǎn)換的過程中，實際上特征路徑長度和聚合系數(shù)都會下降，到變成隨機(jī)網(wǎng)絡(luò)的時候，減少到最少。但這并不是說大的聚合系數(shù)一定伴隨著大的路徑長度，而小的路徑長度伴隨著小的聚合系數(shù)，小世界網(wǎng)絡(luò)就具有大的聚合系數(shù)，而特征路徑長度很小。試驗表明，少量的sh

5、ortcut的建立能夠迅速減少特征路徑長度，而聚合系數(shù)變化卻不大，因為某一個shortcut的建立，不僅影響到所連接的節(jié)點的特征路徑長度，而且影響到他們鄰居的路徑長度，而對整個網(wǎng)絡(luò)的聚合系數(shù)影響不大。這樣，少量的shortcut的建立就能使整個網(wǎng)絡(luò)不知不覺地變成小世界網(wǎng)絡(luò)。實際的社會、生態(tài)、等網(wǎng)絡(luò)都是小世界網(wǎng)絡(luò)，在這樣的系統(tǒng)里，信息傳遞速度快，并且少量改變幾個連接，就可以劇烈地改變網(wǎng)絡(luò)的性能，如對已存在的網(wǎng)絡(luò)進(jìn)行調(diào)整，如蜂窩電話網(wǎng)，改動很少幾條線路，就可以顯著提高性能。2 .小世界網(wǎng)絡(luò)構(gòu)成原則WS小世界網(wǎng)絡(luò)的構(gòu)成原則為：從一個環(huán)斗的規(guī)則網(wǎng)絡(luò)開始，網(wǎng)絡(luò)含有N個結(jié)點，每個結(jié)點向與它最近鄰的K個結(jié)點

6、連出K條邊，并滿足N>>K>>In(N)>>1。隨后進(jìn)行隨機(jī)化重連，以概率p隨機(jī)地重新連接網(wǎng)絡(luò)中的每個邊，即將邊的一個端點保持不變，而另一個端點取為網(wǎng)絡(luò)中隨機(jī)選擇的一個節(jié)點。其中規(guī)定，任意兩個不同的節(jié)點之間至多只能有一條邊，并且每一個節(jié)點都不能有邊與自身相連。這樣就會產(chǎn)生pNK/2條長程的邊把一個結(jié)點和遠(yuǎn)處的結(jié)點聯(lián)系起來。改變p值可以實現(xiàn)從規(guī)則網(wǎng)絡(luò)(p=0)向隨機(jī)網(wǎng)絡(luò)(p=1)轉(zhuǎn)變。NW小世界網(wǎng)絡(luò)的構(gòu)成原則為：從一個環(huán)狀的規(guī)則網(wǎng)絡(luò)開始，網(wǎng)絡(luò)含有N個結(jié)點，每個結(jié)點向與它最近鄰的K個結(jié)點連出K條邊，并滿足N>>K>>In(N)>&g

7、t;1o隨后進(jìn)行隨機(jī)化加邊，以概率p在隨機(jī)選取的一對節(jié)點之間加上一條邊。其中，任意兩個不同的節(jié)點之間至多只能有一條邊，并且每一個節(jié)點都不能有邊與自身相連。改變p值可以實現(xiàn)從最近鄰耦合網(wǎng)絡(luò)(p=0)向全局耦合網(wǎng)絡(luò)(p=1)轉(zhuǎn)變。在p足夠小和N足夠大時，NW小世界模型本質(zhì)上等同于WS小世界模型。3 .MATLAB建模建立一個初始節(jié)點數(shù)為20的NW網(wǎng)絡(luò)。MATLAB程序如下：functionmatrix=SW()%By201121250314ticN=20;m=4;%初始化網(wǎng)絡(luò)數(shù)據(jù)p=0.1;%以概率p=0.1在隨機(jī)選取的一對結(jié)點之間加上一條邊matrix=sparse(口，口,20,20,0);%

8、創(chuàng)建一個20*20的全0稀疏矩陣%建立初始的環(huán)狀的規(guī)則網(wǎng)絡(luò)%結(jié)點網(wǎng)絡(luò)有N個節(jié)點%每個結(jié)點向與它最近鄰的m個結(jié)點連出邊%求出鄰接矩陣fori=m+1:N-mforj=i-m:i+mmatrix(i,j)=1;endendfori=1:mforj=1:i+mmatrix(i,j)=1;endendfori=N-m+1:Nforj=i-m:Nmatrix(i,j)=1;endendfori=1:mforj=N-m+i:Nmatrix(i,j)=1;matrix(j,i)=1;endend%逆時針的邊重連，從節(jié)點到N-m-1fori=1:N-m-1forj=i+1:i+mr=rand(1);%隨機(jī)選取

9、一個數(shù)ifr<=punconect=find(matrix(i,:)=0);%取出鄰接矩陣中的非0元素位置M=length(unconect);%求出非0元素個數(shù)r1=ceil(M*rand(1);%正向取整matrix(i,unconect(r1)=1;matrix(unconect(r1),i)=1;%連接這一對點%matrix(i,j)=0;matrix(j,i)=0;%加上這個是SW小世界網(wǎng)絡(luò)endendend%逆時針的邊重新連接，從節(jié)點N-m到N-1fori=N-m+1:N-1forj=i+1:N1:i-N+mr=rand(1);ifr<=punconect=find(m

10、atrix(i,:)=0);r1=ceil(length(unconect)*rand(1);matrix(i,unconect(r1)=1;matrix(unconect(r1),i)=1;%matrix(i,j)=0;matrix(j,i)=0;endendend%逆時針的邊重新連接，節(jié)點Nfori=Nforj=1:mr=rand(1);ifr<=punconect=find(matrix(i,:)=0);r1=ceil(length(unconect)*rand(1);matrix(i,unconect(r1)=1;matrix(unconect(r1),i)=1;matrix(i

11、,j)=0;matrix(j,i)=0;endendend%恢復(fù)小世界網(wǎng)絡(luò)的鄰接矩陣form=1:Nmatrix(m,m)=0;%去掉自身節(jié)點形成的環(huán)end%存儲鄰接矩陣%savedatamatrix;toc%計算程序耗時end上述程序建立了一個NW小世界網(wǎng)絡(luò)，求出了其鄰接矩陣，用tu_plot()函數(shù)畫出鄰接矩陣的圖，就得出了該小世界網(wǎng)絡(luò)的圖形。functiontu_plot(rel,control)%由鄰接矩陣畫連接圖，輸入為鄰接矩陣rel,必須為方陣；%control為控制量，0表示畫出的圖為無向圖，1表示有向圖。默認(rèn)值為0r_size=size(rel);%a=size(x；返回的是一

12、個行向量，該行向量第一個元素是%乂的行數(shù)，第2個元素是x的列數(shù)ifnargin<2%nargin是用來判斷輸入變量個數(shù)的函數(shù)control=0;%俞入變量小于2,即只有一個，就默認(rèn)control為0endifr_size(1)=r_size(2)%亍數(shù)和歹U數(shù)不相等，不是方陣，不予處理disp('WrongInput!Theinputmustbeasquarematrix!');return;endlen=r_size(1);rho=10;%限制圖尺寸的大小r=2/1.05Nen;%點的半徑theta=0:(2*pi/len):2*pi*(1-1/len);pointx,

13、pointy=pol2cart(theta',rho);theta=0:pi/36:2*pi;tempx,tempy=pol2cart(theta',r);point=pointx,pointy;holdonfori=1:lentemp=tempx,tempy+point(i,1)*ones(length(tempx),1),point(i,2)*ones(length(tempx),1);plot(temp(:,1),temp(:,2),'r');text(point(i,1)-0.3,point(i,2),num2str(i);%畫點endfori=1:le

14、nforj=1:lenifrel(i,j)link_plot(point(i,:),point(j,:),r,control);%連接有關(guān)系的點endendendset(gca,'XLim',-rho-r,rho+r,'YLim',-rho-r,rho+r);axisofffunctionlink_plot(point1,point2,r,control)%連接兩點temp=point2-point1;if(temp(1)&&(temp(2)return;%不畫子回路endtheta=cart2pol(temp(1),temp(2);point1_x,point1_y=pol2cart(theta,r);point_1=point1_x,point1_y+point1;point2_x,point2_y=pol2cart(theta+(2*(theta