WS小世界網(wǎng)絡(luò)模型構(gòu)造實(shí)踐報(bào)告.docVIP

1、課題：ws小世界網(wǎng)絡(luò)模型構(gòu)造姓名 趙訓(xùn) 學(xué)號(hào) 201026811130 班級(jí) 計(jì)算機(jī)實(shí)驗(yàn)班 一、ws 小世界網(wǎng)絡(luò)簡(jiǎn)介1998年, watts和strogatz 提出了小世界網(wǎng)絡(luò)這一概念,并建立了ws模型。 實(shí)證結(jié)果表明,大多數(shù)的真實(shí)網(wǎng)絡(luò)都具有小世界特性(較小的最短路徑) 和聚類(lèi)特性(較大的聚類(lèi)系數(shù)) 。 傳統(tǒng)的規(guī)則最近鄰耦合網(wǎng)絡(luò)具有高聚類(lèi)的特性,但并不具有小世界特性;而er 隨機(jī)網(wǎng)絡(luò)具有小世界特性但卻沒(méi)有高聚類(lèi)特性。 因此這兩種傳統(tǒng)的網(wǎng)絡(luò)模型都不能很好的來(lái)表示實(shí)際的真實(shí)網(wǎng)絡(luò)。 watts和strogatz建立的ws小世界網(wǎng)絡(luò)模型就介于這兩種網(wǎng)絡(luò)之間,同時(shí)具有小世界特性和聚類(lèi)特性,可以很好的來(lái)表

2、示真實(shí)網(wǎng)絡(luò)。二、ws小世界模型構(gòu)造算法1、從規(guī)則圖開(kāi)始：考慮一個(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ò)，通過(guò)調(diào)節(jié)p的值就可以控制從完全規(guī)則網(wǎng)絡(luò)到完全隨機(jī)網(wǎng)絡(luò)的過(guò)渡，如圖a所示。圖a相應(yīng)程序代碼（使用matlab實(shí)現(xiàn)）ws_net.m （位于“代碼”文件夾內(nèi)）fun

