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

./課題：WS小世界網(wǎng)絡(luò)模型構(gòu)造訓(xùn)學(xué)號(hào)0班級(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ò)都具有小世界特性<較小的最短路徑>和聚類特性<較大的聚類系數(shù)>。傳統(tǒng)的規(guī)則最近鄰耦合網(wǎng)絡(luò)具有高聚類的特性,但并不具有小世界特性;而ER隨機(jī)網(wǎng)絡(luò)具有小世界特性但卻沒有高聚類特性。因此這兩種傳統(tǒng)的網(wǎng)絡(luò)模型都不能很好的來表示實(shí)際的真實(shí)網(wǎng)絡(luò)。Watts和Strogatz建立的WS小世界網(wǎng)絡(luò)模型就介于這兩種網(wǎng)絡(luò)之間,同時(shí)具有小世界特性和聚類特性,可以很好的來表示真實(shí)網(wǎng)絡(luò)。二、WS小世界模型構(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ò)的過渡,如圖a所示。圖a相應(yīng)程序代碼〔使用Matlab實(shí)現(xiàn)ws_net.m〔位于"代碼"文件夾functionws_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>;holdon;%生成最近鄰耦合網(wǎng)絡(luò)；A=zeros<N>;disp<A>;fori=1:Nifi+K<=Nforj=i+1:i+KA<i,j>=1;endelseforj=i+1:NA<i,j>=1;endforj=1:<<i+K>-N>A<i,j>=1;endendifK<iforj=i-K:i-1A<i,j>=1;endelseforj=1:i-1A<i,j>=1;endforj=N-K+i:NA<i,j>=1;endendenddisp<A>;%隨機(jī)化重連fori=1:Nforj=i+1:NifA<i,j>==1pp=unifrnd<0,1>;ifpp<=pA<i,j>=0;A<j,i>=0;b=unidrnd<N>;whilei==bb=unidrnd<N>;endA<i,b>=1;A<b,i>=1;endendendend%根據(jù)鄰接矩陣連線fori=1:Nforj=1:NifA<i,j>==1plot<[x<i>,x<j>],[y<i>,y<j>],'linewidth',1>;holdon;endendendholdoffaver_path=aver_pathlength<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=0.fig的截圖P=0.1〔ws_n=16_k=2_p=0.1.fig的截圖p=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)過與它相連的節(jié)點(diǎn),逐步"走"到另一個(gè)節(jié)點(diǎn)sj所經(jīng)過的路途,稱為兩點(diǎn)間的路徑。其中最短的路徑也稱為兩點(diǎn)間的距離,記作。而平均路徑長(zhǎng)度定義為：這其中N是節(jié)點(diǎn)數(shù)目,并定義節(jié)點(diǎn)到自身的最短路徑長(zhǎng)度為0。如果不計(jì)算到自身的距離,那么平均路徑長(zhǎng)度的定義就變成：集聚系數(shù)集聚系數(shù)〔也稱群聚系數(shù)、集群系數(shù)是用來描述圖或網(wǎng)絡(luò)中的頂點(diǎn)〔節(jié)點(diǎn)之間結(jié)集成團(tuán)的程度的系數(shù)。具體來說,是一個(gè)點(diǎn)的鄰接點(diǎn)之間相互連接的程度。例如在社交網(wǎng)絡(luò)中,你的朋友之間相互認(rèn)識(shí)的程度。一個(gè)節(jié)點(diǎn)si的集聚系數(shù)C<i>等于所有與它相連的頂點(diǎn)相互之間所連的邊的數(shù)量,除以這些頂點(diǎn)之間可以連出的最大邊數(shù)。顯然C<i>是一個(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ù)很高,平均路徑長(zhǎng)度也十分短。例如完全耦合網(wǎng)絡(luò),每?jī)蓚€(gè)節(jié)點(diǎn)之間都相連,所以集聚系數(shù)是1,平均路徑長(zhǎng)度是1。然而,現(xiàn)實(shí)中的復(fù)雜網(wǎng)絡(luò)是稀疏的,連接的個(gè)數(shù)只是節(jié)點(diǎn)數(shù)的若干倍〔,遠(yuǎn)遠(yuǎn)不到飽和。如果考慮將節(jié)點(diǎn)排列成正多邊形,每各節(jié)點(diǎn)都只與距離它最近的2K個(gè)節(jié)點(diǎn)相連,那么在K比較大時(shí),其集聚系數(shù)為：雖然能保持高集聚系數(shù),但平均路徑長(zhǎng)度為：平均路徑長(zhǎng)度與節(jié)點(diǎn)數(shù)成正比。純粹的隨機(jī)網(wǎng)絡(luò)〔如ER隨機(jī)網(wǎng)絡(luò)模型有著很小的平均路徑長(zhǎng)度,但同時(shí)集聚系數(shù)也很小?？墒乾F(xiàn)實(shí)中的不少網(wǎng)絡(luò)雖然有很小的平均路徑長(zhǎng)度,但卻也有著比隨機(jī)網(wǎng)絡(luò)高出相當(dāng)多的集聚系數(shù)。因此瓦茨和斯特羅加茨認(rèn)為,現(xiàn)實(shí)中的復(fù)雜網(wǎng)絡(luò)是一種介于規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)之間的網(wǎng)絡(luò)。他們把這種特性稱為現(xiàn)實(shí)網(wǎng)絡(luò)的小世界特性,就是：有很小的平均路徑長(zhǎng)度：在節(jié)點(diǎn)數(shù)N很大時(shí),平均路徑長(zhǎng)度近似于有很高的集聚系數(shù)：集聚系數(shù)大約和規(guī)則網(wǎng)絡(luò)在同一數(shù)量級(jí),遠(yuǎn)大于隨機(jī)網(wǎng)絡(luò)的集聚系數(shù)。圖bWS模型的集聚系數(shù)C〔紅色與平均路徑長(zhǎng)度L<藍(lán)色>隨p變化的圖像相應(yīng)程序代碼〔使用Matlab實(shí)現(xiàn)ws.m〔位于"代碼"文件夾clc;clearall;formatlong;n=1000;k=5;L=zeros<14,20>;C=zeros<14,20>;fori=1:14p<15-i,1>=1/2^<i-1>;end%p=zeros<1,14>;%p1=zeros<14,20>;%LWS=zeros<14,1>;%CWS=zeros<14,1>;%%生成最近鄰耦合網(wǎng)絡(luò)A=zeros<n>;fori=1:nforj=i+1:i+kjj=j;ifj>njj=mod<j,n>;endA<i,jj>=1;A<jj,i>=1;endend%%計(jì)算平均路徑長(zhǎng)度L<0>D1=A;D1<find<D1==0>>=inf;%將鄰接矩陣變?yōu)猷徑泳嚯x矩陣,兩點(diǎn)無邊相連時(shí)賦值為inf,自身到自身的距離為0.fori=1:nD1<i,i>=0;endm=1;whilem<=n%Floyd算法求解任意兩點(diǎn)的最短距離fori=1:nforj=1:nifD1<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)度%%計(jì)算聚類系數(shù)C<0>Ci0=zeros<n,1>;fori=1:naa1=find<D1<i,:>==1>;%尋找子圖的鄰居節(jié)點(diǎn)ifisempty<aa1>Ci0<i>=0;elsem1=length<aa1>;ifm1==1Ci0<i>=0;elseB1=D1<aa1,aa1>;%抽取子圖的鄰接矩陣Ci0<i>=length<find<B1==1>>/<m1*<m1-1>>;endendendC0=mean<Ci0>;forz=1:14%p<z>=1/2^<z-1>;forg=1:20%%生成最近鄰耦合網(wǎng)絡(luò)B=zeros<n>;fori=1:nforj=i+1:i+kjj=j;ifj>njj=mod<j,n>;endB<i,jj>=1;B<jj,i>=1;endend%隨機(jī)化重連%fori=1:n%p_rand=rand<1,1>;%b=find<B<i,:>==1>;%forj=1:length<b>%j1=b<j>;%ifp_rand<p<z,1>%%生成的隨機(jī)數(shù)小于p,則邊進(jìn)行隨機(jī)化重連,否則,邊不進(jìn)行重連%B<i,j1>=0;B<j1,i>=0;%bb=randint<1,1,[1,n]>;%ifB<i,bb>==0&&B<bb,i>==0&&bb~=i%重連條件%B<i,bb>=1;B<bb,i>=1;%end%end%end%endfori=1:nforj=1:kp_rand=rand<1,1>;ifp_rand<p<z,1>bb=randint<1,1,[1,n]>;ifB<i,bb>==0&&B<bb,i>==0&&bb~=i%重連條件j2=j+i;ifj2>nj2=mod<j2,n>;endB<i,j2>=0;B<j2,i>=0;B<i,bb>=1;B<bb,i>=1;endendendend%%計(jì)算平均路徑長(zhǎng)度aver_L%n1=size<A,2>;D=B;D<find<D==0>>=inf;%將鄰接矩陣變?yōu)猷徑泳嚯x矩陣,兩點(diǎn)無邊相連時(shí)賦值為inf,自身到自身的距離為0.fori=1:nD<i,i>=0;endm2=1;whilem2<=n%Floyd算法求解任意兩點(diǎn)的最短距離fori=1:nforj=1:nifD<i,j>>D<i,m2>+D<m2,j>D<i,j>=D<i,m2>+D<m2,j>;endendendm2=m2+1;end%iflength<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>;fori=1:naa=find<D<i,:>==1>;%尋找子圖的鄰居節(jié)點(diǎn)ifisempty<aa>Ci<i>=0;elsem3=length<aa>;ifm3==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>