1、課題：無標度網絡模型構造姓名趙訓學號201026811130 班級實驗班 1001 一、源起無標度網絡（或稱無尺度網絡） 的概念是隨著對復雜網絡的研究而出現的。“網絡”其實就是數學中圖論研究的圖，由一群頂點以及它們之間所連的邊構成。在網絡理論中則換一套說法，用“節點”代替“頂點”，用“連結”代替“邊”。復雜網絡的概念，是用來描述由大量節點以及這些節點之間錯綜復雜的聯系所構成的網絡。這樣的網絡會出現在簡單網絡中沒有的特殊拓撲特性。自二十世紀 60年代開始，對復雜網絡的研究主要集中在隨機網絡上。隨機網絡，又稱隨機圖，是指通過隨機過程制造出的復雜網絡。最典型的隨機網絡是保羅埃爾德什和阿爾弗雷德雷尼提

2、出的er 模型。er 模型是基于一種“自然”的構造方法：假設有個節點，并假設每對節點之間相連的可能性都是常數。這樣構造出的網絡就是er 模型網絡。科學家們最初使用這種模型來解釋現實生活中的網絡。er 模型隨機網絡有一個重要特性， 就是雖然節點之間的連接是隨機形成的，但最后產生的網絡的度分布是高度平等的。度分布是指節點的度的分布情況。在網絡中，每個節點都與另外某些節點相連，這種連接的數目叫做這個節點的度。在網絡中隨機抽取一個節點，它的度是多少呢？這個概率分布就稱為節點的度分布。在一般的隨機網絡（如 er 模型）中，大部分的節點的度都集中在某個特殊值附近，成鐘形的泊松分布規律（見下圖）。偏離這個特

3、定值的概率呈指數性下降，遠大于或遠小于這個值的可能都是微乎其微的，就如一座城市中成年居民的身高大致的分布一樣。然而在 1998年，albert-l szl barab si 、r ka albert等人合作進行一項描繪萬維網的研究時，發現通過超鏈接與網頁、文件所構成的萬維網網絡并不是如一般的隨機網絡一樣，有著均勻的度分布。他們發現，萬維網是由少數高連接性的頁面串聯起來的。絕大多數（超過 80% ）的網頁只有不超過 4個超鏈接，但極少數頁面（不到總頁面數的萬分之一）卻擁有極多的鏈接，超過1000個，有一份文件甚至與超過 200萬個其他頁面相連。 與居民身高的例子作類比的話，就是說大多數的節點都是

4、“矮個子”，而卻又有極少數的身高百丈的“巨人”。barab si 等人將其稱為“無標度”網絡。隨機網絡的度（a）集中在某個平均值附近，而無標度網絡的度分布（b）則遵守冪律分布二、描述與定義無標度網絡的特性， 在于其度分布沒有一個特定的平均值指標，即大多數節點的度在此附近。在研究這個網絡的度分布時， barab si 等人發現其遵守冪律分布 （也稱為帕累托分布） ， 也就是說，隨機抽取一個節點， 它的度是自然數的概率：也就是說的概率正比于的某個冪次（一般是負的，記為）。因此越大，的概率就越低。然而這個概率隨增大而下降的“速度”是比較緩慢的：在一般的隨機網絡中， 下降的速度是指數性的， 而在無尺度

5、網絡中只是以多項式類的速度下降。在現實中許多大規模的無尺度網絡中，度分布的值介于 2與3之間。在對數坐標系中，度分布將會是一條斜率介于-2至-3 之間的直線。 如下圖中， 橫坐標為節點的度，從一直到；縱坐標為找到這樣的節點的概率從一直到。最高度數的節點有 882條連接。所有的藍點大致成一條直線分布 （綠色的直線）。200,000個節點的無標度網絡的度分布（對數坐標）僅僅是將度分布的冪律分布作為無標度網絡的定義有其不夠完善之處。由于冪律分布是方差可能無窮的高可變分布，對于度分布是同一個冪律分布的不同網絡，其拓撲結構和特性可能存在巨大的差異。2005年， lun li 和大衛阿爾德森（david

6、alderson ） 等人在論文邁向無標度圖的理論（towards a theory of scale free graphs）中提出了一種補充性的標度性測度。設為所有具有（依照冪律分布的）度分布的網絡的集合，對于其中每一個網絡，定義度 - 度相關數：其中表示中所有連接的集合。 根據排序原理， 如果度數大的點之間相互連接的話，那么會比較大。設為最大的，那么定義度 -度相關系數：度-度相關系數介于0與1之間。越靠近1，則稱此網絡“無尺度”的，靠近0，則稱是“富尺度”的。在此定義下，無尺度網絡中的節點度數分布特征體現了自相似的性質，而凸顯了“無尺度”的特征，與富尺度網絡之間有相當的差異。三、例子不

7、少現實中的網絡結構都屬于無標度網絡，或者有無標度的特性。 以下是一些無標度網絡的例子：網絡節點連接電影演員網絡演員出演同一部電影萬維網網頁超鏈接因特網路由器物理連接蛋白質相互作用網絡蛋白質蛋白質之間的相互作用關系金融網絡金融機構借貸關系美國飛機航班網絡機場飛機航線四、ba模型及其構造算法albert-l szl barab si 與r ka albert在1999年的論文中提出了一個模型來解釋復雜網絡的無標度特性，稱為ba 模型。這個模型基于兩個假設：增長模式：不少現實網絡是不斷擴大不斷增長而來的，例如互聯網中新網頁的誕生，人際網絡中新朋友的加入， 新的論文的發表， 航空網絡中新機場的建造等等

