matlab課程論文—無(wú)尺度網(wǎng)絡(luò)的實(shí)現(xiàn)與可視化

1、課程論文：無(wú)尺度網(wǎng)絡(luò)的實(shí)現(xiàn)與可視化摘要隨著對(duì)復(fù)雜網(wǎng)絡(luò)的深入研究，越來(lái)越多的系統(tǒng)，如神經(jīng)網(wǎng)絡(luò)和萬(wàn)維網(wǎng)，都被描述為有著復(fù)雜拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)。而很多的網(wǎng)絡(luò)中節(jié)點(diǎn)的度分布都滿(mǎn)足與圖的大小無(wú)關(guān)的冪率分布，這被稱(chēng)為無(wú)尺度網(wǎng)絡(luò)。冪率分布被發(fā)現(xiàn)是由增長(zhǎng)和優(yōu)先連接導(dǎo)致的。在這里我用matlab實(shí)現(xiàn)了網(wǎng)絡(luò)動(dòng)態(tài)生長(zhǎng)的過(guò)程并把最終生成的無(wú)尺度網(wǎng)絡(luò)進(jìn)行了可視化。1引言1.1無(wú)尺度網(wǎng)絡(luò)的提出在網(wǎng)絡(luò)理論的研究中，復(fù)雜網(wǎng)絡(luò)是由數(shù)量巨大的節(jié)點(diǎn)和節(jié)點(diǎn)之間錯(cuò)綜復(fù)雜的關(guān)系共同構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu)。用數(shù)學(xué)的語(yǔ)言來(lái)說(shuō)，就是一個(gè)有著足夠復(fù)雜的拓?fù)浣Y(jié)構(gòu)特征的圖。復(fù)雜網(wǎng)絡(luò)的研究是現(xiàn)今科學(xué)研究中的一個(gè)熱點(diǎn)，與現(xiàn)實(shí)中各類(lèi)高復(fù)雜性系統(tǒng)，如的互聯(lián)網(wǎng)網(wǎng)絡(luò)、神經(jīng)

2、網(wǎng)絡(luò)和社會(huì)網(wǎng)絡(luò)的研究有密切關(guān)系。無(wú)論在社會(huì)科學(xué)、生命科學(xué)還是信息科學(xué)中，都存在著擁有十分復(fù)雜的拓?fù)浣Y(jié)構(gòu)特征的網(wǎng)絡(luò)結(jié)構(gòu)。這種網(wǎng)絡(luò)結(jié)構(gòu)的形式既不是完全規(guī)則，也不是完全隨機(jī)的，例如在度分布中出現(xiàn)重尾現(xiàn)象。在一般的隨機(jī)網(wǎng)絡(luò)（如ER模型）中，大部分的節(jié)點(diǎn)的度都集中在某個(gè)特殊值（平均值）附近，成鐘形的泊松分布規(guī)律。偏離這個(gè)特定值的概率呈指數(shù)性下降，遠(yuǎn)大于或遠(yuǎn)小于這個(gè)值的可能都是微乎其微的，就如一座城市中成年居民的身高大致的分布一樣。然而現(xiàn)實(shí)世界的網(wǎng)絡(luò)大部分都不是隨機(jī)網(wǎng)絡(luò)，少數(shù)的節(jié)點(diǎn)往往擁有大量的連接，而大部分節(jié)點(diǎn)卻很少，一般而言他們符合二八定律，(也就是80/20 Pareto principle)。在1

