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

_4.2 小世界網(wǎng)絡(luò)4.2.1 小世界網(wǎng)絡(luò)簡介1998年, Watts和Strogatz 提出了小世界網(wǎng)絡(luò)這一概念，并建立了WS模型。實(shí)證結(jié)果表明，大多數(shù)的真實(shí)網(wǎng)絡(luò)都具有小世界特性（較小的最短路徑）和聚類特性（較大的聚類系數(shù)）。傳統(tǒng)的規(guī)則最近鄰耦合網(wǎng)絡(luò)具有高聚類的特性，但并不具有小世界特性；而隨機(jī)網(wǎng)絡(luò)具有小世界特性但卻沒有高聚類特性。因此這兩種傳統(tǒng)的網(wǎng)絡(luò)模型都不能很好的來表示實(shí)際的真實(shí)網(wǎng)絡(luò)。Watts和Strogatz建立的小世界網(wǎng)絡(luò)模型就介于這兩種網(wǎng)絡(luò)之間，同時(shí)具有小世界特性和聚類特性，可以很好的來表示真實(shí)網(wǎng)絡(luò)。4.2.2 小世界模型構(gòu)造算法1、從規(guī)則圖開始：考慮一個(gè)含有N個(gè)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)，它們圍成一個(gè)環(huán)，其中每個(gè)節(jié)點(diǎn)都與它左右相鄰的各K/2節(jié)點(diǎn)相連，K是偶數(shù)。2、隨機(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)都不能有邊與自身相連。在上述模型中，p=0對(duì)應(yīng)于完全規(guī)則網(wǎng)絡(luò)，p=1則對(duì)應(yīng)于完全隨機(jī)網(wǎng)絡(luò)，通過調(diào)節(jié)p的值就可以控制從完全規(guī)則網(wǎng)絡(luò)到完全隨機(jī)網(wǎng)絡(luò)的過渡。相應(yīng)程序代碼（使用Matlab實(shí)現(xiàn)）ws_net.m （位于“代碼”文件夾內(nèi)）function ws_net()disp(小世界網(wǎng)絡(luò)模型)N=input(請輸入網(wǎng)絡(luò)節(jié)點(diǎn)數(shù));K=input(請輸入與節(jié)點(diǎn)左右相鄰的K/2的節(jié)點(diǎn)數(shù));p=input(請輸入隨機(jī)重連的概率);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)絡(luò)；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);%隨機(jī)化重連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%計(jì)算平均路徑長度L(0)D1=A;D1(find(D1=0)=inf; %將鄰接矩陣變?yōu)猷徑泳嚯x矩陣，兩點(diǎn)無邊相連時(shí)賦值為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); %平均路徑長度%計(jì)算聚類系數(shù)C(0)Ci0=zeros(n,1);for i=1:naa1=find(D1(i,:)=1); %尋找子圖的鄰居節(jié)點(diǎn)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)絡(luò)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%隨機(jī)化重連% 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) % 生成的隨機(jī)數(shù)小于p，則邊進(jìn)行隨機(jī)化重連,否則，邊不進(jìn)行重連% 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%計(jì)算平均路徑長度aver_L% n1=size(A,2);D=B;D(find(D=0)=inf; %將鄰接矩陣變?yōu)猷徑泳嚯x矩陣，兩點(diǎn)無邊相連時(shí)賦值為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%計(jì)算聚類系數(shù)aver_CCi=zeros(n,1);for i=1:naa=find(D(i,:)=1); %尋找子圖的鄰居節(jié)點(diǎn)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 小結(jié)在網(wǎng)絡(luò)理論中，小世界網(wǎng)絡(luò)是一類特殊的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)，在這種網(wǎng)絡(luò)中大部分的節(jié)點(diǎn)彼此并不相連，但絕大部份節(jié)點(diǎn)之間經(jīng)過少數(shù)幾步就可到達(dá)。在日常生活中，有時(shí)你會(huì)發(fā)現(xiàn)，某些你覺得與你隔得很“遙遠(yuǎn)”的人，其實(shí)與你“很近”。小世界網(wǎng)絡(luò)就是對(duì)這種現(xiàn)象（也稱為小世界現(xiàn)象）的數(shù)學(xué)描述。用數(shù)學(xué)中圖論的語言來說，小世界網(wǎng)絡(luò)就是一個(gè)由大量頂點(diǎn)構(gòu)成的圖，其中任意兩點(diǎn)之間的平均路徑長度比頂點(diǎn)數(shù)量小得多。除了社會(huì)人際網(wǎng)絡(luò)以外，小世界網(wǎng)絡(luò)的例子在生物學(xué)、物理學(xué)、計(jì)算機(jī)科學(xué)等領(lǐng)域也有出現(xiàn)。許多經(jīng)驗(yàn)中的圖可以由小世界網(wǎng)絡(luò)來作為模型。萬維網(wǎng)、公路交通網(wǎng)、腦神經(jīng)網(wǎng)絡(luò)和基因網(wǎng)絡(luò)都呈現(xiàn)小世界網(wǎng)絡(luò)的特征。