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

1、WS小世界網(wǎng)絡(luò)模型構(gòu)造課題：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ò)這一概念，并建立了 W濮型。實(shí)證結(jié)果表明，大多數(shù)的真實(shí)網(wǎng)絡(luò)都具有小世界特性（較小的最短路徑）和聚類特性（較大的聚類系數(shù)）。傳統(tǒng)的規(guī) 則最近鄰耦合網(wǎng)絡(luò)具有高聚類的特性，但并不具有小世界特性；而ER隨機(jī)網(wǎng)絡(luò)具有小世界特性但卻沒(mé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)表示真

2、實(shí)網(wǎng)絡(luò)。二、WSb世界模型構(gòu)造算法它們圍成一個(gè)環(huán)，其中每個(gè)節(jié)點(diǎn)都與即將邊的一個(gè)端點(diǎn)保持不變，而另1、從規(guī)則圖開(kāi)始：考慮一個(gè)含有 r個(gè)點(diǎn)的最近鄰耦合網(wǎng)絡(luò), 它左右相鄰的各K/2節(jié)點(diǎn)相連，K是偶數(shù)。2、隨機(jī)化重連：以概率p隨機(jī)地從新連接網(wǎng)絡(luò)中的每個(gè)邊，個(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所示。規(guī)則網(wǎng)絡(luò) WS小世界網(wǎng)絡(luò)隨機(jī)網(wǎng)絡(luò)p = 00<p<Ip-I相應(yīng)程序代碼（使用

3、Matlab實(shí)現(xiàn)）ws_net.m （位于“代碼”文件夾內(nèi)）fun ctio n ws_n et()disp('WS小世界網(wǎng)絡(luò)模型')N=i nput('請(qǐng)輸入網(wǎng)絡(luò)節(jié)點(diǎn)數(shù))；K=input('請(qǐng)輸入與節(jié)點(diǎn)左右相鄰的K/2的節(jié)點(diǎn)數(shù)');p=i nput('請(qǐng)輸入隨機(jī)重連的概率');an gle=0:2*pi/N:2*pi-2*pi/N;x=100*cos(a ngle);y=100*si n(an gle);plot(x,y,'r.','Markersize',30);hold on;%fc成最近鄰耦合網(wǎng)絡(luò)；

4、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 K<ifor j=i-K:i-1A(i,j)=1;end elsefor j=1:i-1A(i,j)=1;endfor j=N-K+i:NA(i,j)=1;endendenddisp(A);%隨機(jī)化重連for i=1:Nfor j=i+1:N if A(i,j)=1 pp=unifrn d(0,1);if pp<=pA(i,j)=0;

5、A(j,i)=0; b=unidrn d(N); while i=b b=unidrn d(N);endA(i,b)=1;A(b,i)=1;endendendend% 艮據(jù)鄰接矩陣連線for i=1:Nfor j=1:Nif A(i,j)=1plot(x(i),x(j),y(i),y(j),'li newidth',1); hold on;endendendhold offaver_path=aver_pathle ngth(A); disp(aver_path);對(duì)應(yīng)輸出（取網(wǎng)絡(luò)節(jié)點(diǎn)數(shù) N=16, K=2; p分別取0, 0.1 , 1）。p=0( ws_n=16_k=2_p

6、=0.fig 的截圖)P=0.1 （ws_n=16_k=2_p=0.1.fig 的截圖）-100-80-60-40-20020406080100p=1 （ws_n=16_k=2_p=1.fig 的截圖）輸出結(jié)果與圖a（圖a位于第2頁(yè)）吻合。三、WS、世界網(wǎng)絡(luò)模型平均路徑長(zhǎng)度 L（p）與聚類系數(shù)C（p）歸一化圖平均路徑長(zhǎng)度平均路徑長(zhǎng)度也稱為特征路徑長(zhǎng)度或平均最短路徑長(zhǎng)度，指的是一個(gè)網(wǎng)絡(luò)中兩點(diǎn)之間最短路徑長(zhǎng)度（或稱距離）的平均值。從一個(gè)節(jié)點(diǎn)Si出發(fā)，經(jīng)過(guò)與它相連的節(jié)點(diǎn)，逐步“走” 到另一個(gè)節(jié)點(diǎn)s所經(jīng)過(guò)的路途，稱為兩點(diǎn)間的路徑。其中最短的路徑也稱為兩點(diǎn)間的距離，記作而平均路徑長(zhǎng)度定義為:這其中N是節(jié)

7、點(diǎn)數(shù)目，并定義節(jié)點(diǎn)到自身的最短路徑長(zhǎng)度為0。如果不計(jì)算到自身的距離，那么平均路徑長(zhǎng)度的定義就變成：集聚系數(shù)集聚系數(shù)（也稱群聚系數(shù)、 集群系數(shù)）是用來(lái)描述圖或網(wǎng)絡(luò)中的頂點(diǎn)（節(jié)點(diǎn)）之間結(jié)集 成團(tuán)的程度的系數(shù)。具體來(lái)說(shuō)，是一個(gè)點(diǎn)的鄰接點(diǎn)之間相互連接的程度。例如在社交網(wǎng) 絡(luò)中，你的朋友之間相互認(rèn)識(shí)的程度。一個(gè)節(jié)點(diǎn)Si的集聚系數(shù) Qi）等于所有與它相連的頂點(diǎn)相互之間所連的邊的數(shù)量， 除以這些頂點(diǎn)之間可以連出的最大邊數(shù)。顯然Ci）是一個(gè)介于0與1之間的數(shù)。C（i）越接近1,表示這個(gè)節(jié)點(diǎn)附近的點(diǎn)越有 "抱團(tuán)”的趨 勢(shì)。介于隨機(jī)與規(guī)則之間對(duì)于純粹的規(guī)則網(wǎng)絡(luò)， 當(dāng)其中連接數(shù)量接近飽和時(shí)，集聚系數(shù)很高，

8、 分短。例如完全耦合網(wǎng)絡(luò)，每?jī)蓚€(gè)節(jié)點(diǎn)之間都相連，所以集聚系數(shù)是平均路徑長(zhǎng)度也十1,平均路徑長(zhǎng)度是1。然而，現(xiàn)實(shí)中的復(fù)雜網(wǎng)絡(luò)是稀疏的，連接的個(gè)數(shù)只是節(jié)點(diǎn)數(shù)的若干倍）,每各節(jié)點(diǎn)都只與距離它最近的 2K個(gè)遠(yuǎn)遠(yuǎn)不到飽和。如果考慮將節(jié)點(diǎn)排列成正多邊形, 節(jié)點(diǎn)相連，那么在 K比較大時(shí)，其集聚系數(shù)為：(K t)(37J2)32K(2K - i) 4雖然能保持高集聚系數(shù)，但平均路徑長(zhǎng)度為:平均路徑長(zhǎng)度與節(jié)點(diǎn)數(shù)成正比。純粹的隨機(jī)網(wǎng)絡(luò)（如 ER隨機(jī)網(wǎng)絡(luò)模型）有著很小的平均路徑長(zhǎng)度，但同時(shí)集聚系數(shù)也 很小。可是現(xiàn)實(shí)中的不少網(wǎng)絡(luò)雖然有很小的平均路徑長(zhǎng)度，但卻也有著比隨機(jī)網(wǎng)絡(luò)高出相當(dāng)多的集聚系數(shù)。因此瓦茨和斯特羅加茨認(rèn)

9、為，現(xiàn)實(shí)中的復(fù)雜網(wǎng)絡(luò)是一種介于規(guī)則網(wǎng) 絡(luò)和隨機(jī)網(wǎng)絡(luò)之間的網(wǎng)絡(luò)。他們把這種特性稱為現(xiàn)實(shí)網(wǎng)絡(luò)的小世界特性，就是：1.有很小的平均路徑長(zhǎng)度：在節(jié)點(diǎn)數(shù)N很大時(shí)，平均路徑長(zhǎng)度近似于distc ex log(Al2.有很高的集聚系數(shù)：集聚系數(shù)大約和規(guī)則網(wǎng)絡(luò)在同一數(shù)量級(jí)，遠(yuǎn)大于隨機(jī)網(wǎng)絡(luò) 的集聚系數(shù)。相應(yīng)程序代碼(使用Matlab實(shí)現(xiàn))ws.m (位于“代碼”文件夾內(nèi))clc;clear all;format lo ng;n=1000;k=5;L=zeros(14,20);C=zeros(14,20);for i=1:14p(15-i,1)=1/2A(i-1);end% p=zeros(1,14);% p1=

10、 zeros(14,20);% LWS=zeros(14,1);% CWS=zeros(14,1);%生成最近鄰耦合網(wǎng)絡(luò)A=zeros (n);for i=1: nfor j=i+1:i+kjj=j;if j>njj=mod(j, n);endA(i,jj)=1; A(jj,i)=1;endend%計(jì)算平均路徑長(zhǎng)度L(0)D1=A;inf,自身D1(fi nd(D1=0)=i nf;%將鄰接矩陣變?yōu)猷徑泳嚯x矩陣，兩點(diǎn)無(wú)邊相連時(shí)賦值為到自身的距離為 0.for i=1: nD1(i,i)=0;endm=1;while m<=n%Floyd算法求解任意兩點(diǎn)的最短距離for i=1: n

11、for j=1: nif D1(i,j)>D1(i,m)+D1(m,j)D1(i,j)=D1(i,m)+D1(m,j);endendendm=m+1;endL0=sum(sum(D1)/( n*( n-1);% 平均路徑長(zhǎng)度%十算聚類系數(shù)C(0)CiO=zeros( n,1);for i=1: naa1=fi nd(D1(i,:)=1);%尋找子圖的鄰居節(jié)點(diǎn)if isempty(aal)Ci0(i)=0;elsem1=le ngth(aa1);if m1=1Ci0(i)=0;elseB仁D1(aa1,aa1);%抽取子圖的鄰接矩陣CiO(i)=le ngth(fi nd(B 1=1)/(

12、m1*(m1-1);endendendC0=mea n(CiO);for z=1:14%p(z)=1/2A(z-1);for g=1:20%生成最近鄰耦合網(wǎng)絡(luò)B=zeros (n);for i=1: nfor j=i+1:i+kjj=j；if j>njj=mod(j, n); endB(i,jj)=1; B(jj,i)=1; endend%隨機(jī)化重連for i=1:n%p_ra nd=ra nd(1,1);%b=fi nd(B(i,:)=1);%for j=1:le ngth(b)%j仁 b(j);%if p_rand<p(z,1)%生成的隨機(jī)數(shù)小于p,則邊進(jìn)行隨機(jī)化重連，否則，邊

13、不進(jìn)行重連%件%endendendB(i,j1)=0;B(j1,i)=0;bb=ra ndin t(1,1,1, n);if B(i,bb)=0&&B(bb,i)=0&&bb=iB(i,bb)=1;B(bb,i)=1;end%重連條for i=1: nfor j=1:kp_ran d=ra nd(1,1);if p_ra nd<p(z,1)bb=ra ndin t(1,1,1, n);if B(i,bb)=0&&B(bb,i)=0&&bb=i j2=j+i;if j2>nj2=mod(j2, n);endB(i,j2)

14、=0;B(j2,i)=0;B(i,bb)=1;B(bb,i)=1;endendendend%計(jì)算平均路徑長(zhǎng)度aver_L%n仁 size(A,2);D=B;%重連條件兩點(diǎn)無(wú)邊相連時(shí)賦值為inf，D(fi nd(D=0)=i nf;%將鄰接矩陣變?yōu)猷徑泳嚯x矩陣,自身到自身的距離為 0.for i=1: nD(i,i)=0;endm2=1;while m2<=n%Floyd算法求解任意兩點(diǎn)的最短距離for i=1: nfor j=1: nif D(i,j)>D(i,m2)+D(m2,j)D(i,j)=D(i,m2)+D(m2,j);endendendm2=m2+1;end%if len

15、 gth(i nflin e)>0%D(i nflin e,:)=;%D(:,i nflin e)=;%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=fi nd(D(i,:)=1);%尋找子圖的鄰居節(jié)點(diǎn)if isempty(aa)Ci(i)=0;elsem3=le ngth(aa);if m3=1Ci(i)=0;elseBB=D(aa,aa);%抽取子圖的鄰接矩陣C

16、i(i)=le ngth(fi nd(BB=1)/(m3*(m3-1);endendendC(z,g)=mea n( Ci);endendfigureLWS=mea n( L,2);CWS=mea n(C,2); semilogx(p, LWS/LO,'ro'); hold on; semilogx(p,CWS/CO,'b*');對(duì)應(yīng)輸出（ws.fig的截圖） * 才* +'4- 1' 廠+*0704020.110O <>M I L卜10'與圖b （圖b位于第7頁(yè)）吻合四、結(jié)論在網(wǎng)絡(luò)理論中，小世界網(wǎng)絡(luò)是一類特殊的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)，

17、在這種網(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)象（也稱為小世界現(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ò)的例子在生物學(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ò)重新連線產(chǎn)生的遠(yuǎn)程連接。五、參考來(lái)源1. W與NV兩種小世界網(wǎng)絡(luò)模型的建模及仿真研究王波,王萬(wàn)良，楊旭華 浙