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

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

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

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

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

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

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

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

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

9、一個(gè)數(shù)ifr<=punconect=find(matrix(i,:)=0);%取出鄰接矩陣中的非0元素位置M=length(unconect);%求出非0元素個(gè)數(shù)r1=ceil(M*rand(1);%正向取整matrix(i,unconect(r1)=1;matrix(unconect(r1),i)=1;%連接這一對(duì)點(diǎn)%matrix(i,j)=0;matrix(j,i)=0;%加上這個(gè)是SW小世界網(wǎng)絡(luò)endendend%逆時(shí)針的邊重新連接，從節(jié)點(diǎn)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%逆時(shí)針的邊重新連接，節(jié)點(diǎn)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é)點(diǎn)形成的環(huán)end%存儲(chǔ)鄰接矩陣%savedatamatrix;toc%計(jì)算程序耗時(shí)end上述程序建立了一個(gè)NW小世界網(wǎng)絡(luò)，求出了其鄰接矩陣，用tu_plot()函數(shù)畫出鄰接矩陣的圖，就得出了該小世界網(wǎng)絡(luò)的圖形。functiontu_plot(rel,control)%由鄰接矩陣畫連接圖，輸入為鄰接矩陣rel,必須為方陣；%control為控制量，0表示畫出的圖為無(wú)向圖，1表示有向圖。默認(rèn)值為0r_size=size(rel);%a=size(x；返回的是一

12、個(gè)行向量，該行向量第一個(gè)元素是%乂的行數(shù)，第2個(gè)元素是x的列數(shù)ifnargin<2%nargin是用來(lái)判斷輸入變量個(gè)數(shù)的函數(shù)control=0;%俞入變量小于2,即只有一個(gè)，就默認(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;%點(diǎn)的半徑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);%畫點(diǎn)endfori=1:le

14、nforj=1:lenifrel(i,j)link_plot(point(i,:),point(j,:),r,control);%連接有關(guān)系的點(diǎn)endendendset(gca,'XLim',-rho-r,rho+r,'YLim',-rho-r,rho+r);axisofffunctionlink_plot(point1,point2,r,control)%連接兩點(diǎn)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