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

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

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

3、取代WS小世界網(wǎng)絡模型構造中的“隨機化重連”。 在考慮網(wǎng)絡特征的時候，使用兩個特征來衡量網(wǎng)絡： 特征路徑長度和聚合系數(shù)。 特征路徑長度（characteristic path length）：在網(wǎng)絡中，任選兩個節(jié)點，連同這兩個節(jié)點的最少邊數(shù)，定義為這兩個節(jié)點的路徑長度，網(wǎng)絡中所有節(jié)點對的路徑長度的平均值，定義為網(wǎng)絡的特征路徑長度。這是網(wǎng)絡的全局特征。 聚合系數(shù)(clustering coefficient)：假設某個節(jié)點有k個邊，則這k條邊連接的節(jié)點之間最多可能存在的邊的個數(shù)為k(k-1)/2，用實際存在的邊數(shù)除以最多可能存在的邊數(shù)得到的分數(shù)值，定義為這個節(jié)點的聚合系數(shù)。所有節(jié)點的聚合系數(shù)的均

4、值定義為網(wǎng)絡的聚合系數(shù)。聚合系數(shù)是網(wǎng)絡的局部特征，反映了相鄰兩個人之間朋友圈子的重合度，即該節(jié)點的朋友之間也是朋友的程度。 我們可以發(fā)現(xiàn)規(guī)則網(wǎng)絡具有很高的聚合系數(shù)，大世界（large world，意思是特征路徑長度很大），其特征路徑長度隨著n(網(wǎng)絡中節(jié)點的數(shù)量)線性增長，而隨機網(wǎng)絡聚合系數(shù)很小，小世界（small world，意思是特征路徑長度?。涮卣髀窂介L度隨著log(n)增長中說明，在從規(guī)則網(wǎng)絡向隨機網(wǎng)絡轉換的過程中，實際上特征路徑長度和聚合系數(shù)都會下降，到變成隨機網(wǎng)絡的時候，減少到最少。但這并不是說大的聚合系數(shù)一定伴隨著大的路徑長度，而小的路徑長度伴隨著小的聚合系數(shù)，小世界網(wǎng)絡就具有

5、大的聚合系數(shù)，而特征路徑長度很小。試驗表明，少量的short cut的建立能夠迅速減少特征路徑長度，而聚合系數(shù)變化卻不大，因為某一個short cut的建立，不僅影響到所連接的節(jié)點的特征路徑長度，而且影響到他們鄰居的路徑長度，而對整個網(wǎng)絡的聚合系數(shù)影響不大。這樣，少量的short cut的建立就能使整個網(wǎng)絡不知不覺地變成小世界網(wǎng)絡。 實際的社會、生態(tài)、等網(wǎng)絡都是小世界網(wǎng)絡，在這樣的系統(tǒng)里，信息傳遞速度快，并且少量改變幾個連接，就可以劇烈地改變網(wǎng)絡的性能，如對已存在的網(wǎng)絡進行調整，如蜂窩電話網(wǎng)，改動很少幾條線路，就可以顯著提高性能。 2.小世界網(wǎng)絡構成原則 WS小世界網(wǎng)絡的構成原則為：從一個環(huán)狀

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

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

8、在隨機選取的一對結點之間加上一條邊 matrix=sparse(,20,20,0);% 創(chuàng)建一個20*20的全0稀疏矩陣 %建立初始的環(huán)狀的規(guī)則網(wǎng)絡 %結點網(wǎng)絡有N個節(jié)點 %每個結點向與它最近鄰的m個結點連出邊 %求出鄰接矩陣 for i=m+1:N-m for j=i-m:i+m matrix(i,j)=1; end end for i=1:m for j=1:i+m matrix(i,j)=1; end end for i=N-m+1:N for j=i-m:N matrix(i,j)=1; end end for i=1:m for j=N-m+i:N matrix(i,j)=1;mat

9、rix(j,i)=1; end end %逆時針的邊重連,從節(jié)點到N-m-1 for i=1:N-m-1 for j=i+1:i+m r=rand(1);% 隨機選取一個數(shù) if r<=p unconect=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小世界

10、網(wǎng)絡 end end end %逆時針的邊重新連接,從節(jié)點N-m到N-1 for i=N-m+1:N-1 for j=i+1:N 1:i- N+m r=rand(1); if r<=p unconect=find(matrix(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; end end end %逆時針的邊重新連接,節(jié)點N for i=N for j=1:m r=rand(1); if

11、r<=p unconect=find(matrix(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; end end end %恢復小世界網(wǎng)絡的鄰接矩陣 for m=1:N matrix(m,m)=0;% 去掉自身節(jié)點形成的環(huán) end %存儲鄰接矩陣 %save data matrix; toc %計算程序耗時 end 上述程序建立了一個NW小世界網(wǎng)絡，求出了其鄰接矩陣，用tu_plot()函數(shù)

12、畫出鄰接矩陣的圖，就得出了該小世界網(wǎng)絡的圖形。 function tu_plot(rel,control) %由鄰接矩陣畫連接圖，輸入為鄰接矩陣rel，必須為方陣； %control為控制量，0表示畫出的圖為無向圖，1表示有向圖。默認值為0 r_size=size(rel);%a=size(x)返回的是一個行向量，該行向量第一個元素是 %x的行數(shù)，第2個元素是x的列數(shù) if nargin<2 %nargin是用來判斷輸入變量個數(shù)的函數(shù) control=0; %輸入變量小于2，即只有一個，就默認control為0 end if r_size(1)=r_size(2)%行數(shù)和列數(shù)不相等，不是

13、方陣，不予處理 disp('Wrong Input! The input must be a square matrix!'); return; end len=r_size(1); rho=10;%限制圖尺寸的大小 r=2/1.05len;%點的半徑 theta=0:(2*pi/len):2*pi*(1-1/len); pointx,pointy=pol2cart(theta',rho); theta=0:pi/36:2*pi; tempx,tempy=pol2cart(theta',r); point=pointx,pointy; hold on for i

14、=1:len temp=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);%畫點 end for i=1:len for j=1:len if rel(i,j) link_plot(point(i,:),point(j,:),r,control); %連接有關系的點 end end end set(gca,'XLim&#

15、39;,-rho-r,rho+r,'YLim',-rho-r,rho+r); axis off function link_plot(point1,point2,r,control)%連接兩點 temp=point2-point1; if (temp(1)&&(temp(2) return;%不畫子回路 end theta=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*(thet