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

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

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

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

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

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

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

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

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

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

10、) ) %第一個點和第二個點相同的話，重新選擇 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 %選出第三個和新點相連接的頂? 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 %新點加入網(wǎng)絡(luò)后, 對鄰接矩陣進行更新 for k = 1:m adjacent_matrix(iter,choose(k) = 1; adjacent_matrix(choose(k),iter) = 1; end %調(diào)整節(jié)點度的值 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)，可以得到一個50*50的臨界矩陣，對應(yīng)的網(wǎng)絡(luò)就是隨機生成的無尺度網(wǎng)絡(luò)。但是這只是一個矩陣，用C語言，Java都可以生成。而且舉著過于抽象，難以理解，無法把握住無尺度網(wǎng)絡(luò)的特性，于是用matlab把這個網(wǎng)絡(luò)可視化。3無尺度網(wǎng)絡(luò)的可視化對于生成的無尺度網(wǎng)絡(luò)，用matlab繪圖工具可視化。定義函數(shù)graph_plot，輸入變量為一個圖的鄰接矩陣，且為方針，否則會輸出錯誤信息。輸出為鄰接矩陣對應(yīng)的圖。整體思路為首先繪制出每個節(jié)點，這里把節(jié)點放置在一個以原點為圓心的圓上，排列比較整齊。然后根據(jù)臨界矩陣繪制出節(jié)點之間的邊，用連

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

14、); %計算每個節(jié)點的坐標y=100*sin(angle);for i=1:N for j=i+1:N if Adjacent(i,j)=1 %繪制節(jié)點之間的連線 plot(x(i),x(j),y(i),y(j),'linewidth',1); hold on; end end %繪制節(jié)點的度 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)，可以得到一個可視化的有50個節(jié)點的無尺度網(wǎng)絡(luò)。這個圖上從0°到360°按照逆時針排列著50個節(jié)點，每個節(jié)點上的數(shù)字代表著節(jié)點的度，這些連線代表著節(jié)點之間的邊。從圖上可以大致看出比較靠前的節(jié)點的度比較大，而后來新加入的節(jié)點度稍微小一些，而且圖上大部分的節(jié)點度都比較小，而很少數(shù)的節(jié)點則擁有很大的度，復(fù)合二八定律。下面這張圖是100個節(jié)點的無尺度網(wǎng)絡(luò)可視化結(jié)果。由于節(jié)點比較多，看起來沒有那么舒適，但是還是可以看到度分布的二八定律。4分析與思考無尺度網(wǎng)絡(luò)還有一個特點就是“富者越富”，因為新節(jié)點發(fā)出的邊的選擇是優(yōu)先選擇度比較大的點。從可視化結(jié)

16、果就可看出，度比較大的點基本都分布在第一象限，也就是最初選定的初始節(jié)點和比較早加進去的點。這也是因為網(wǎng)絡(luò)中最開始出現(xiàn)的節(jié)點在最初幾步新加入節(jié)點時有較大的概率被新加的節(jié)點選中作為鄰居。而由于比較早的節(jié)點有較大的幾率在每一步被選中，因而他們的度相比于后加入的節(jié)點會比較大，在后續(xù)節(jié)點加入過程中更容易被選中。有如滾雪球般，最初的節(jié)點度比較大，容易被選中。容易被選中就導(dǎo)致度更大，最后導(dǎo)致了度分布為冪率分布。當然還有一些值得思考的問題，例如后加入的節(jié)點有沒有可能因為某個關(guān)系而突然取得領(lǐng)先優(yōu)勢，在網(wǎng)絡(luò)中成為度最大的節(jié)點？或者在最開始每個節(jié)點的度都一樣的時候，度最大的節(jié)點時如何逐漸脫穎而出的？參考文獻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課程，收獲不小。不得不說matlab是一款功能很強大的軟件，上至矩陣運算，下至方程組求解，樣樣精通。真是連比較難的二次三次多元方程組都可以給出帶參數(shù)的精確解。這讓我對matlab有些相見恨晚的感覺，甚至在想，當初學(xué)線性代數(shù)的時候怎么沒有去學(xué)習(xí)matlab，不然矩陣的求逆，矩陣的特征多項式的求解會方便很多的。我是計算機專業(yè)的學(xué)生，在大四上的時候接觸了matlab，那時候我在學(xué)習(xí)社交網(wǎng)絡(luò)相關(guān)的知識，需要做蒙特卡洛模擬，也需要繪圖。當時我是把matlab代碼嵌入到