8、。優先連接模式：新的節點在加入時會傾向于與有更多連接的節點相連，例如新網頁一般會有到知名的網絡站點的連接，新加入社群的人會想與社群中的知名人士結識，新的論文傾向于引用已被廣泛引用的著名文獻，新機場會優先考慮建立與大機場之間的航線等等。在這種假設下， ba 模型的具體構造為： 1. 增長：從一個較小的網絡開始（這個網絡有個節點，條邊），逐步加入新的節點，每次加入一個。 2. 連接：假設原來的網絡已經有個節點（）。在某次新加入一個節點時，從這個新節點向原有的個節點連出個連結。 3. 優先連接：連接方式為優先考慮高度數的節點。對于某個原有節點（），將其在原網絡中的度數記作，那么新節點與之相連的概率為

9、：這樣，在經過次之后，得到的新網絡有個節點，一共有條邊。分析ba 模型網絡的漸近度分布 （當節點數量很大時的度分布） 主要有連續場理論、主方程法和速率方程法。 這三種方法得到的漸近結果都是相同的。2001年，b la bollob s證明了在節點數量很大時， ba 模型網絡的度分布遵從的冪律分布。之后，其它的無標度網絡模型也開始被提出。有 1000 個節點的ba 模型網絡制造 ba模型的過程：每次增加一個節點，兩個連接相應程序代碼（使用matlab 實現）freescale.m function matrix = freescale(x)n= x; m0= 3; m= 3;%初始化網絡數據ad

10、jacent_matrix = sparse( m0, m0);% 初始化鄰接矩陣for i = 1: m0for j = 1:m0if j = i %去除每個點自身形成的環 adjacent_matrix(i,j) = 1;%建立初始鄰接矩陣，3點同均同其他的點相連endendendadjacent_matrix =sparse(adjacent_matrix);%鄰接矩陣稀疏化node_degree = zeros(1,m0+1); %初始化點的度node_degree(2: m0+1) = sum(adjacent_matrix);%對度維數進行擴展for iter= 4:n iter

11、% 加點 total_degree = 2*m*(iter- 4)+6;% 計算網絡中此點的度之和 cum_degree = cumsum(node_degree);%求出網絡中點的度矩陣 choose= zeros(1,m);%初始化選擇矩陣% 選出第一個和新點相連接的頂點 r1= rand(1)*total_degree;%算出與舊點相連的概率for i= 1:iter-1if (r1=cum_degree(i)&( r1=cum_degree(i)&(r2=cum_degree(i)&(r2=cum_degree(i)&(r3=cum_degree(i)&

12、amp;(r3cum_degree(i+1) choose(3) = i;breakendendend% 新點加入網絡后, 對鄰接矩陣進行更新for k = 1:m adjacent_matrix(iter,choose(k) = 1; adjacent_matrix(choose(k),iter) = 1;end node_degree=zeros(1,iter+1); node_degree(2:iter+1) = sum(adjacent_matrix);endmatrix = adjacent_matrix; tu_plot.m function tu_plot(rel,control

13、) % 由鄰接矩陣畫連接圖， 輸入為鄰接矩陣rel，必須為方陣；%control為控制量， 0 表示畫出的圖為無向圖，1 表示有向圖。默認值為0r_size=size(rel);%a=size(x)返回的是一個行向量，該行向量第一個元素是%x 的行數，第2 個元素是x 的列數if nargin2 %nargin是用來判斷輸入變量個數的函數 control=0; %輸入變量小于2，即只有一個，就默認control為 0end if r_size(1)=r_size(2)% 行數和列數不相等，不是方陣，不予處理 disp(wrong input! the input must be a squar

14、e matrix!); return; end len=r_size(1); rho=10;%限制圖尺寸的大小r=2/1.05len;%點的半徑theta=0:(2*pi/len):2*pi*(1-1/len); pointx,pointy=pol2cart(theta,rho); theta=0:pi/36:2*pi; tempx,tempy=pol2cart(theta,r); point=pointx,pointy; hold on for i=1:len temp=tempx,tempy+point(i,1)*ones(length(tempx),1),point(i,2)*ones(

15、length(tempx),1); plot(temp(:,1),temp(:,2),r); text(point(i,1)-0.3,point(i,2),num2str(i);%畫點endfor i=1:len for j=1:len if rel(i,j) link_plot(point(i,:),point(j,:),r,control); %連接有關系的點endendend set(gca,xlim,-rho-r,rho+r,ylim,-rho-r,rho+r); axis off function link_plot(point1,point2,r,control)% 連接兩點tem

16、p=point2-point1; if (temp(1)&(temp(2) return; %不畫子回路end theta=cart2pol(temp(1),temp(2); point1_x,point1_y=pol2cart(theta,r); point_1=point1_x,point1_y+point1; point2_x,point2_y=pol2cart(theta+(2*(thetapi)-1)*pi,r); point_2=point2_x,point2_y+point2; if control arrow(point_1,point_2); else plot(point_1(1),point_2(1),point_1(2),point_2(2); end 輸入freescale （50），可建立一個初始結點為3，最終結點為 50的無標度網絡，用tu_plot()畫圖可得到網絡建模圖形初始結點為 3，最終結點為 70 的無標度網絡圖形五、結論在網絡理論中，無標度網絡（或稱無尺度網絡）是帶有