3、ction ws_net()disp(ws小世界網(wǎng)絡(luò)模型)n=input(請(qǐng)輸入網(wǎng)絡(luò)節(jié)點(diǎn)數(shù));k=input(請(qǐng)輸入與節(jié)點(diǎn)左右相鄰的k/2的節(jié)點(diǎn)數(shù));p=input(請(qǐng)輸入隨機(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:n if i+k=n for j=i+1:i+k a(i,j)=1; end else for j=i+1:n a(i,j)=1; end f

4、or j=1:(i+k)-n) a(i,j)=1; end end if ki for j=i-k:i-1 a(i,j)=1; end else for j=1:i-1 a(i,j)=1; end for j=n-k+i:n a(i,j)=1; end endenddisp(a);%隨機(jī)化重連for i=1:n for j=i+1:n if a(i,j)=1 pp=unifrnd(0,1); if ppn jj=mod(j,n); end a(i,jj)=1; a(jj,i)=1; endend%計(jì)算平均路徑長(zhǎng)度l(0)d1=a;d1(find(d1=0)=inf; %將鄰接矩陣變?yōu)猷徑泳嚯x矩

5、陣，兩點(diǎn)無(wú)邊相連時(shí)賦值為inf，自身到自身的距離為0.for i=1:n d1(i,i)=0;endm=1;while md1(i,m)+d1(m,j) d1(i,j)=d1(i,m)+d1(m,j); end end end m=m+1;endl0=sum(sum(d1)/(n*(n-1); %平均路徑長(zhǎng)度%計(jì)算聚類(lèi)系數(shù)c(0)ci0=zeros(n,1);for i=1:n aa1=find(d1(i,:)=1); %尋找子圖的鄰居節(jié)點(diǎn) if isempty(aa1) ci0(i)=0; else m1=length(aa1); if m1=1 ci0(i)=0; else b1=d1(a

6、a1,aa1); % 抽取子圖的鄰接矩陣 ci0(i)=length(find(b1=1)/(m1*(m1-1); end endendc0=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:n for j=i+1:i+k jj=j; if jn jj=mod(j,n); end b(i,jj)=1; b(jj,i)=1; end end %隨機(jī)化重連 % for i=1:n% p_rand=rand(1,1);% b=find(b(i,:)=1);% for j=1:length(b

7、)% 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% end for i=1:n for j=1:k p_rand=rand(1,1); if p_randn j2=mod(j2,n); end b(i,j2)=0; b(j2,i)=0; b(i,bb)=1; b(bb,i)=1; end end

8、 end end %計(jì)算平均路徑長(zhǎng)度aver_l % n1=size(a,2); d=b; d(find(d=0)=inf; %將鄰接矩陣變?yōu)猷徑泳嚯x矩陣，兩點(diǎn)無(wú)邊相連時(shí)賦值為inf，自身到自身的距離為0. for i=1:n d(i,i)=0; end m2=1; while m2d(i,m2)+d(m2,j) d(i,j)=d(i,m2)+d(m2,j); end end end m2=m2+1; end % if length(infline)0% d(infline,:)=;% d(:,infline)=;% n2=size(d,2);% l(z,g)=sum(sum(d)/(n2*(

9、n2-1);%求出平均路徑% else l(z,g)=sum(sum(d)/(n*(n-1);%求出平均路徑% end %計(jì)算聚類(lèi)系數(shù)aver_c ci=zeros(n,1); for i=1:n aa=find(d(i,:)=1); %尋找子圖的鄰居節(jié)點(diǎn) if isempty(aa) ci(i)=0; else m3=length(aa); if m3=1 ci(i)=0; else bb=d(aa,aa); % 抽取子圖的鄰接矩陣 ci(i)=length(find(bb=1)/(m3*(m3-1); end end end c(z,g)=mean(ci); endendfigurelws

10、=mean(l,2);cws=mean(c,2);semilogx(p,lws/l0,ro);hold on;semilogx(p,cws/c0,b*);對(duì)應(yīng)輸出(ws.fig的截圖)與圖b（圖b位于第7頁(yè)）吻合四、結(jié)論在網(wǎng)絡(luò)理論中，小世界網(wǎng)絡(luò)是一類(lèi)特殊的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)，在這種網(wǎng)絡(luò)中大部份的節(jié)點(diǎn)彼此并不相連，但絕大部份節(jié)點(diǎn)之間經(jīng)過(guò)少數(shù)幾步就可到達(dá)（本文只討論ws小世界模型）。在日常生活中，有時(shí)你會(huì)發(fā)現(xiàn)，某些你覺(jué)得與你隔得很“遙遠(yuǎn)”的人，其實(shí)與你“很近”。小世界網(wǎng)絡(luò)就是對(duì)這種現(xiàn)象（也稱(chēng)為小世界現(xiàn)象）的數(shù)學(xué)描述。用數(shù)學(xué)中圖論的語(yǔ)言來(lái)說(shuō)，小世界網(wǎng)絡(luò)就是一個(gè)由大量頂點(diǎn)構(gòu)成的圖，其中任意兩點(diǎn)之間的平均路徑

11、長(zhǎng)度比頂點(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ò)來(lái)作為模型。萬(wàn)維網(wǎng)、公路交通網(wǎng)、腦神經(jīng)網(wǎng)絡(luò)和基因網(wǎng)絡(luò)都呈現(xiàn)小世界網(wǎng)絡(luò)的特征。小世界網(wǎng)絡(luò)模型反映了朋友關(guān)系網(wǎng)絡(luò)的一種特性，即大部分的人的朋友都是和他們住在同一條街上的鄰居或在同一單位工作的同事。另一方面，也有些人是住得較遠(yuǎn)的，甚至是遠(yuǎn)在異國(guó)他鄉(xiāng)的朋友，這種情形對(duì)應(yīng)于ws小世界模型中通過(guò)重新連線(xiàn)產(chǎn)生的遠(yuǎn)程連接。五、參考來(lái)源1.ws與nw兩種小世界網(wǎng)絡(luò)模型的建模及仿真研究王波,王萬(wàn)良,楊旭華 浙江工業(yè)大學(xué)學(xué)報(bào) 第37 卷第2 期 2009 年4 月2.“小世界”網(wǎng)絡(luò)的集體動(dòng)力學(xué) duncan j. watts ， steven h. strogatz （nature | vol 393 |