複雜網路綜述3——網路特性

最簡單的網路模型是隨即圖，在這種模型中，無向邊被隨機分配到個頂點之間， $frac{1}{2}n(n-1)$ 條邊中的每一條邊都會以相同的概率出現，每個頂點的連邊數服從泊松分佈。隨即圖被數學家們廣泛研究，形成了一系列成果。很多真實網路有趣的特徵近年來吸引了大量的研究者，但是這些特徵與隨機網路中的又大不相同。真實網路在某些方面的不隨機性表明可能存在指導網路形成的機制和能通過研究網路結構來實現某一目標的方法。

小世界特性

在20世紀60年代Stanley Milgram的社會學實驗中，只需通過六個人就能夠將一封信送至目標個體。該結果是第一個對小世界效用的直接證明，事實上，大多數網路中兩個節點間的路徑都很短。在Milgram之前的1929年，匈牙利作家Frigyes Karinthy在一篇小說中就推測存在小世界效應，更嚴格的證明是由Pool和Kochen給出的，儘管發表在Milgram的研究之後，但是他們十年前就在預印版中提出了該問題。如今，小世界效應已經在大量的不同的網路中得到了證實。

現在考慮一個無向網路，定義為節點對之間的平均最短路徑，那麼 $l=frac{1}{frac{1}{2}n(n+1)}sum_{igeq j}{d_{ij}}$

$d_{ij}$ 是節點到節點的距離，如果兩個頂點不可達，則把距離定義為無限遠。

上述公式包含了節點到自身的路徑長度(路徑長為0)。在一個有個頂點和條邊的網路中，可以用廣度優先遍歷（也叫「燃燒演算法」）在時間內得到。小世界效應對發生在網路上的動態過程有明顯的影響。例如，一個人想在網路上傳播一條信息，由「六度分離」理論可知在大多數網路上這種效應會加快傳播，尤其是謠言。小世界效應會影響網際網路上的中繼器的數量，旅行者的航班數和疾病在人羣中傳播的時間等等，這種效應也會影響室內遊戲，尤其是計算「Erdos數」和「Bacon數」。

另一方面，小世界效應在數學上也是顯而易見的。如果距中心點距離小於的節點數以指數增長，那麼就以增長。近年來，小世界效應的定義變得越來越準確：如果說一個網路具有小世界效應，那麼的值相對於網路規模應該是對數尺度（對於一個固定平均度的網路）。有一些網路的l值增長的甚至比還慢。Bollobas和Riordan證明瞭在power-law網路中，的增長不會快於 ,並且Cohen和Havlin討論了真實情況或許比這還慢。

聚集性

與隨機網路不同的是，在許多網路中，如果節點A和B相連，B和C相連，那麼A和C也很有可能相連，也即，你朋友的朋友也是你的朋友。聚集係數就是來衡量這種可能性大小的一個指標，聚集係數可以衡量一個網路，也可以衡量網路中的一個節點。

$C=frac{3 imes number of triangles in the network}{number of connected triples of vertices}$

$C_{i}=frac{number of triangles connected to vertex i}{number of triples centered on vertex i}$ Dorogovtsev, Goltsev,Mendes和Szabo,Alava,Kertesz兩組人發現在scale-free網路中， $C_{i}$ 正比於 $k_{i}^{-1}$ ，其中 $k_{i}$ 是節點i的度。類似的特徵在真實網路中也得到了證。

聚集係數是衡量一個網路中三角形的密集程度的，也可以將它推廣到長度為4或5的圈。

度分佈

節點的度是其上的連邊數，定義 $p_{k}$ 為網路中度為k的節點的比例，也即在網路中隨機選擇一條邊，其度為k的概率是 $p_{k}$ .在隨機圖中，節點的度服從泊松分佈，但是真實網路的分佈卻不是這樣。大多數真實網路的度分佈會向右偏移，出現長尾效應。

量化這個長尾需要一些技巧，儘管理論上可以畫出度分佈的直方圖，但是實際上極少有能很好統計長尾的指標，並且，直接畫出的直方圖中包含大量的噪音。有兩種方法可以解決該問題：一種是，每隔指數間隔大小統計一下度分佈（節點度之和除以間隔大小），這種統計方法一般用在對數坐標中，因為間隔越來越大，統計問題也隨之減小；另一種是用累計分佈函數，

$P_{k}=sum_{k^{}=k}^{infty}{p_{k^{}}}$

表示度大於或等於k的概率之和。這種方法能夠保證所有的數據都能展現出來，並且消除了不同數據點落到同一間隔的問題。累計分佈函數同樣能夠減少長尾處的噪音。在power-law網路中，度的累積分佈函數,

$P_{k}simsum_{k^{}=k}^{infty}{k^{-alpha}}sim k^{-(alpha-1)}$

對於其它類型的網路，度分佈的情況要稍微複雜一些，例如，二部圖，兩類節點都有各自的度分佈。還有在有向圖中，有入度分佈，出度分佈和二者的聯合分佈.

a. Scale-Free網路

Power-law網路有時也叫scale-free網路，儘管只是它的度分佈服從scale-free。最早的scale-free網路可能是Price的科學論文引用網路，這個網路中的介於2.5到3之間，在後來的一篇論文中，他指出了的精確值（3.04）。他還發現了這個網路中的出度服從power-law分佈。Power-law現象還廣泛存在於其他的引用網路、WWW網、網際網路、代謝網路、電話網路和人類的性關係網路中。

b.最大度

網路中節點的最大度一般依賴於網路的規模。給定一個特定的度分佈（假設所有的度都是獨立採樣的，真實網路並非如此），隨機選取m個度為k的頂點，網路中不存在比k更大的度的概率為，

$h_{k}=sum_{m=1}^{n}{inom{n}{m}p_{k}^{m}(1-P_{k})^{n-m}}=(p_{k}+1-P_{k})^{n}-(1-P_{k})^{n}$

那麼最大度的期望值為 $k_{max}=sum_{k}{h_{k}}$

對於很小或者很大的k， $h_{k}$ 都會趨於0，因此 $K_{max}由h_{k}的最大值決定$

網路彈性

與度分佈相關的另一個特性是在移除節點後網路的彈性。大多數網路的網路功能依賴於其連接性，即節點間是否可達。如果網路中的節點被移除後，那麼平均意義上而言，路徑長度會增加，最終節點間變得不可達。有一些不同的方式來移除節點，例如，可以在網路中隨機選點進行移除，或者移除一些特殊的點（比如最大度的點），不同的網路也具有不同的彈性。網路彈性在流行病學中具有特別重要的作用，例如移除某個節點意味著給個體接種疫苗，因為接種疫苗不僅意味著使該個體免於感染，同時也切斷了傳播路徑，這在公共健康方面有著重要作用。

Albert,Jeong和Barabasi研究了在兩個網路中——具有6000個自治系統的網際網路和具有326000個網頁的萬維網子網——刪除頂點後的影響。兩種網路都服從power-law分佈，然後他們測量在隨機刪點和刪除最大度的點後點對之間的平均路徑長度。