3、998年，Barabasi、Albert等人合作進(jìn)行一項(xiàng)描繪萬(wàn)維網(wǎng)的研究時(shí)，發(fā)現(xiàn)通過(guò)超鏈接與網(wǎng)頁(yè)、文件所構(gòu)成的萬(wàn)維網(wǎng)網(wǎng)絡(luò)并不是如一般的隨機(jī)網(wǎng)絡(luò)一樣，有著均勻的度分布4。他們發(fā)現(xiàn)，萬(wàn)維網(wǎng)是由少數(shù)高連接性的頁(yè)面串聯(lián)起來(lái)的。絕大多數(shù)（超過(guò)80%）的網(wǎng)頁(yè)只有不超過(guò)4個(gè)超鏈接，但極少數(shù)頁(yè)面（不到總頁(yè)面數(shù)的萬(wàn)分之一）卻擁有極多的鏈接，超過(guò)1000個(gè)，有一份文件甚至與超過(guò)200萬(wàn)個(gè)其他頁(yè)面相連。與居民身高的例子作類(lèi)比的話(huà)，就是說(shuō)大多數(shù)的節(jié)點(diǎn)都是“矮個(gè)子”，而卻又有極少數(shù)的身高百丈的“巨人”。Barabasi等人將其稱(chēng)為無(wú)尺度網(wǎng)絡(luò)1。1.2無(wú)尺度網(wǎng)絡(luò)的性質(zhì)人們給具有這種性質(zhì)的網(wǎng)絡(luò)起了一個(gè)特別的名字無(wú)尺度網(wǎng)絡(luò)。

4、這里的無(wú)標(biāo)度是指網(wǎng)絡(luò)缺乏一個(gè)特征度值（或平均度值），即節(jié)點(diǎn)度值的波動(dòng)范圍相當(dāng)大，典型的特性則是度分布的冪定律(Power law)遞減。所謂一個(gè)網(wǎng)絡(luò)的度分布，是指隨機(jī)地從網(wǎng)絡(luò)中挑出一個(gè)節(jié)點(diǎn)時(shí)，這個(gè)節(jié)點(diǎn)的度為d的概率。無(wú)尺度網(wǎng)絡(luò)的度分布滿(mǎn)足冪律分布，也就是說(shuō)d=k的概率正比于k的某個(gè)次冪：Pd=kk-。冪律分布這一特性，正說(shuō)明了無(wú)尺度網(wǎng)絡(luò)的度分布與一般隨機(jī)網(wǎng)絡(luò)的不同。隨機(jī)網(wǎng)絡(luò)的度分布屬于正態(tài)分布，因此有一個(gè)特征度數(shù)，即大部分節(jié)點(diǎn)的度數(shù)都接近它。無(wú)尺度網(wǎng)絡(luò)的度分布是呈集散分布：大部分的節(jié)點(diǎn)只有比較少的連接，而少數(shù)節(jié)點(diǎn)有大量的連接。由于不存在特征度數(shù)，因此得名“無(wú)尺度”?，F(xiàn)實(shí)生活中，無(wú)尺度網(wǎng)絡(luò)的例子

