小世界網(wǎng)絡.doc

_4.2 小世界網(wǎng)絡4.2.1 小世界網(wǎng)絡簡介1998年, Watts和Strogatz 提出了小世界網(wǎng)絡這一概念，并建立了WS模型。實證結果表明，大多數(shù)的真實網(wǎng)絡都具有小世界特性（較小的最短路徑）和聚類特性（較大的聚類系數(shù)）。傳統(tǒng)的規(guī)則最近鄰耦合網(wǎng)絡具有高聚類的特性，但并不具有小世界特性；而隨機網(wǎng)絡具有小世界特性但卻沒有高聚類特性。因此這兩種傳統(tǒng)的網(wǎng)絡模型都不能很好的來表示實際的真實網(wǎng)絡。Watts和Strogatz建立的小世界網(wǎng)絡模型就介于這兩種網(wǎng)絡之間，同時具有小世界特性和聚類特性，可以很好的來表示真實網(wǎng)絡。4.2.2 小世界模型構造算法1、從規(guī)則圖開始：考慮一個含有N個點的最近鄰耦合網(wǎng)絡，它們圍成一個環(huán)，其中每個節(jié)點都與它左右相鄰的各K/2節(jié)點相連，K是偶數(shù)。2、隨機化重連：以概率p隨機地從新連接網(wǎng)絡中的每個邊，即將邊的一個端點保持不變，而另一個端點取為網(wǎng)絡中隨機選擇的一個節(jié)點。其中規(guī)定，任意兩個不同的節(jié)點之間至多只能有一條邊，并且每一個節(jié)點都不能有邊與自身相連。在上述模型中，p=0對應于完全規(guī)則網(wǎng)絡，p=1則對應于完全隨機網(wǎng)絡，通過調(diào)節(jié)p的值就可以控制從完全規(guī)則網(wǎng)絡到完全隨機網(wǎng)絡的過渡。相應程序代碼（使用Matlab實現(xiàn)）ws_net.m （位于“代碼”文件夾內(nèi)）function ws_net()disp(小世界網(wǎng)絡模型)N=input(請輸入網(wǎng)絡節(jié)點數(shù));K=input(請輸入與節(jié)點左右相鄰的K/2的節(jié)點數(shù));p=input(請輸入隨機重連的概率);angle=0:2*pi/N:2*pi-2*pi/N;x=100*cos(angle);y=100*sin(angle);plot(x,y,r.,Markersize,30);hold on;%生成最近鄰耦合網(wǎng)絡；A=zeros(N);disp(A);for i=1:Nif i+K=Nfor j=i+1:i+KA(i,j)=1;endelsefor j=i+1:NA(i,j)=1; endfor j=1:(i+K)-N) A(i,j)=1; endendif Kifor j=i-K:i-1 A(i,j)=1;endelsefor j=1:i-1A(i,j)=1; endfor j=N-K+i:N A(i,j)=1; endendenddisp(A);%隨機化重連for i=1:Nfor j=i+1:Nif A(i,j)=1pp=unifrnd(0,1); if ppnjj=mod(j,n);endA(i,jj)=1; A(jj,i)=1;endend%計算平均路徑長度L(0)D1=A;D1(find(D1=0)=inf; %將鄰接矩陣變?yōu)猷徑泳嚯x矩陣，兩點無邊相連時賦值為inf，自身到自身的距離為0.for i=1:nD1(i,i)=0;endm=1;while mD1(i,m)+D1(m,j)D1(i,j)=D1(i,m)+D1(m,j);endendendm=m+1;endL0=sum(sum(D1)/(n*(n-1); %平均路徑長度%計算聚類系數(shù)C(0)Ci0=zeros(n,1);for i=1:naa1=find(D1(i,:)=1); %尋找子圖的鄰居節(jié)點if isempty(aa1)Ci0(i)=0;elsem1=length(aa1);if m1=1Ci0(i)=0;elseB1=D1(aa1,aa1); % 抽取子圖的鄰接矩陣Ci0(i)=length(find(B1=1)/(m1*(m1-1);endendendC0=mean(Ci0);for z=1:14% p(z)=1/2(z-1);for g=1:20%生成最近鄰耦合網(wǎng)絡B=zeros(n);for i=1:nfor j=i+1:i+kjj=j;if jnjj=mod(j,n);endB(i,jj)=1; B(jj,i)=1;endend%隨機化重連% for i=1:n% p_rand=rand(1,1);% b=find(B(i,:)=1);% for j=1:length(b)% j1=b(j);% if p_randp(z,1) % 生成的隨機數(shù)小于p，則邊進行隨機化重連,否則，邊不進行重連% B(i,j1)=0;B(j1,i)=0;% bb=randint(1,1,1,n);% if B(i,bb)=0&B(bb,i)=0&bb=i %重連條件% B(i,bb)=1;B(bb,i)=1;% end% end% end% endfor i=1:nfor j=1:kp_rand=rand(1,1);if p_randnj2=mod(j2,n);endB(i,j2)=0;B(j2,i)=0;B(i,bb)=1;B(bb,i)=1;endendendend%計算平均路徑長度aver_L% n1=size(A,2);D=B;D(find(D=0)=inf; %將鄰接矩陣變?yōu)猷徑泳嚯x矩陣，兩點無邊相連時賦值為inf，自身到自身的距離為0.for i=1:nD(i,i)=0;endm2=1;while m2D(i,m2)+D(m2,j)D(i,j)=D(i,m2)+D(m2,j);endendendm2=m2+1;end% if length(infline)0% D(infline,:)=;% D(:,infline)=;% n2=size(D,2);% L(z,g)=sum(sum(D)/(n2*(n2-1);%求出平均路徑% elseL(z,g)=sum(sum(D)/(n*(n-1);%求出平均路徑% end%計算聚類系數(shù)aver_CCi=zeros(n,1);for i=1:naa=find(D(i,:)=1); %尋找子圖的鄰居節(jié)點if isempty(aa)Ci(i)=0;elsem3=length(aa);if m3=1Ci(i)=0;elseBB=D(aa,aa); % 抽取子圖的鄰接矩陣Ci(i)=length(find(BB=1)/(m3*(m3-1);endendendC(z,g)=mean(Ci);endendfigureLWS=mean(L,2);CWS=mean(C,2);semilogx(p,LWS/L0,ro);hold on;semilogx(p,CWS/C0,b*);4.2.4 小結在網(wǎng)絡理論中，小世界網(wǎng)絡是一類特殊的復雜網(wǎng)絡結構，在這種網(wǎng)絡中大部分的節(jié)點彼此并不相連，但絕大部份節(jié)點之間經(jīng)過少數(shù)幾步就可到達。在日常生活中，有時你會發(fā)現(xiàn)，某些你覺得與你隔得很“遙遠”的人，其實與你“很近”。小世界網(wǎng)絡就是對這種現(xiàn)象（也稱為小世界現(xiàn)象）的數(shù)學描述。用數(shù)學中圖論的語言來說，小世界網(wǎng)絡就是一個由大量頂點構成的圖，其中任意兩點之間的平均路徑長度比頂點數(shù)量小得多。除了社會人際網(wǎng)絡以外，小世界網(wǎng)絡的例子在生物學、物理學、計算機科學等領域也有出現(xiàn)。許多經(jīng)驗中的圖可以由小世界網(wǎng)絡來作為模型。萬維網(wǎng)、公路交通網(wǎng)、腦神經(jīng)網(wǎng)絡和基因網(wǎng)絡都呈現(xiàn)小世界網(wǎng)絡的特征。