5、有很多。因特網(wǎng)、美國(guó)演員網(wǎng)絡(luò)、細(xì)胞中蛋白質(zhì)的交互網(wǎng)絡(luò)都是無(wú)尺度網(wǎng)絡(luò)。無(wú)尺度網(wǎng)絡(luò)的特性是：當(dāng)節(jié)點(diǎn)意外失效或改變時(shí)，對(duì)網(wǎng)絡(luò)的影響一般很小，只有很小的概率會(huì)發(fā)生大的影響，但當(dāng)有Hub節(jié)點(diǎn)受到影響時(shí)，網(wǎng)絡(luò)受到的影響會(huì)比隨機(jī)網(wǎng)絡(luò)大得多。1.3無(wú)尺度網(wǎng)絡(luò)的形成無(wú)尺度網(wǎng)絡(luò)是怎么產(chǎn)生的呢？?jī)缏史植加质侨绾涡纬傻腂arabasi在1999年的論文中提出了一個(gè)BA模型來(lái)解釋復(fù)雜網(wǎng)絡(luò)的無(wú)尺度特性2。這個(gè)模型基于兩個(gè)假設(shè)：l 增長(zhǎng)模式(Growth)：不少現(xiàn)實(shí)網(wǎng)絡(luò)是不斷擴(kuò)大不斷增長(zhǎng)而來(lái)的，例如互聯(lián)網(wǎng)中新網(wǎng)頁(yè)的誕生，人際網(wǎng)絡(luò)中新朋友的加入，新的論文的發(fā)表，航空網(wǎng)絡(luò)中新機(jī)場(chǎng)的建造等等。l 優(yōu)先連接模式(Preferent

6、ial attachment)：新的節(jié)點(diǎn)在加入時(shí)會(huì)傾向于與有更多連接的節(jié)點(diǎn)相連，例如新網(wǎng)頁(yè)一般會(huì)有到知名的網(wǎng)絡(luò)站點(diǎn)的連接，新加入社群的人會(huì)想與社群中的知名人士結(jié)識(shí)，新的論文傾向于引用已被廣泛引用的著名文獻(xiàn)，新機(jī)場(chǎng)會(huì)優(yōu)先考慮建立與大機(jī)場(chǎng)之間的航線(xiàn)等等。在這種假設(shè)之下，BA模型的具體構(gòu)造為：1. 增長(zhǎng)：從一個(gè)較小的網(wǎng)絡(luò)開(kāi)始（這個(gè)網(wǎng)絡(luò)是有m0個(gè)節(jié)點(diǎn)的完全圖），逐步加入新的節(jié)點(diǎn)，每次加入一個(gè)新節(jié)點(diǎn)。新節(jié)點(diǎn)與m個(gè)(m小于等于m0)不同的已經(jīng)存在于網(wǎng)絡(luò)中的舊點(diǎn)相連產(chǎn)生m條新邊。2. 優(yōu)先連接：連接方式為優(yōu)先考慮高度數(shù)的節(jié)點(diǎn)。對(duì)于某個(gè)原有節(jié)點(diǎn)i，將其在原網(wǎng)絡(luò)中的度數(shù)記作di，那么新節(jié)點(diǎn)與之相連的概率為：Pi

7、=diidi論文中證明了這種方式產(chǎn)生的網(wǎng)絡(luò)度分度為冪率分布，是無(wú)尺度網(wǎng)絡(luò)。2無(wú)尺度網(wǎng)絡(luò)的實(shí)現(xiàn)基于增長(zhǎng)和優(yōu)先選擇機(jī)制，這里用matlab程序生成無(wú)尺度網(wǎng)絡(luò)。定義函數(shù)scale_free，輸入變量為網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)，輸出為網(wǎng)絡(luò)對(duì)應(yīng)圖的鄰接矩陣。Matlab代碼如下：function matrix = scale_free(X) %初始化網(wǎng)絡(luò)數(shù)據(jù)N = X; %網(wǎng)絡(luò)結(jié)點(diǎn)個(gè)數(shù)m0 = 3; %初始結(jié)點(diǎn)個(gè)數(shù)m = 3; %后來(lái)每個(gè)新加每個(gè)節(jié)點(diǎn)發(fā)出的邊的個(gè)數(shù)adjacent_matrix = zeros(N); % 初始化鄰接矩?for i = 1: m0 for j = 1:m0 if (j = i)

8、%去除每個(gè)點(diǎn)自身形成的? adjacent_matrix(i,j) =1; %建立初始鄰接矩陣，3個(gè)節(jié)點(diǎn)構(gòu)成完全圖 end endend node_degree = zeros(1,m0+1); %初始化點(diǎn)的度temp = sum(adjacent_matrix);node_degree(2: m0+1) = temp(1:m0); %求每個(gè)節(jié)點(diǎn)的度%node_degree(i+1)為第i個(gè)節(jié)點(diǎn)的度，方便后面總度數(shù)的計(jì)算 for iter= 4:N %循環(huán)加新節(jié)點(diǎn) total_degree = 2*m*(iter - 4) + 6; %計(jì)算網(wǎng)絡(luò)中此點(diǎn)的度之和 cum_degree = cums

9、um(node_degree); %求出網(wǎng)絡(luò)中節(jié)點(diǎn)的度的累加和 choose = zeros(1,m); %初始化選擇矩陣 %選出第一個(gè)和新點(diǎn)相連接的頂點(diǎn) r1= rand(1)*total_degree; %算出與舊點(diǎn)相連的概率 for i= 1:iter-1 if ( (r1>=cum_degree(i)&&( r1<cum_degree(i+1) ) %優(yōu)先選取度大的點(diǎn) choose(1) = i; break end end %選出第二個(gè)和新點(diǎn)相連接的頂點(diǎn) choose(2) = choose(1); while ( choose(2) = choose(1

10、) ) %第一個(gè)點(diǎn)和第二個(gè)點(diǎn)相同的話(huà)，重新選擇 r2 = rand(1)*total_degree; for i = 1:iter-1 if (r2>=cum_degree(i)&&(r2<cum_degree(i+1) choose(2) = i; break end end end %選出第三個(gè)和新點(diǎn)相連接的頂? choose(3) = choose(1); while ( (choose(3)=choose(1)|(choose(3)=choose(2) ) r3 = rand(1)*total_degree; for i =1:iter-1 if (r3&g

11、t;=cum_degree(i)&&(r3<cum_degree(i+1) choose(3) = i; break end end end %新點(diǎn)加入網(wǎng)絡(luò)后, 對(duì)鄰接矩陣進(jìn)行更新 for k = 1:m adjacent_matrix(iter,choose(k) = 1; adjacent_matrix(choose(k),iter) = 1; end %調(diào)整節(jié)點(diǎn)度的值 node_degree=zeros(1,iter+1); temp = sum(adjacent_matrix); node_degree(2:iter+1) = temp(1:iter);endma

12、trix = adjacent_matrix;輸入scale_free(50)，可以得到一個(gè)50*50的臨界矩陣，對(duì)應(yīng)的網(wǎng)絡(luò)就是隨機(jī)生成的無(wú)尺度網(wǎng)絡(luò)。但是這只是一個(gè)矩陣，用C語(yǔ)言，Java都可以生成。而且舉著過(guò)于抽象，難以理解，無(wú)法把握住無(wú)尺度網(wǎng)絡(luò)的特性，于是用matlab把這個(gè)網(wǎng)絡(luò)可視化。3無(wú)尺度網(wǎng)絡(luò)的可視化對(duì)于生成的無(wú)尺度網(wǎng)絡(luò)，用matlab繪圖工具可視化。定義函數(shù)graph_plot，輸入變量為一個(gè)圖的鄰接矩陣，且為方針，否則會(huì)輸出錯(cuò)誤信息。輸出為鄰接矩陣對(duì)應(yīng)的圖。整體思路為首先繪制出每個(gè)節(jié)點(diǎn)，這里把節(jié)點(diǎn)放置在一個(gè)以原點(diǎn)為圓心的圓上，排列比較整齊。然后根據(jù)臨界矩陣?yán)L制出節(jié)點(diǎn)之間的邊，用連

13、線(xiàn)代表。同時(shí)再在每個(gè)節(jié)點(diǎn)附近標(biāo)注出節(jié)點(diǎn)的度，便于觀(guān)察冪率分布。Matlab代碼如下：function graph_plot(Adjacent)row,col = size(Adjacent);if(row=col) %不是方陣，報(bào)錯(cuò) disp('Wrong Input! The input must be a square matrix!'); return;endN = row; %取得節(jié)點(diǎn)個(gè)數(shù)node_degree = sum(Adjacent); %計(jì)算每個(gè)節(jié)點(diǎn)的度angle=0:2*pi/N:2*pi*(1-1/N); %計(jì)算每個(gè)節(jié)點(diǎn)的偏角x=100*cos(angle

14、); %計(jì)算每個(gè)節(jié)點(diǎn)的坐標(biāo)y=100*sin(angle);for i=1:N for j=i+1:N if Adjacent(i,j)=1 %繪制節(jié)點(diǎn)之間的連線(xiàn) plot(x(i),x(j),y(i),y(j),'linewidth',1); hold on; end end %繪制節(jié)點(diǎn)的度 text(x(i)+3*cos(angle(i),y(i)+3*sin(angle(i),num2str(node_degree(i) );endhold offaxis off可以用graph_plot函數(shù)可視化scale_free函數(shù)生成的鄰接矩陣。例如在matlab輸入：graph

15、_plot(scale_free(50)，可以得到一個(gè)可視化的有50個(gè)節(jié)點(diǎn)的無(wú)尺度網(wǎng)絡(luò)。這個(gè)圖上從0°到360°按照逆時(shí)針排列著50個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)上的數(shù)字代表著節(jié)點(diǎn)的度，這些連線(xiàn)代表著節(jié)點(diǎn)之間的邊。從圖上可以大致看出比較靠前的節(jié)點(diǎn)的度比較大，而后來(lái)新加入的節(jié)點(diǎn)度稍微小一些，而且圖上大部分的節(jié)點(diǎn)度都比較小，而很少數(shù)的節(jié)點(diǎn)則擁有很大的度，復(fù)合二八定律。下面這張圖是100個(gè)節(jié)點(diǎn)的無(wú)尺度網(wǎng)絡(luò)可視化結(jié)果。由于節(jié)點(diǎn)比較多，看起來(lái)沒(méi)有那么舒適，但是還是可以看到度分布的二八定律。4分析與思考無(wú)尺度網(wǎng)絡(luò)還有一個(gè)特點(diǎn)就是“富者越富”，因?yàn)樾鹿?jié)點(diǎn)發(fā)出的邊的選擇是優(yōu)先選擇度比較大的點(diǎn)。從可視化結(jié)

16、果就可看出，度比較大的點(diǎn)基本都分布在第一象限，也就是最初選定的初始節(jié)點(diǎn)和比較早加進(jìn)去的點(diǎn)。這也是因?yàn)榫W(wǎng)絡(luò)中最開(kāi)始出現(xiàn)的節(jié)點(diǎn)在最初幾步新加入節(jié)點(diǎn)時(shí)有較大的概率被新加的節(jié)點(diǎn)選中作為鄰居。而由于比較早的節(jié)點(diǎn)有較大的幾率在每一步被選中，因而他們的度相比于后加入的節(jié)點(diǎn)會(huì)比較大，在后續(xù)節(jié)點(diǎn)加入過(guò)程中更容易被選中。有如滾雪球般，最初的節(jié)點(diǎn)度比較大，容易被選中。容易被選中就導(dǎo)致度更大，最后導(dǎo)致了度分布為冪率分布。當(dāng)然還有一些值得思考的問(wèn)題，例如后加入的節(jié)點(diǎn)有沒(méi)有可能因?yàn)槟硞€(gè)關(guān)系而突然取得領(lǐng)先優(yōu)勢(shì)，在網(wǎng)絡(luò)中成為度最大的節(jié)點(diǎn)？或者在最開(kāi)始每個(gè)節(jié)點(diǎn)的度都一樣的時(shí)候，度最大的節(jié)點(diǎn)時(shí)如何逐漸脫穎而出的？參考文獻(xiàn)1 Al

17、bert, Réka, Hawoong Jeong, and Albert-László Barabási. "Internet: Diameter of the world-wide web." Nature 401.6749 (1999): 130-131.2 Barabási, Albert-László, and Réka Albert. "Emergence of scaling in random networks." science 286.5439 (1999): 509-512.5課程收獲和建議這學(xué)期我選修了matlab課程，收獲不小。不得不說(shuō)matlab是一款功能很強(qiáng)大的軟件，上至矩陣運(yùn)算，下至方程組求解，樣樣精通。真是連比較難的二次三次多元方程組都可以給出帶參數(shù)的精確解。這讓我對(duì)matlab有些相見(jiàn)恨晚的感覺(jué)，甚至在想，當(dāng)初學(xué)線(xiàn)性代數(shù)的時(shí)候怎么沒(méi)有去學(xué)習(xí)matlab，不然矩陣的求逆，矩陣的特征多項(xiàng)式的求解會(huì)方便很多的。我是計(jì)算機(jī)專(zhuān)業(yè)的學(xué)生，在大四上的時(shí)候接觸了matlab，那時(shí)候我在學(xué)習(xí)社交網(wǎng)絡(luò)相關(guān)的知識(shí)，需要做蒙特卡洛模擬，也需要繪圖。當(dāng)時(shí)我是把matlab代碼嵌入到